Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hardness versus randomness:
TR00-009 | 21st February 2000
Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

Extractors and pseudo-random generators with optimal seed length

We give the first construction of a pseudo-random generator with
optimal seed length that uses (essentially) arbitrary hardness.
It builds on the novel recursive use of the NW-generator in
a previous paper by the same authors, which produced many optimal
generators one of which was pseudo-random. This is achieved ... more >>>

TR18-085 | 26th April 2018
Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan

XOR Codes and Sparse Random Linear Equations with Noise

A $k$-LIN instance is a system of $m$ equations over $n$ variables of the form $s_{i[1]} + \dots + s_{i[k]} =$ 0 or 1 modulo 2 (each involving $k$ variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are ... more >>>

TR18-092 | 4th May 2018
Marco Carmosino, Russell Impagliazzo, Manuel Sabin

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>

ISSN 1433-8092 | Imprint