Circuit complexity, kolmogorov complexity, and prospects for lower bounds

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationDescriptional Complexity of Formal Systems - 10th International Workshop, DCFS 2008
PublisherUniversity of Prince Edward Island
Pages7-13
Number of pages7
ISBN (Print)9780919013568
StatePublished - Jan 1 2008
Event10th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2008 - Charlottetown, PE, Canada
Duration: Jul 16 2008Jul 18 2008

Publication series

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

Other

Other10th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2008
CountryCanada
CityCharlottetown, PE
Period7/16/087/18/08

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Circuit complexity, kolmogorov complexity, and prospects for lower bounds'. Together they form a unique fingerprint.

Cite this