Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PERMUTATION BRANCHING PROGRAMS:
Reports tagged with permutation branching programs:
TR10-113 | 16th July 2010
Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

#### Pseudorandom Generators for Group Products

We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

TR12-083 | 29th June 2012
Thomas Steinke

#### Pseudorandomness for Permutation Branching Programs Without the Group Theory

We exhibit an explicit pseudorandom generator that stretches an $O \left( \left( w^4 \log w + \log (1/\varepsilon) \right) \cdot \log n \right)$-bit random seed to $n$ pseudorandom bits that cannot be distinguished from truly random bits by a permutation branching program of width $w$ with probability more than $\varepsilon$. ... more >>>

TR20-138 | 9th September 2020
William Hoza, Edward Pyne, Salil Vadhan

#### Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here, $n$ is the length of the ... more >>>

ISSN 1433-8092 | Imprint