A note on uniform circuit lower bounds for the counting hierarchy

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

7 Scopus citations

Abstract

A very recent paper by Caussinus, McKenzie, Thérien, and Vollmer [CMTV95] shows that ACC0 is properly contained in ModPH, and TC0 is properly contained in the counting hierarchy. Thus, [CMTV95] shows that there are problems in ModPH that require superpolynomialsize uniform ACC0 circuits, and problems in the counting hierarchy that require superpolynomial-size uniform TC0 circuits. The proof in [CMTV95] uses “leaf languages” as a tool in obtaining their separations, and their proof does not immediately yield larger lower bounds for the complexity of these problems. In this paper, we give a simple direct proof of these same separations, and use it to provide “sub-subexponential” size lower bounds on the size of uniform circuits for these problems.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 2nd Annual International Conference, COCOON 1996, Proceedings
EditorsJin-Yi Cai, Chak Kuen Wong, Chak Kuen Wong
PublisherSpringer Verlag
Pages127-135
Number of pages9
ISBN (Print)9783540613329
DOIs
StatePublished - 1996
Event2nd Annual International Conference on Computing and Combinatorics, COCOON 1996 - Hong Kong, Hong Kong
Duration: Jun 17 1996Jun 19 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1090
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd Annual International Conference on Computing and Combinatorics, COCOON 1996
Country/TerritoryHong Kong
CityHong Kong
Period6/17/966/19/96

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A note on uniform circuit lower bounds for the counting hierarchy'. Together they form a unique fingerprint.

Cite this