Circuit complexity before the dawn of the new millennium
From MaRDI portal
Publication:6567750
DOI10.1007/3-540-62034-6_33zbMATH Open1541.68135MaRDI QIDQ6567750
Publication date: 5 July 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
- A note on the power of majority gates and modular gates
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- \(NC^ 1\): The automata-theoretic viewpoint
- On the power of small-depth threshold circuits
- Non-uniform automata over groups
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Relativized circuit complexity
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Parallel computation with threshold functions
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- On the relative complexity of some languages in \(NC^ 1\)
- Rudimentary reductions revisited
- Almost everywhere high nonuniform complexity
- On read-once threshold formulae and their randomized decision tree complexity
- Majority gates vs. general weighted threshold gates
- Space-bounded reducibility among combinatorial problems
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Exponential size lower bounds for some depth three circuits
- The expressive power of voting polynomials
- Depth reduction for circuits of unbounded fan-in
- Hardness vs randomness
- \(\Sigma\Pi\Sigma\) threshold formulas
- On the degree of Boolean functions as real polynomials
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Complex polynomials and circuit lower bounds for modular counting
- Representing Boolean functions as polynomials modulo composite numbers
- Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
- The complexity of iterated multiplication
- A note on a theorem of Barrington, Straubing and Thérien
- Superlinear lower bounds for bounded-width branching programs
- The power of the middle bit of a \(\#\)P function
- Vector analysis of threshold functions
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
- \(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
- A circuit-based proof of Toda's theorem
- Circuit lower bounds à la Kolmogorov
- A note on some languages in uniform \(ACC^ 0\)
- On uniformity within \(NC^ 1\)
- On the computational power of depth 2 circuits with threshold and modulo gates
- Constant depth circuits, Fourier transform, and learnability
- Parity, circuits, and the polynomial-time hierarchy
- Circuit-size lower bounds and non-reducibility to sparse sets
- Constant Depth Reducibility
- PP is as Hard as the Polynomial-Time Hierarchy
- On relativized exponential and probabilistic complexity classes
- Languages that Capture Complexity Classes
- Classifying the computational complexity of problems
- Finite monoids and the fine structure of NC 1
- Alternation
- Expressibility and Parallel Complexity
- A Uniform Circuit Lower Bound for the Permanent
- Lower bounds for depth-three circuits with equals and mod-gates
- Lower Bounds on Representing Boolean Functions as Polynomials in $Z_m $
- On small depth threshold circuits
- Simulating threshold circuits by majority circuits
- Natural proofs
- A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
- A note on the simulation of exponential threshold weights
This page was built for publication: Circuit complexity before the dawn of the new millennium
