Martin Dietzfelbinger, Miroslaw Kutylowski, RĂ¼diger Reischuk

It was shown some years ago that the computation time for many important

Boolean functions of n arguments on concurrent-read exclusive-write

parallel random-access machines

(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.

On the other hand, it ...
more >>>

Cristopher Moore

We propose definitions of $\QAC^0$, the quantum analog of the

classical class $\AC^0$ of constant-depth circuits with AND and OR

gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class

$\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is

possible to make a `cat' state on ...
more >>>

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Vitaly Feldman

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over $\{0,1\}^n$. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem ... more >>>

Arkadev Chattopadhyay, Rahul Santhanam

We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class $\C$, and correlation with

circuits in $\C$. We use this connection to prove the first lower bounds

on general probabilistic multi-round instance compression. We show that there

is no

probabilistic multi-round ...
more >>>

Eric Blais, Li-Yang Tan

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function.

In the first direction, our main positive results are the first non-trivial universal upper bounds on ...
more >>>

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

Nikhil Balaji, Andreas Krebs, Nutan Limaye

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

Nader Bshouty

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.

More specifically, let $\gamma:{\mathbb R}^+\to ... more >>>