On the Probabilistic Degrees of Symmetric Boolean Functions

DOI10.1137/19M1294162MaRDI QIDQ4959660FDOQ4959660

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

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

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)

Cites Work

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

Cited In (11)

• Title not available (Why is that?)
• A robust version of Hegedűs's lemma, with applications
• Symmetrization of probability measures, pushforward of order 2 and the Boolean convolution
• Title not available (Why is that?)
• A class of Boolean functions homogeneously distributed over balls with degree 1
• Probabilities of 2-Xor Functions
• Boolean degree 1 functions on some classical association schemes
• Oblivious bounds on the probability of boolean functions
• On the probabilistic degree of OR over the reals
• On the minimal Fourier degree of symmetric Boolean functions
• 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)