Pseudorandom generators for group products
From MaRDI portal
Publication:5419096
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
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
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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ 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
