Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AC0:
Reports tagged with AC0:
TR09-104 | 26th October 2009
Scott Aaronson

#### BQP and the Polynomial Hierarchy

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

TR10-109 | 11th July 2010
Scott Aaronson

#### A Counterexample to the Generalized Linial-Nisan Conjecture

In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that "almost k-wise independent" distributions are indistinguishable from the uniform distribution by constant-depth ... more >>>

TR11-095 | 22nd June 2011
Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

#### Low uniform versions of NC1

Revisions: 1

In the setting known as DLOGTIME-uniformity,
the fundamental complexity classes
$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several
robust characterizations.
In this paper we refine uniformity further and examine the impact
of these refinements on $NC^1$ and its subclasses.
When applied to the logarithmic circuit depth characterization of $NC^1$,
some refinements leave ... more >>>

TR12-116 | 13th September 2012
Luca Trevisan

#### A Derandomized Switching Lemma and an Improved Derandomization of AC0

Revisions: 1

We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$.
A seed length of ... more >>>

TR13-152 | 7th November 2013
Oded Goldreich, Avi Wigderson

#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

{\em Does derandomization of probabilistic algorithms become easier when the number of bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ... more >>>

TR14-177 | 14th December 2014
Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

#### Visibly Counter Languages and Constant Depth Circuits

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].

more >>>

TR15-003 | 3rd January 2015
Oded Goldreich, Emanuele Viola, Avi Wigderson

#### On Randomness Extraction in AC0

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>> TR15-189 | 25th November 2015 Shay Moran, Cyrus Rashtchian #### Shattered Sets and the Hilbert Function Revisions: 1 We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>> TR16-018 | 3rd February 2016 Kuan Cheng, Xin Li #### Randomness Extraction in$AC^0$and with Small Locality Revisions: 7 We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by$AC^0$circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that ... more >>> TR16-180 | 15th November 2016 Eshan Chattopadhyay, Xin Li #### Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to many elegant constructions and applications in cryptography. However, most works so far only ... more >>> TR17-144 | 27th September 2017 Moritz Müller, Ján Pich #### Feasibly constructive proofs of succinct weak circuit lower bounds We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length$n$. In 1995 Razborov showed that many can be proved in Cook’s theory$PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small$n$of ... more >>> TR18-015 | 25th January 2018 Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett #### Pseudorandom Generators from Polarizing Random Walks Revisions: 1 , Comments: 1 We propose a new framework for constructing pseudorandom generators for$n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in$[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in$[-1,1]^n\$ that ... more >>>

ISSN 1433-8092 | Imprint