Subspace-invariant AC^0 formulas

zbMATH Open1437.68061arXiv1806.04831MaRDI QIDQ5227514FDOQ5227514

Authors: Benjamin Rossman 

Publication date: 6 August 2019

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

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

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)

Cites Work

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

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)