Polynomial threshold functions and Boolean threshold circuits
From MaRDI portal
Publication:2514146
DOI10.1016/j.ic.2014.09.008zbMath1312.68089OpenAlexW2084194126MaRDI QIDQ2514146
Vladimir V. Podolskii, Kristoffer Arnsfelt Hansen
Publication date: 30 January 2015
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2014.09.008
Related Items
Weights of exact threshold functions ⋮ A characterization of 2-threshold functions via pairs of prime segments ⋮ Trading transforms of non-weighted simple games and integer weights of weighted simple games ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Nearest neighbor representations of Boolean functions ⋮ Differentiable learning of matricized DNFs and its application to Boolean networks ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Asymptotics of the number of 2-threshold functions ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of a threshold gate at the top
- Probabilistic communication complexity
- Learning intersections and thresholds of halfspaces
- On the power of small-depth threshold circuits
- Polynomials that sign represent parity and Descartes' rule of signs
- Majority gates vs. general weighted threshold gates
- On the computational power of depth-2 circuits with threshold and modulo gates
- Computing Boolean functions by polynomials and threshold circuits
- Perceptrons, PP, and the polynomial hierarchy
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Threshold circuits of bounded depth
- Theory of majority decision elements
- Polynomial Threshold Functions and Boolean Threshold Circuits
- The Sign-Rank of AC$^0$
- Max-linear Systems: Theory and Algorithms
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- A Bound on Solutions of Linear Integer Equalities and Inequalities
- Mathematical Foundations of Computer Science 2004
