On the Probabilistic Degrees of Symmetric Boolean Functions

DOI10.1137/19M1294162MaRDI QIDQ4959660

S. Venkitesh, Utkarsh Tripathi, Srikanth Srinivasan

Publication date: 17 September 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitysymmetric Boolean functionprobabilistic degree

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Bounded-depth, polynomial-size circuits for symmetric functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• The complexity of symmetric functions in bounded-depth circuits
• Approximate inclusion-exclusion
• Anti-concentration for polynomials of independent random variables
• Polylogarithmic independence fools AC ⁰ circuits
• Analysis of Boolean Functions
• Concentration of Measure for the Analysis of Randomized Algorithms
• An exact characterization of symmetric functions in \(qAC^{0}[2\)]
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Probabilistic Degrees of Symmetric Boolean Functions