PP is closed under intersection

DOI10.1006/jcss.1995.1017zbMath0827.68040OpenAlexW4210720364MaRDI QIDQ1892214

Nick Reingold, Richard Beigel, Daniel A. Spielman

Publication date: 8 June 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1017

zbMATH Keywords

probabilistic Turing machines

Mathematics Subject Classification ID

Related Items (52)

The Bayesian ontology language \(\mathcal {BEL}\) ⋮ On closure properties of GapP ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ A linear-optical proof that the permanent is # P -hard ⋮ When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one ⋮ Complex polynomials and circuit lower bounds for modular counting ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ On ACC ⋮ Probabilistic logic with independence ⋮ Approximate Degree in Classical and Quantum Computing ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Fooling Polytopes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Learning intersections and thresholds of halfspaces ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ The effect of combination functions on the complexity of relational Bayesian networks ⋮ A lower bound for monotone perceptrons ⋮ Complexity limitations on one-turn quantum refereed games ⋮ On the power of deterministic reductions to C=P ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Commuting quantum circuits and complexity of Ising partition functions ⋮ Exponential lower bound for bounded depth circuits with few threshold gates ⋮ On measuring inconsistency in definite and indefinite databases with denial constraints ⋮ A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases ⋮ Unnamed Item ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Algorithmic Polynomials ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ New degree bounds for polynomial threshold functions ⋮ Learning intersections of halfspaces with a margin ⋮ The hardest halfspace ⋮ Open-world probabilistic databases: semantics, algorithms, complexity ⋮ On the complexity of propositional and relational credal networks ⋮ Arithmetization: A new method in structural complexity theory ⋮ Extremal properties of polynomial threshold functions ⋮ Quantum computing, postselection, and probabilistic polynomial-time ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy ⋮ Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) ⋮ Circuits over PP and PL ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Complexity results for structure-based causality. ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors

This page was built for publication: PP is closed under intersection