Threshold circuits of bounded depth
From MaRDI portal
Publication:2366275
DOI10.1016/0022-0000(93)90001-DzbMath0801.68052MaRDI QIDQ2366275
György Turán, Pavel Pudlák, Andras Hajnal, Wolfgang Maass, Mario Szegedy
Publication date: 29 June 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items
Affine projections of symmetric polynomials., Weights of exact threshold functions, Expander-based cryptography meets natural proofs, A lower bound for depth-3 circuits with MOD \(m\) gates, Local Reductions, On small depth threshold circuits, Powering requires threshold depth 3, Local reduction, Circuit lower bounds from learning-theoretic approaches, Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes, Faster All-Pairs Shortest Paths via Circuit Complexity, Iterated multiplication in \(VTC^0\), General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, 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, Upper and lower bounds for some depth-3 circuit classes, \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product, A Short List of Equalities Induces Large Sign-Rank, Decomposition of threshold functions into bounded fan-in threshold functions, Neural networks and complexity theory, Parallel complexity of iterated morphisms and the arithmetic of small numbers, On the power of circuits with gates of low \(L_{1}\) norms., Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts, Half-Spaces with Influential Variable, Exponential lower bound for bounded depth circuits with few threshold gates, The unbounded-error communication complexity of symmetric functions, Unnamed Item, Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\), Complexity of hard-core set proofs, Learning $$AC^0$$ Under k-Dependent Distributions, New degree bounds for polynomial threshold functions, New algorithms and lower bounds for circuits with linear threshold gates, Depth Reduction for Composites, String Matching: Communication, Circuits, and Learning., On the computation of Boolean functions by analog circuits of bounded fan-in, Learning unions of \(\omega(1)\)-dimensional rectangles, Size, Depth and Energy of Threshold Circuits Computing Parity Function., Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity, Root finding with threshold circuits, Uniqueness of optimal mod 3 polynomials for parity, On the correlation between parity and modular polynomials, Threshold circuit lower bounds on cryptographic functions, Estimation of certain exponential sums arising in complexity theory, Testing (Subclasses of) Halfspaces, On XOR lemmas for the weight of polynomial threshold functions, Degree-uniform lower bound on the weights of polynomials with given sign function, Polynomial threshold functions and Boolean threshold circuits, Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size, Quantum matchgate computations and linear threshold gates, On the relationship between energy complexity and other Boolean function measures, Unnamed Item, Expander-Based Cryptography Meets Natural Proofs, Threshold circuits of small majority-depth, Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Can large fanin circuits perform reliable computations in the presence of faults?, On the Computational Power of Threshold Circuits with Sparse Activity, Unnamed Item, From Circuit Complexity to Faster All-Pairs Shortest Paths, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\), Efficient threshold circuits for power series, Superlinear Integrality Gaps for the Minimum Majority Problem
Cites Work
- A measure in which Boolean negation is exponentially powerful
- The critical complexity of graph properties
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Bounded-depth, polynomial-size circuits for symmetric functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Constant Depth Reducibility
- A logic for constant-depth circuits
- Log Depth Circuits for Division and Related Problems
- A complexity theory based on Boolean algebra
- The Depth of All Boolean Functions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
