Paper: On Proofs about Threshold Circuits and Counting Hierarchies (at LICS 1998)

Authors: Jan Johannsen Chris Pollett

Abstract

We define theories of Bounded Arithmetic characterizing classes of functions computable by constant-depth threshold circuits of polynomial and quasipolynomial size. Then we define certain second-order theories and show that they characterize the functions in the Counting Hierarchy. Finally we show that the former theories are isomorphic to the latter via the so-called RSUV-isomorphism

BibTeX

  @InProceedings{JohannsenPollett-OnProofsaboutThresh,
    author = 	 {Jan Johannsen and Chris Pollett},
    title = 	 {On Proofs about Threshold Circuits and Counting Hierarchies},
    booktitle =  {Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1998)},
    year =	 {1998},
    month =	 {June}, 
    pages =      {444--452 },
    location =   {Indianapolis, IN, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }