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.