Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > AFFINE DISPERSERS:
Reports tagged with affine dispersers:
TR11-026 | 27th February 2011
Evgeny Demenkov, Alexander Kulikov

An Elementary Proof of $3n-o(n)$ Lower Bound on the Circuit Complexity of Affine Dispersers

A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main ... more >>>


TR13-145 | 20th October 2013
Gil Cohen, Avishay Tal

Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. ... more >>>


TR14-099 | 7th August 2014
Gil Cohen, Igor Shinkar

The Complexity of DNF of Parities

We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as ... more >>>




ISSN 1433-8092 | Imprint