@article{BEIGEL1995191,
    Abstract = {In this seminal paper on probabilistic Turing machines, Gill asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming P ≠ PP) separation of certain query hierarchies over PP. Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons) and a lower bound on the number of threshold gates that are needed to compute the parity function.},
    Author = {Beigel, R. and Reingold, N. and Spielman, D.},
    File = {PP Is Closed under Intersection - 1-s2.0-S0022000085710173-main.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Number = {2},
    Pages = {191-202},
    Title = {PP Is Closed under Intersection},
    URL = {https://www.sciencedirect.com/science/article/pii/S0022000085710173},
    Volume = {50},
    Year = {1995},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022000085710173},
    bdsk-url-2 = {https://doi.org/10.1006/jcss.1995.1017},
    date-added = {2022-02-22 13:05:04 +0100},
    date-modified = {2022-02-22 13:05:04 +0100},
    doi = {10.1006/jcss.1995.1017}
}

@article{BEIGEL1995191, Abstract = {In this seminal paper on probabilistic Turing machines, Gill asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming P ≠ PP) separation of certain query hierarchies over PP. Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons) and a lower bound on the number of threshold gates that are needed to compute the parity function.}, Author = {Beigel, R. and Reingold, N. and Spielman, D.}, File = {PP Is Closed under Intersection - 1-s2.0-S0022000085710173-main.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Number = {2}, Pages = {191-202}, Title = {PP Is Closed under Intersection}, URL = {https://www.sciencedirect.com/science/article/pii/S0022000085710173}, Volume = {50}, Year = {1995}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022000085710173}, bdsk-url-2 = {https://doi.org/10.1006/jcss.1995.1017}, date-added = {2022-02-22 13:05:04 +0100}, date-modified = {2022-02-22 13:05:04 +0100}, doi = {10.1006/jcss.1995.1017} }