Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PSEUDO-RANDOM GENERATOR:
Reports tagged with pseudo-random generator:
TR05-071 | 29th June 2005
Marius Zimand

#### Simple extractors via constructions of cryptographic pseudo-random generators

Trevisan has shown that constructions of pseudo-random generators from
hard functions (the Nisan-Wigderson approach) also produce extractors.
We show that constructions of pseudo-random generators from one-way permutations
(the Blum-Micali-Yao approach) can be used for building extractors as well.
Using this new technique we build extractors that ... more >>>

TR11-069 | 18th April 2011
Marius Zimand

#### On the optimal compression of sets in PSPACE

We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>>

TR16-196 | 5th December 2016
Igor Carboni Oliveira, Rahul Santhanam

#### Pseudodeterministic Constructions in Subexponential Time

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

TR21-013 | 20th January 2021
Srinivasan Arunachalam, Penghui Yao

#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary $m$-facet polytopes in $n$ variables with seed length poly-logarithmic in $m,n$, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, ... more >>>

ISSN 1433-8092 | Imprint