Depth Reduction for Composites
From MaRDI portal
Publication:4634033
DOI10.1137/17M1129672zbMath1421.68054OpenAlexW2943630340MaRDI QIDQ4634033
Periklis A. Papakonstantinou, Shiteng Chen
Publication date: 7 May 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1129672
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Estimation of certain exponential sums arising in complexity theory
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Depth reduction for circuits of unbounded fan-in
- On ACC
- A hierarchy for nondeterministic time complexity
- Threshold circuits of bounded depth
- A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
- Bounds on an exponential sum arising in Boolean circuit complexity
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
- 30th Conference on Computational Complexity (CCC 2015)
- New algorithms and lower bounds for circuits with linear threshold gates
- Linear Systems over Composite Moduli
- Computational Complexity
This page was built for publication: Depth Reduction for Composites
