Subspace-invariant AC^0 formulas

DOI10.4230/LIPICS.ICALP.2017.93zbMATH Open1442.68054MaRDI QIDQ5111425FDOQ5111425

Authors: Benjamin Rossman 

Publication date: 27 May 2020

Recommendations

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

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)

Cited In (2)

• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• Smallest Formulas for 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)