Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with symmetric functions:
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 >>>

TR98-036 | 11th June 1998
Vince Grolmusz, Gábor Tardos

Lower Bounds for (MOD p -- MOD m) Circuits

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

TR05-049 | 1st April 2005
Joan Boyar, rene peralta

The Exact Multiplicative Complexity of the Hamming Weight Function

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

TR07-100 | 25th September 2007
Alexander A. Sherstov

The Pattern Matrix Method for Lower Bounds on Quantum Communication

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

TR07-135 | 26th December 2007
Paul Valiant, Paul Valiant

Testing Symmetric Properties of Distributions

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

TR10-039 | 10th March 2010
Gil Cohen, Amir Shpilka

On the degree of symmetric functions on the Boolean cube

Comments: 1

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

ISSN 1433-8092 | Imprint