Zeev Dvir, Ariel Gabizon, Avi Wigderson

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

Daniel Minahan, Ilya Volkovich

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

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

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