Circuits, Lower Bounds, and Circuit Analysis Algorithms.
Lead Research Organisation:
Imperial College London
Department Name: 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
Area: Algorithms, Optimizations and Markets
Organisations
People |
ORCID iD |
Dimitrios Myrisiotis (Student) |
Publications
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 | 30/09/2016 | 30/03/2022 | |||
2295711 | Studentship | EP/N509486/1 | 30/09/2017 | 30/03/2021 | Dimitrios Myrisiotis |