98 citations · 406 across the 27 of their papers we have counts for
8 papers · 1 filter
Generative Models of Huge Objects
Lunjia Hu, Inbal Livni-Navon, Omer Reingold
This work initiates the systematic study of explicit distributions that are indistinguishable from a single exponential-size combinatorial object. In this we extend the work of Gol…
Deterministic Approximation of Random Walks in Small Space
Jack Murtagh, Omer Reingold, Aaron Sidford +1
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph , a positive integer , and a set of vertices, approximates the conductance of $…
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, Avishay Tal
We construct pseudorandom generators of seed length that -fool ordered read-once branching programs (ROBPs) of width and length . For…
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Jack Murtagh, Omer Reingold, Aaron Sidford +1
We give a deterministic -space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating h…
Pseudorandomness for Regular Branching Programs via Fourier Analysis
Omer Reingold, Thomas Steinke, Salil Vadhan
We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed lengt…
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan, Raghu Meka, Omer Reingold +2
We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pse…