Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > AC^0:
Reports tagged with AC^0:
TR97-044 | 26th September 1997
David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

Searching constant width mazes captures the AC^0 hierarchy


We show that searching a width k maze is complete for \Pi_k, i.e., for
the k'th level of the AC^0 hierarchy. Equivalently, st-connectivity
for width k grid graphs is complete for \Pi_k. As an application,
we show that there is a data structure solving dynamic st-connectivity
for constant ... more >>>


TR11-152 | 12th November 2011
Emanuele Viola

The communication complexity of addition

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>


TR12-063 | 17th May 2012
Raghav Kulkarni, Miklos Santha

Query complexity of matroids

Let $\mathcal{M}$ be a bridgeless matroid on ground set $\{1,\ldots, n\}$ and $f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$ be the indicator function of its independent sets. A folklore fact is that $f_\mathcal{M}$ is ``evasive," i.e., $D(f_\mathcal{M}) = n$ where $D(f)$ denotes the deterministic decision tree complexity of $f.$ Here we prove ... more >>>


TR19-003 | 2nd January 2019
Alexander A. Sherstov, Pei Wu

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>


TR22-123 | 4th September 2022
Alexander A. Sherstov

The Approximate Degree of DNF and CNF Formulas

The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ essentially matching the trivial upper bound of $n.$ This ... more >>>


TR23-176 | 15th November 2023
William Hoza

A Technique for Hardness Amplification Against $\mathrm{AC}^0$

Revisions: 2

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $k = 1$ is resolved by HÃ¥stad, Rossman, ... more >>>




ISSN 1433-8092 | Imprint