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 is known that every Boolean function of n ... more >>>

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

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

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 different ... more >>>

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

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