Subspace-invariant AC^0 formulas

MaRDI QIDQ5227514zbMATH OpenFDO

Authors Benjamin Rossman

Publication date 6 August 2019

Full work available at URL https://arxiv.org/abs/1806.04831

zbMATH Keywords

circuit complexityparityformula size\(\mathrm{AC}^0\)symmetric 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
• Separation of \(\mathrm{AC}^0[\oplus]\) formulas and circuits
• The average sensitivity of bounded-depth formulas
• scientific article; zbMATH DE number 7166711
• The effect of random restrictions on formula size

Cites work

• scientific article; zbMATH DE number 4068311 (Why is no real title available?)
• scientific article; zbMATH DE number 1086678 (Why is no real title available?)
• Choiceless computation and symmetry
• Choiceless polynomial time
• Complexity of the realization of a linear function in the class of -circuits
• Definability by constant-depth polynomial-size circuits
• Generating hard tautologies using predicate logic and the symmetric group
• On Symmetric and Choiceless Computation
• On polynomial time computation over unordered structures
• Poly-logarithmic Frege depth lower bounds via an expander switching lemma
• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• The independence of the modulo \(p\) counting principles
• The isoperimetric number of random regular graphs

Cited in

(1)

• Subspace-invariant \(\mathrm{AC}^0\) formulas

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 Q5227514)