Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SYMMETRIC BOOLEAN FUNCTIONS:
Reports tagged with symmetric Boolean functions:
TR13-032 | 26th February 2013
Mark Bun, Justin Thaler

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Revisions: 2

The $\epsilon$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $\epsilon$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an ... more >>>


TR19-138 | 6th October 2019
Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

On the Probabilistic Degrees of Symmetric Boolean functions

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial $\mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>>




ISSN 1433-8092 | Imprint