Circuits, Lower Bounds, and Circuit Analysis Algorithms.

We survey the connections among circuit complexity classes, circuit lower bounds, and circuit analysis algorithms. Circuit analysis algorithms include (among others) satisfiability algorithms, learning algorithms, or natural properties (which are algorithms that discriminate between functions computable in some specific circuit class and random functions). Recent work has indicated the importance of this direction by providing new intriguing ways of looking at old results, like, for example, old results regarding lower bounds, as well as by providing guidelines on acquiring new (like new lower bounds or new learning algorithms). Finally, we pose some problems that pertain to these aforementioned connections and possible extensions on them.

Area: Algorithms, Optimizations and Markets