Russell Impagliazzo
University of California, San Diego

Meta-Algorithms: Links between Algorithm Design and Lower Bounds 

Department of Computer Science
Thursday, June 27, 2013, 1:00 p.m., Room EN-2022 

 

---

 

Abstract

Meta-algorithms are computational problems whose inputs are computational devices. Important examples are Circuit Satisfiability (where the input is a circuit and the problem is to determine whether it computes the constantly zero function), generic derandomization (given a probabilistic algorithm, estimate its acceptance probability), polynomial identity testing (given an algebraic circuit, is the polynomial it computes identically zero?), and learning (given black-box access to a circuit, find a circuit that computes approximately the same function). There is an intuitive connection between finding meta-algorithms and proving circuit lower bounds, because both require an understanding of circuits. Work in complexity theory has proved formal versions of this connection, showing that in some circumstances, lower bounds imply efficient meta-algorithms and vice versa. We will survey some of this work, and the tools used to prove such connections. Hardness vs. Randomness (Yao, AjtaiWigderson, NisanWigderson, BabaiFortnowNisanWigderson, ImpagliazzoWigderson, etc.), shows how to convert hard functions into pseudo-random generators and hence solve generic derandomization problems. The easy witness method of Kabanets and Impagliazzo, Kabanets and Wigderson can be used to prove a partial converse, converting any algorithm for generic derandomization into a circuit lower bound. Kabanets and Impagliazzo extended this connection to algebraic circuits, showing that any deterministic polynomial time algorithm for polynomial identity testing yields either a Boolean or algebraic circuit lower bound. Finally, Williams extended this to Satisfiability, showing that any non-trivial improvement over exhaustive search for Satisfiability yields a circuit lower bound. He used this to actually prove a circuit lower bound for ACC by giving an improved Satisfiability algorithm for ACC circuits. We will sketch the above results, and show how each built on the others. In particular, we will look at the various ''flips'', techniques that start with an upper bound assumption and obtain a lower bound conclusion, and vice versa.