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

Vince Grolmusz, Gábor Tardos

Modular gates are known to be immune for the random

restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and

Hastad. We demonstrate here a random clustering technique which

overcomes this difficulty and is capable to prove generalizations of

several known modular circuit lower bounds of Barrington, Straubing,

Therien; Krause ...
more >>>

Joan Boyar, rene peralta

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>>

Alexander A. Sherstov

In a breakthrough result, Razborov (2003) gave optimal

lower bounds on the communication complexity of every function f

of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in

the bounded-error quantum model with and without prior entanglement.

This was proved by the _multidimensional_ discrepancy method. We

give an entirely ...
more >>>

Paul Valiant, Paul Valiant

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and

general enough that ``a property is testable if and only if the

Canonical Tester tests it''. We construct a Canonical Tester

for the class of symmetric properties of one or two

more >>>

Gil Cohen, Amir Shpilka

In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in

\mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as $c < n$ it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$ when $c=n$, our

result shows a surprising ...
more >>>