The following pages link to PP is closed under intersection (Q1892214):
Displaying 50 items.
- Zero-information protocols and unambiguity in Arthur-Merlin communication (Q343848) (← links)
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length (Q368235) (← links)
- Exponential lower bound for bounded depth circuits with few threshold gates (Q413295) (← links)
- On the complexity of propositional and relational credal networks (Q518627) (← links)
- Learning intersections and thresholds of halfspaces (Q598257) (← links)
- Arithmetization: A new method in structural complexity theory (Q685721) (← links)
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) (Q764326) (← links)
- Unconditional lower bounds for learning intersections of halfspaces (Q1009217) (← links)
- A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy (Q1271610) (← links)
- On closure properties of GapP (Q1337146) (← links)
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one (Q1346613) (← links)
- Complex polynomials and circuit lower bounds for modular counting (Q1346614) (← links)
- Perceptrons, PP, and the polynomial hierarchy (Q1346615) (← links)
- On ACC (Q1346616) (← links)
- Circuits over PP and PL (Q1567408) (← links)
- Complexity results for structure-based causality. (Q1852862) (← links)
- The hardest halfspace (Q1983325) (← links)
- A structured view on weighted counting with relations to counting, quantum computation and applications (Q2216125) (← links)
- Open-world probabilistic databases: semantics, algorithms, complexity (Q2238646) (← links)
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression (Q2316930) (← links)
- The Bayesian ontology language \(\mathcal {BEL}\) (Q2362495) (← links)
- Probabilistic logic with independence (Q2379311) (← links)
- On PAC learning algorithms for rich Boolean function classes (Q2382283) (← links)
- The effect of combination functions on the complexity of relational Bayesian networks (Q2409113) (← links)
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) (Q2422767) (← links)
- Learning intersections of halfspaces with a margin (Q2462501) (← links)
- Extremal properties of polynomial threshold functions (Q2475403) (← links)
- LWPP and WPP are not uniformly gap-definable (Q2495405) (← links)
- Error-bounded probabilistic computations between MA and AM (Q2507698) (← links)
- Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms (Q2701071) (← links)
- A linear-optical proof that the permanent is # <b>P</b> -hard (Q2901811) (← links)
- On the power of deterministic reductions to C=P (Q4032933) (← links)
- Generalized theorems on relationships among reducibility notions to certain complexity classes (Q4298368) (← links)
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits (Q4554070) (← links)
- The Power of Asymmetry in Constant-Depth Circuits (Q4562278) (← links)
- A lower bound for monotone perceptrons (Q4841765) (← links)
- Relationships among $PL$, $\#L$, and the determinant (Q4889814) (← links)
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ (Q4957911) (← links)
- (Q5009530) (← links)
- Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors (Q5025767) (← links)
- Approximate Degree in Classical and Quantum Computing (Q5060675) (← links)
- Fooling Polytopes (Q5066946) (← links)
- (Q5091179) (← links)
- Algorithmic Polynomials (Q5138783) (← links)
- A relationship between difference hierarchies and relativized polynomial hierarchies (Q5289273) (← links)
- Quantum computing, postselection, and probabilistic polynomial-time (Q5428317) (← links)
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials (Q5891428) (← links)
- New degree bounds for polynomial threshold functions (Q5894427) (← links)
- Complexity limitations on one-turn quantum refereed games (Q6038714) (← links)
- Commuting quantum circuits and complexity of Ising partition functions (Q6100591) (← links)
