R. Beigel, W. Hurwood, N. Kahale

We consider the fault diagnosis problem: how to use parallel testing

rounds to identify which processors in a set are faulty. We prove

that 4 rounds suffice when 3% or less of the processors are faulty,

and 4 rounds are necessary when any nontrivial constant fraction of

the processors are ...
more >>>

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

We study a model of graph related formulae that we call

the \emph{Constraint-Graph model}. A

constraint-graph is a labeled multi-graph (a graph where loops

and parallel edges are allowed), where each edge $e$ is labeled

by a distinct Boolean variable and every vertex is

associate with a Boolean function over ...
more >>>

Shachar Lovett

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

Martin Schwarz

We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce ... more >>>