Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with parity:
TR95-004 | 1st January 1995
Martin Dietzfelbinger, Miroslaw Kutylowski, RĂ¼diger Reischuk

Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

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

TR99-032 | 7th July 1999
Cristopher Moore

Quantum Circuits: Fanout, Parity, and Counting

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

TR06-059 | 3rd May 2006
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

New Results for Learning Noisy Parities and Halfspaces

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

TR06-066 | 5th May 2006
Vitaly Feldman

On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions

Revisions: 1

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

TR12-108 | 4th September 2012
Arkadev Chattopadhyay, Rahul Santhanam

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits

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

TR13-051 | 2nd April 2013
Eric Blais, Li-Yang Tan

Approximating Boolean functions with depth-2 circuits

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

TR13-164 | 28th November 2013
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

Weak Parity

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

TR14-183 | 25th December 2014
Nikhil Balaji, Andreas Krebs, Nutan Limaye

Skew Circuits of Small Width

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

ISSN 1433-8092 | Imprint