TY - GEN

T1 - Circuit complexity, kolmogorov complexity, and prospects for lower bounds

AU - Allender, Eric

PY - 2008/1/1

Y1 - 2008/1/1

N2 - This invited Descriptional Complexity of Formal Systems lecture provides an opportunity to raise awareness of the tight connection that exists between Kolmogorov Complexity and Circuit Complexity, and to argue that this connection is useful and interesting. Kolmogorov complexity has been used to provide examples of complete sets for classes such as EXP and PSPACE that are fundamentally different than the usual complete sets (in the sense that they are provably not complete under the usual reducibilities). Furthermore, there are connections between Kolmogorov complexity and recent approaches to proving lower bounds on circuit size.

AB - This invited Descriptional Complexity of Formal Systems lecture provides an opportunity to raise awareness of the tight connection that exists between Kolmogorov Complexity and Circuit Complexity, and to argue that this connection is useful and interesting. Kolmogorov complexity has been used to provide examples of complete sets for classes such as EXP and PSPACE that are fundamentally different than the usual complete sets (in the sense that they are provably not complete under the usual reducibilities). Furthermore, there are connections between Kolmogorov complexity and recent approaches to proving lower bounds on circuit size.

UR - http://www.scopus.com/inward/record.url?scp=84905826137&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905826137&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84905826137

SN - 9780919013568

T3 - Descriptional Complexity of Formal Systems - 10th International Workshop, DCFS 2008

SP - 7

EP - 13

BT - Descriptional Complexity of Formal Systems - 10th International Workshop, DCFS 2008

PB - University of Prince Edward Island

T2 - 10th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2008

Y2 - 16 July 2008 through 18 July 2008

ER -