Under the auspices of the Computational Complexity Foundation (CCF)

TR07-056 | 10th July 2007
Zeev Dvir, Ariel Gabizon, Avi Wigderson

#### Extractors and Rank Extractors for Polynomial Sources

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

TR16-171 | 3rd November 2016
Daniel Minahan, Ilya Volkovich

#### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the
operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain ... more >>>

TR19-169 | 21st November 2019
Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

#### On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

Revisions: 1

The Exponential-Time Hypothesis ($ETH$) is a strengthening of the $\mathcal{P} \neq \mathcal{NP}$ conjecture, stating that $3\text{-}SAT$ on $n$ variables cannot be solved in time $2^{\epsilon\cdot n}$, for some $\epsilon>0$. In recent years, analogous hypotheses that are exponentially-strong'' forms of other classical complexity conjectures (such as $\mathcal{NP}\not\subseteq\mathcal{BPP}$ or $co\text{-}\mathcal{NP}\not\subseteq \mathcal{NP}$) have ... more >>>

TR20-098 | 4th July 2020
Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

#### Impossibility of Derandomizing the Isolation Lemma for all Families

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

ISSN 1433-8092 | Imprint