All reports by Author Omid Etesami:

__
TR17-136
| 10th September 2017
__

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo#### Complete Classification of Generalized Santha-Vazirani Sources

__
TR14-179
| 20th December 2014
__

Salman Beigi, Omid Etesami, Amin Gohari#### Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources

__
TR14-100
| 4th August 2014
__

Salman Beigi, Omid Etesami, Amin Gohari#### The Value of Help Bits in Randomized and Average-Case Complexity

__
TR12-175
| 13th December 2012
__

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan#### On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

__
TR09-141
| 19th December 2009
__

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani#### Improved Pseudorandom Generators for Depth 2 Circuits

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

Salman Beigi, Omid Etesami, Amin Gohari

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible.

In this paper, we study the generalization of SV ...
more >>>

Salman Beigi, Omid Etesami, Amin Gohari

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity.

Amir, Beigel, and Gasarch ... more >>>

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>>

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

We prove the existence of a $poly(n,m)$-time computable

pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables

and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.

Previously, the best pseudorandom generator for depth-2 circuits had seed

length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It ... more >>>