Criticality of regular formulas

DOI10.4230/LIPIcs.CCC.2019.1OpenAlexW2965474919MaRDI QIDQ5091751

Benjamin Rossman

Publication date: 27 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2019.1

zbMATH Keywords

criticalityformulasAC\(^0\) circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Paradigms for Unconditional Pseudorandom Generators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• The average sensitivity of bounded-depth formulas
• On the Average Sensitivity and Density of k-CNF Formulas
• A Complete Proof of Universal Inequalities for the Distribution Function of the Binomial Law
• Constant depth circuits, Fourier transform, and learnability
• Variable Influences in Conjunctive Normal Forms
• Approximation of biased Boolean functions of small total influence by DNFs
• On the Correlation of Parity and Small-Depth Circuits
• Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity

This page was built for publication: Criticality of regular formulas