Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

ISSN 1433-8092 | Imprint