All reports by Author Salman Beigi:

__
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

__
TR08-051
| 4th April 2008
__

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor#### The Power of Unentanglement

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

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The class QMA(k), introduced by Kobayashi et al., consists

of all languages that can be verified using k unentangled quantum

proofs. Many of the simplest questions about this class have remained

embarrassingly open: for example, can we give any evidence that k

quantum proofs are more powerful than one? Can ...
more >>>