@inbook{doi:10.1142/9789812794499_0035,
    Abstract = {Abstract In the spring of 1989, Seinosuke Toda of the University of Electro-Communications in Tokyo, Japan, proved that the polynomial hierarchy is contained in PPP [To-89]. In this Structural Complexity Column, we will briefly review Toda's result, and explore how it relates to other topics of interest in computer science. In particular, we will introduce the reader to The Counting Hierarchy: a hierarchy of complexity classes contained in PSPACE and containing the Polynomial Hierarchy. Threshold Circuits: circuits constructed of MAJORITY gates; this notion of circuit is being studied not only by complexity theoreticians, but also by researchers in an active subfield of AI studying ``neural networks''. Along the way, we'll review the important notion of an operator on a complexity class.},
    Author = {Allender, Eric W. and Wagner, Klaus W.},
    BookTitle = {Current Trends in Theoretical Computer Science},
    EPrint = {https://www.worldscientific.com/doi/pdf/10.1142/9789812794499\_0035},
    File = {Counting Hierarchies - Polynomial Time And Constant Depth Circuits.pdf},
    Pages = {469-483},
    Title = {Counting Hierarchies: Polynomial Time and Constant Depth Circuits},
    URL = {https://www.worldscientific.com/doi/abs/10.1142/9789812794499\_0035},
    bdsk-url-1 = {https://www.worldscientific.com/doi/abs/10.1142/9789812794499\_0035},
    bdsk-url-2 = {https://doi.org/10.1142/9789812794499\_0035},
    date-added = {2021-11-23 14:45:04 +0100},
    date-modified = {2021-11-23 14:45:04 +0100},
    doi = {10.1142/9789812794499_0035}
}

@inbook{doi:10.1142/9789812794499_0035, Abstract = {Abstract In the spring of 1989, Seinosuke Toda of the University of Electro-Communications in Tokyo, Japan, proved that the polynomial hierarchy is contained in PPP [To-89]. In this Structural Complexity Column, we will briefly review Toda's result, and explore how it relates to other topics of interest in computer science. In particular, we will introduce the reader to The Counting Hierarchy: a hierarchy of complexity classes contained in PSPACE and containing the Polynomial Hierarchy. Threshold Circuits: circuits constructed of MAJORITY gates; this notion of circuit is being studied not only by complexity theoreticians, but also by researchers in an active subfield of AI studying ``neural networks''. Along the way, we'll review the important notion of an operator on a complexity class.}, Author = {Allender, Eric W. and Wagner, Klaus W.}, BookTitle = {Current Trends in Theoretical Computer Science}, EPrint = {https://www.worldscientific.com/doi/pdf/10.1142/9789812794499_0035}, File = {Counting Hierarchies - Polynomial Time And Constant Depth Circuits.pdf}, Pages = {469-483}, Title = {Counting Hierarchies: Polynomial Time and Constant Depth Circuits}, URL = {https://www.worldscientific.com/doi/abs/10.1142/9789812794499_0035}, bdsk-url-1 = {https://www.worldscientific.com/doi/abs/10.1142/9789812794499_0035}, bdsk-url-2 = {https://doi.org/10.1142/9789812794499_0035}, date-added = {2021-11-23 14:45:04 +0100}, date-modified = {2021-11-23 14:45:04 +0100}, doi = {10.1142/9789812794499_0035} }