Lower bounds for depth-three circuits with equals and Mod-gates

DOI10.1007/3-540-59042-0_63MaRDI QIDQ4596611zbMATH OpenOpenAlexFDO

Authors Frederic Green

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_63

Mathematics Subject Classification ID

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

Recommendations

• A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
• Exponential size lower bounds for some depth three circuits
• A lower bound for depth-3 circuits with MOD m gates
• On the computational power of depth 2 circuits with threshold and modulo gates
• On the computational power of depth-2 circuits with threshold and modulo gates

Cited in

(8)

• Complex polynomials and circuit lower bounds for modular counting
• A note on a theorem of Barrington, Straubing and Thérien
• Upper and lower bounds for some depth-3 circuit classes
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
• A lower bound for depth-3 circuits with MOD m gates
• Lower bounds for modular counting by circuits with modular gates
• Circuit complexity before the dawn of the new millennium
• On the correlation between parity and modular polynomials

This page was built for publication: Lower bounds for depth-three circuits with equals and Mod-gates

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