Depth reduction for composites

DOI10.1137/17M1129672MaRDI QIDQ4634033zbMATH OpenOpenAlexFDO

Authors Shiteng Chen, Periklis A. Papakonstantinou

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

zbMATH Keywords

composite moduluscircuit lower boundinteractive compressiondepth-reductionWilliams' program

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Depth reduction for circuits of unbounded fan-in
• Communication complexity towards lower bounds on circuit depth
• Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
• A lower bound for depth-3 circuits with MOD m gates
• Improved Bounds for Reduction to Depth 4 and Depth 3

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 549851 (Why is no real title available?)
• A hierarchy for nondeterministic time complexity
• A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
• Bounds on an exponential sum arising in Boolean circuit complexity
• Computational Complexity
• Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
• Depth reduction for circuits of unbounded fan-in
• Estimation of certain exponential sums arising in complexity theory
• Linear Systems over Composite Moduli
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Majority is incompressible by \(\mathrm{AC}^0[p]\) circuits
• NEXP does not have non-uniform quasipolynomial-size ACC circuits of o( n) depth
• On ACC
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Threshold circuits of bounded depth

Cited in

(4)

• Satisfiability and derandomization for small polynomial threshold circuits
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• A technique for hardness amplification against AC^0
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees

This page was built for publication: Depth reduction for composites

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634033)