Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HARDNESS VERSUS RANDOMNESS:
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 >>>

TR19-037 | 5th March 2019
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

#### Closure of VP under taking factors: a short and simple proof

Revisions: 1

In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree $d$ polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>>

TR20-081 | 21st May 2020
Robert Andrews

#### Algebraic Hardness versus Randomness in Low Characteristic

We show that lower bounds for explicit constant-variate polynomials over fields of characteristic $p > 0$ are sufficient to derandomize polynomial identity testing over fields of characteristic $p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the ... more >>>

TR20-148 | 28th September 2020
Lijie Chen, Roei Tell

#### Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost

Extending the classical hardness-to-randomness'' line-of-works, Doron et al. (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a function in $\mathcal{DTIME}[2^n]$ that cannot be computed by randomized SVN circuits of size $2^{(1-\epsilon)\cdot n}$ for a small $\epsilon$.

In this work we ... more >>>

ISSN 1433-8092 | Imprint