Subspace-invariant AC^0 formulas

DOI10.4230/LIPICS.ICALP.2017.93MaRDI QIDQ5111425zbMATHFDO

Authors Benjamin Rossman

Publication date 27 May 2020

zbMATH Keywords

lower boundsparitysize-depth tradeoffsymmetry in computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• Subspace-invariant \(\mathrm{AC}^0\) formulas
• scientific article; zbMATH DE number 4209604
• scientific article; zbMATH DE number 176874
• The effect of random restrictions on formula size
• Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)

Cited in

(3)

• Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
• Subspace-invariant \(\mathrm{AC}^0\) formulas
• Smallest formulas for the parity of \(2^k\) variables are essentially unique

This page was built for publication: Subspace-invariant \(\mathrm{AC}^0\) formulas

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