Upper and lower bounds for some depth-3 circuit classes
From MaRDI portal
Publication:1377575
DOI10.1007/BF01294257zbMATH Open0890.68063MaRDI QIDQ1377575FDOQ1377575
Authors: Richard Beigel, Alexis Maciel 
Publication date: 6 July 1998
Published in: Computational Complexity (Search for Journal in Brave)
Recommendations
- Top-down lower bounds for depth-three circuits
- A lower bound for depth-3 circuits with MOD \(m\) gates
- Exponential size lower bounds for some depth three circuits
- Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
- Lower bounds for depth-three circuits with equals and Mod-gates
- Approximate degree and the complexity of depth three circuits
- Exponential lower bounds for depth three Boolean circuits
- Multi-\(k\)-ic depth three circuit lower bound
- Multi-\(k\)-ic depth three circuit lower bound
- scientific article; zbMATH DE number 1559525
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Representing Boolean functions as polynomials modulo composite numbers
- A note on a theorem of Barrington, Straubing and Thérien
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Parity, circuits, and the polynomial-time hierarchy
- On the power of small-depth threshold circuits
- A guided tour of Chernoff bounds
- On ACC
- Threshold circuits of bounded depth
- Non-uniform automata over groups
- On the computational power of depth-2 circuits with threshold and modulo gates
- Threshold circuits of small majority-depth
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Depth reduction for circuits of unbounded fan-in
- A note on the power of majority gates and modular gates
- A weight-size trade-off for circuits with MOD \(m\) gates
- An oracle separating \(\oplus P\) from \(PP^{PH}\)
- Some notes on threshold circuits, and multiplication in depth 4
- Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
Cited In (17)
- Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
- Approximate degree and the complexity of depth three circuits
- On the correlation between parity and modular polynomials
- Exponential lower bound for bounded depth circuits with few threshold gates
- Powering requires threshold depth 3
- Title not available (Why is that?)
- A lower bound for depth-3 circuits with MOD \(m\) gates
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The correlation between parity and quadratic polynomials mod \(3\)
- Exponential size lower bounds for some depth three circuits
- Top-down lower bounds for depth-three circuits
- Size and Energy of Threshold Circuits Computing Mod Functions
- Title not available (Why is that?)
- On small depth threshold circuits
- A nonuniform circuit class with multilayer of threshold gates having super quasi polynomial size lower bounds against NEXP
- On \(\mathrm{TC}^{0}\) lower bounds for the permanent
This page was built for publication: Upper and lower bounds for some depth-3 circuit classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377575)
