Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

TR21-023 | 20th February 2021
Jiatu Li, Tianqi Yang

$3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>

ISSN 1433-8092 | Imprint