Circuits, Lower Bounds, and Circuit Analysis Algorithms.

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


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


10 25 50
publication icon
Cheraghchi M (2020) Circuit Lower Bounds for MCSP from Local Pseudorandom Generators in ACM Transactions on Computation Theory

Studentship Projects

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