All reports by Author Omer Reingold:

__
TR13-086
| 13th June 2013
__

Omer Reingold, Thomas Steinke, Salil Vadhan#### Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

__
TR12-060
| 16th May 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold#### DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

__
TR11-106
| 6th August 2011
__

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan#### The Limits of Two-Party Differential Privacy

__
TR11-068
| 27th April 2011
__

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder#### Balls and Bins: Smaller Hash Families and Faster Evaluation

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 length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold

Given a DNF formula $f$ on $n$ variables, the two natural size measures are the number of terms or size $s(f)$, and the maximum width of a term $w(f)$. It is folklore that short DNF formulas can be made narrow. We prove a converse, showing that narrow formulas can be ... more >>>

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>