Pages that link to "Item:Q1330793"
From MaRDI portal
The following pages link to The expressive power of voting polynomials (Q1330793):
Displaying 42 items.
- Sign-representation of Boolean functions using a small number of monomials (Q280399) (← 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)
- The communication complexity of addition (Q519955) (← links)
- Learning intersections and thresholds of halfspaces (Q598257) (← links)
- Unbounded-error quantum query complexity (Q638526) (← links)
- Powering requires threshold depth 3 (Q845974) (← links)
- Problems and results in extremal combinatorics. II (Q941386) (← links)
- Unconditional lower bounds for learning intersections of halfspaces (Q1009217) (← links)
- On the computational power of depth-2 circuits with threshold and modulo gates (Q1269909) (← links)
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one (Q1346613) (← links)
- Perceptrons, PP, and the polynomial hierarchy (Q1346615) (← links)
- On the power of circuits with gates of low \(L_{1}\) norms. (Q1389652) (← links)
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) (Q1887713) (← links)
- The hardest halfspace (Q1983325) (← links)
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression (Q2316930) (← links)
- The unbounded-error communication complexity of symmetric functions (Q2428632) (← links)
- Extremal properties of polynomial threshold functions (Q2475403) (← links)
- LWPP and WPP are not uniformly gap-definable (Q2495405) (← links)
- Learning $$AC^0$$ Under k-Dependent Distributions (Q2988821) (← links)
- Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates (Q3088133) (← links)
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits (Q4554070) (← links)
- The Power of Asymmetry in Constant-Depth Circuits (Q4562278) (← links)
- Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits (Q4568115) (← links)
- Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression (Q4612476) (← links)
- New algorithms and lower bounds for circuits with linear threshold gates (Q4612481) (← links)
- A lower bound for monotone perceptrons (Q4841765) (← links)
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ (Q4957911) (← links)
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem (Q4957916) (← links)
- A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma (Q4993326) (← links)
- Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors (Q5025767) (← links)
- Approximate Degree in Classical and Quantum Computing (Q5060675) (← links)
- Parity helps to compute majority (Q5091774) (← links)
- Algorithmic Polynomials (Q5138783) (← links)
- On neuronal capacity (Q5854113) (← links)
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials (Q5891428) (← links)
- New degree bounds for polynomial threshold functions (Q5894427) (← links)
- Natural proofs (Q5906823) (← links)
- On the modulo degree complexity of Boolean functions (Q5918108) (← links)
- An exact characterization of symmetric functions in \(qAC^{0}[2]\) (Q5941440) (← links)
- A robust version of Hegedűs's lemma, with applications (Q6566590) (← links)
- Circuit complexity before the dawn of the new millennium (Q6567750) (← links)
