scientific article; zbMATH DE number 7089064

zbMath1437.68061arXiv1806.04831MaRDI QIDQ5227514

Benjamin Rossman

Publication date: 6 August 2019

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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

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

This page was built for publication: