Under the auspices of the Computational Complexity Foundation (CCF)

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

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

ISSN 1433-8092 | Imprint