On the probabilistic degree of OR over the reals

DOI10.1002/rsa.20991zbMath1524.68132arXiv1812.01982MaRDI QIDQ6074648

Srikanth Srinivasan, Tulasimohan Molli, Prahladh Harsha, Siddharth Bhandari

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

polynomial representationsprobabilistic polynomialspolynomials over realsprobabilistic degreeOR polynomial

Mathematics Subject Classification ID

Boolean functions (06E30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

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

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