Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amin Gohari:

TR14-179 | 20th December 2014
Salman Beigi, Omid Etesami, Amin Gohari

Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources

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

TR14-100 | 4th August 2014
Salman Beigi, Omid Etesami, Amin Gohari

The Value of Help Bits in Randomized and Average-Case Complexity

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

ISSN 1433-8092 | Imprint