On the probabilistic degree of OR over the reals

DOI10.4230/LIPICS.FSTTCS.2018.5MaRDI QIDQ5090936FDOQ5090936

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

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.

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)

Cites Work

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