The expressive power of voting polynomials
From MaRDI portal
Publication:1330793
DOI10.1007/BF01215346zbMath0845.68045OpenAlexW2611287588MaRDI QIDQ1330793
James Aspnes, Steven Rudich, Merrick L. Furst, Richard Beigel
Publication date: 11 August 1994
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01215346
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (40)
Sign-representation of Boolean functions using a small number of monomials ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ Powering requires threshold depth 3 ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ 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 ⋮ A lower bound for monotone perceptrons ⋮ On the power of circuits with gates of low \(L_{1}\) norms. ⋮ Exponential lower bound for bounded depth circuits with few threshold gates ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Unbounded-error quantum query complexity ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ Algorithmic Polynomials ⋮ New degree bounds for polynomial threshold functions ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Problems and results in extremal combinatorics. II ⋮ The hardest halfspace ⋮ The communication complexity of addition ⋮ Extremal properties of polynomial threshold functions ⋮ Natural proofs ⋮ An exact characterization of symmetric functions in \(qAC^{0}[2\)] ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ On the modulo degree complexity of Boolean functions ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ On the computational power of depth-2 circuits with threshold and modulo gates ⋮ Parity helps to compute majority ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ On neuronal capacity ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
Cites Work
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Relativized counting classes: Relations among thresholds, parity, and mods
- Parity, circuits, and the polynomial-time hierarchy
- Harmonic Analysis of Polynomial Threshold Functions
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Unnamed Item
- Unnamed Item
This page was built for publication: The expressive power of voting polynomials
