PP is closed under intersection
From MaRDI portal
Recommendations
Cited in
(54)- Unconditional lower bounds for learning intersections of halfspaces
- A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
- On closure properties of GapP
- 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
- Circuits over PP and PL
- Complexity results for structure-based causality.
- PP is closed under truth-table reductions
- The hardest halfspace
- A structured view on weighted counting with relations to counting, quantum computation and applications
- Open-world probabilistic databases: semantics, algorithms, complexity
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- The Bayesian ontology language \(\mathcal {BEL}\)
- Probabilistic logic with independence
- On PAC learning algorithms for rich Boolean function classes
- The effect of combination functions on the complexity of relational Bayesian networks
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Learning intersections of halfspaces with a margin
- Extremal properties of polynomial threshold functions
- LWPP and WPP are not uniformly gap-definable
- Error-bounded probabilistic computations between MA and AM
- Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
- On the power of deterministic reductions to C=P
- Exponential lower bound for bounded depth circuits with few threshold gates
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The power of asymmetry in constant-depth circuits
- A lower bound for monotone perceptrons
- Relationships among $PL$, $\#L$, and the determinant
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
- Approximate degree and the complexity of depth three circuits
- Polynomial threshold functions, hyperplane arrangements, and random tensors
- Approximate Degree in Classical and Quantum Computing
- Fooling Polytopes
- Sign-rank can increase under intersection
- Algorithmic Polynomials
- On the complexity of propositional and relational credal networks
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Quantum computing, postselection, and probabilistic polynomial-time
- New degree bounds for polynomial threshold functions
- Learning intersections and thresholds of halfspaces
- Complexity limitations on one-turn quantum refereed games
- Commuting quantum circuits and complexity of Ising partition functions
- On measuring inconsistency in definite and indefinite databases with denial constraints
- A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
- Arithmetization: A new method in structural complexity theory
- Power of counting by nonuniform families of polynomial-size finite automata
- On measuring inconsistency in graph databases with regular path constraints
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
This page was built for publication: PP is closed under intersection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892214)
