On the probabilistic degree of OR over the reals

DOI10.4230/LIPICS.FSTTCS.2018.5MaRDI QIDQ5090936zbMATH OpenFDO

Authors Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

Publication date 21 July 2022

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

zbMATH Keywords

polynomials over realsprobabilistic polynomialsprobabilistic degreeOR polynomial

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• On the probabilistic degree of OR over the reals
• On the probabilistic degrees of symmetric Boolean functions
• On the Probabilistic Degrees of Symmetric Boolean Functions
• On the degree of Boolean functions as real polynomials
• On Improved Degree Lower Bounds for Polynomial Approximation.

Cites work

• A lower bound for radio broadcast
• Anti-concentration for polynomials of independent random variables
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Covering the cube by affine hyperplanes
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On a lemma of Littlewood and Offord
• On deterministic approximation of DNF
• On polynomial approximations to \(\mathrm{AC}^0\)
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)

Cited in

(3)

• A robust version of Hegedűs's lemma, with applications
• On the probabilistic degree of OR over the reals
• On the Probabilistic Degrees of Symmetric Boolean Functions

This page was built for publication: On the probabilistic degree of OR over the reals

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