On the Probabilistic Degrees of Symmetric Boolean Functions

DOI10.1137/19M1294162MaRDI QIDQ4959660zbMATH OpenFDO

Authors Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

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

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

Recommendations

• On the probabilistic degrees of symmetric Boolean functions
• On the probabilistic degree of OR over the reals
• On the probabilistic degree of OR over the reals
• On the degree of Boolean functions as real polynomials
• On the minimal Fourier degree of symmetric Boolean functions

Cites work

• scientific article; zbMATH DE number 3682004 (Why is no real title available?)
• scientific article; zbMATH DE number 512859 (Why is no real title available?)
• scientific article; zbMATH DE number 7561310 (Why is no real title available?)
• scientific article; zbMATH DE number 7650325 (Why is no real title available?)
• An exact characterization of symmetric functions in \(qAC^{0}[2]\)
• Analysis of Boolean Functions
• Anti-concentration for polynomials of independent random variables
• Approximate inclusion-exclusion
• Bounded-depth, polynomial-size circuits for symmetric functions
• Concentration of Measure for the Analysis of Randomized Algorithms
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• The complexity of symmetric functions in bounded-depth circuits
• The polynomial method in circuit complexity applied to algorithm design (invited talk)

Cited in

(11)

• scientific article; zbMATH DE number 7267634 (Why is no real title available?)
• A robust version of Hegedűs's lemma, with applications
• Symmetrization of probability measures, pushforward of order 2 and the Boolean convolution
• A class of Boolean functions homogeneously distributed over balls with degree 1
• scientific article; zbMATH DE number 1285633 (Why is no real title available?)
• Boolean degree 1 functions on some classical association schemes
• Probabilities of 2-Xor Functions
• Oblivious bounds on the probability of boolean functions
• On the minimal Fourier degree of symmetric Boolean functions
• On the probabilistic degree of OR over the reals
• The Degree of Balanced Elementary Symmetric Boolean Functions of <formula formulatype="inline"> <tex Notation="TeX">${{\bf 4k}+{\bf 3}}$</tex> </formula> Variables

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959660)