Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with AND-OR tree:
TR13-023 | 6th February 2013
Alexander A. Sherstov

Approximating the AND-OR Tree

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial
that approximates $f$ within $1/3$ at every point. We prove that the function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,
known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight
and closes a ... more >>>

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 >>>

TR13-151 | 7th November 2013
Mark Bun, Justin Thaler

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit ... more >>>

TR22-087 | 8th June 2022
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Depth-$d$ Threshold Circuits vs. Depth-$(d + 1)$ AND-OR Trees

Revisions: 1

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed ... more >>>

ISSN 1433-8092 | Imprint