Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Dispersers:
TR01-018 | 23rd February 2001
Omer Reingold, Salil Vadhan, Avi Wigderson

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

The main contribution of this work is a new type of graph product, which we call the zig-zag
product. Taking a product of a large graph with a small graph, the resulting graph inherits
(roughly) its size from the large one, its degree from the small one, and ... more >>>

TR05-061 | 15th June 2005
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

On the Error Parameter of Dispersers

Optimal dispersers have better dependence on the error than
optimal extractors. In this paper we give explicit disperser
constructions that beat the best possible extractors in some
parameters. Our constructions are not strong, but we show that
having such explicit strong constructions implies a solution
to the Ramsey graph construction ... more >>>

TR10-037 | 8th March 2010
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a
distribution $X$ on binary strings of length $n$ is a
$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$
to any string of length $n$. For every $\delta>0$ we construct the
following poly($n$)-time ... more >>>

TR11-129 | 22nd September 2011
Eli Ben-Sasson, Ariel Gabizon

Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... more >>>

TR15-170 | 26th October 2015
Alexander Golovnev, Alexander Kulikov

Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An $(n,k,s)$-quadratic disperser is a function on $n$ variables that is not constant on any subset of $\mathbb{F}_2^n$ of size at least $s$ ... more >>>

TR18-065 | 8th April 2018
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

Revisions: 1

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,
the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.
Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ... more >>>

TR18-192 | 12th November 2018
Alexander Golovnev, Alexander Kulikov

Circuit Depth Reductions

Revisions: 3

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>>

TR19-079 | 28th May 2019
Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

Average Bias and Polynomial Sources

Revisions: 2

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>

TR24-092 | 16th May 2024
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

Hilbert Functions and Low-Degree Randomness Extractors

For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ ... more >>>

ISSN 1433-8092 | Imprint