Pseudorandom generators for group products

DOI10.1145/1993636.1993672zbMath1288.68131OpenAlexW1967969290MaRDI QIDQ5419096

Prajakta Nimbhorkar, Michal Koucký, Pavel Pudlák

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993672

zbMATH Keywords

pseudorandom generatorssmall bias spacesbounded width branching programsrandomized group product

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (17)

A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Learning Read-Constant Polynomials of Constant Degree Modulo Composites ⋮ Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs ⋮ Learning read-constant polynomials of constant degree modulo composites ⋮ Approximating iterated multiplication of stochastic matrices in small space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

This page was built for publication: Pseudorandom generators for group products