Holographic Algorithms
by Leslie Valiant.
Oded's comments
As clarified in the talk, the key notion is actually
that of holographic reductions between counting problems.
These reductions map combinations of sets of solutions
rather than individual solutions, and they can be used
both for deriving algorithms (i.e., by a reduction
to an easy problem) and for deriving hardness results
(i.e., by reductions from hard problems).
The original abstract
We briefly review where we are and summarize a known lower bound
argument with regard to holographic algorithms. We go on to discuss,
and illustrate with new examples, some avenues that remain open in
this framework in the search for polynomial time algorithms.
Back to
list of Oded's choices.