Circuits, Lower Bounds, and Circuit Analysis Algorithms.

Lead Research Organisation: Imperial College London
Department Name: Dept of Computing

Abstract

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

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509486/1 01/10/2016 30/09/2021
2295711 Studentship EP/N509486/1 01/10/2017 31/03/2021 Dimitrios Myrisiotis