Pages that link to "Item:Q1346615"
From MaRDI portal
The following pages link to Perceptrons, PP, and the polynomial hierarchy (Q1346615):
Displaying 32 items.
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length (Q368235) (← links)
- Improved approximation of linear threshold functions (Q371200) (← links)
- Unbounded-error quantum query complexity (Q638526) (← links)
- Complexity classes of equivalence problems revisited (Q716333) (← links)
- Perceptrons of large weight (Q734289) (← links)
- On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P (Q845727) (← links)
- A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy (Q1271610) (← links)
- Relating polynomial time to constant depth (Q1274992) (← links)
- The hardest halfspace (Q1983325) (← links)
- On separation between the degree of a Boolean function and the block sensitivity (Q2117108) (← links)
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities (Q2347795) (← links)
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) (Q2422767) (← 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)
- Degree-uniform lower bound on the weights of polynomials with given sign function (Q2510769) (← links)
- Polynomial threshold functions and Boolean threshold circuits (Q2514146) (← links)
- A note on the circuit complexity of PP (Q2576885) (← links)
- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits (Q3448791) (← links)
- Immunity and Simplicity for Exact Counting and Other Counting Classes (Q4265536) (← links)
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits (Q4554070) (← links)
- (Q4612486) (← links)
- (Q4612487) (← links)
- (Q5009530) (← links)
- Weights of exact threshold functions (Q5033984) (← links)
- Approximate Degree in Classical and Quantum Computing (Q5060675) (← links)
- A Short List of Equalities Induces Large Sign-Rank (Q5087014) (← links)
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ (Q5117375) (← links)
- (Q5140844) (← 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)
