Omer Reingold

According to our database1, Omer Reingold authored at least 96 papers between 1995 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2014, "For contributions to the study of pseudorandomness, derandomization, and cryptography.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Learning from Outcomes: Evidence-Based Rankings.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Tracking and Improving Information in the Service of Fairness.
Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Deterministic Approximation of Random Walks in Small Space.
Proceedings of the Approximation, 2019

2018
Incremental Deterministic Public-Key Encryption.
J. Cryptology, 2018

Efficient Batch Verification for UP.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Pseudorandom Generators for Width-3 Branching Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2018

On the Communication Complexity of Key-Agreement Protocols.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Fairness Through Computationally-Bounded Awareness.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Multicalibration: Calibration for the (Computationally-Identifiable) Masses.
Proceedings of the 35th International Conference on Machine Learning, 2018

2017
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Calibration for the (Computationally-Identifiable) Masses.
CoRR, 2017

Guilt-free data reuse.
Commun. ACM, 2017

ERA: A Framework for Economic Resource Allocation for the Cloud.
Proceedings of the 26th International Conference on World Wide Web Companion, 2017

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
New techniques and tighter bounds for local computation algorithms.
J. Comput. Syst. Sci., 2016

Constant-Round Interactive Proofs for Delegating Computation.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Equality and Social Mobility in Twitter Discussion Groups.
Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, 2016

Adaptive Condorcet-Based Stopping Rules Can Be Efficient.
Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

2015
Finding Collisions in Interactive Protocols - Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments.
SIAM J. Comput., 2015

Preserving Statistical Validity in Adaptive Data Analysis.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Generalization in Adaptive Data Analysis and Holdout Reuse.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Pure Differential Privacy for Rectangle Queries via Private Partitions.
Proceedings of the Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29, 2015

2014
A New Interactive Hashing Theorem.
J. Cryptology, 2014

Fault tolerance in large games.
Games Econ. Behav., 2014

Pseudorandom Graphs in Data Structures.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Fast Pseudorandomness for Independence and Load Balancing - (Extended Abstract).
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Deterministic Coupon Collection and Better Strong Dispersers.
Proceedings of the Approximation, 2014

2013
Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Electronic Colloquium on Computational Complexity (ECCC), 2013

DNF sparsification and a faster deterministic counting algorithm.
Computational Complexity, 2013

2012
Better pseudorandom generators from milder pseudorandom restrictions.
Electronic Colloquium on Computational Complexity (ECCC), 2012

DNF Sparsification and a Faster Deterministic Counting.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Fairness through awareness.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011
S-T connectivity on digraphs with a known stationary distribution.
ACM Trans. Algorithms, 2011

The Limits of Two-Party Differential Privacy.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Balls and Bins: Smaller Hash Families and Faster Evaluation.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Only valuable experts can be valued.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010
Universal One-Way Hash Functions via Inaccessible Entropy.
IACR Cryptology ePrint Archive, 2010

Partial exposure in large games.
Games Econ. Behav., 2010

Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Pseudorandom Generators for Combinatorial Shapes.
Electronic Colloquium on Computational Complexity (ECCC), 2010

2009
Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.
SIAM J. Comput., 2009

Players' Effects Under Limited Independence.
Math. Oper. Res., 2009

Inaccessible Entropy.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Derandomized Constructions of k-Wise (Almost) Independent Permutations.
Algorithmica, 2009

On the complexity of differentially private data release: efficient algorithms and hardness results.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Computational Differential Privacy.
Proceedings of the Advances in Cryptology, 2009

Pseudorandom Bit Generators That Fool Modular Sums.
Proceedings of the Approximation, 2009

How Well Do Random Walks Parallelize?.
Proceedings of the Approximation, 2009

2008
Undirected connectivity in log-space.
J. ACM, 2008

Dense Subsets of Pseudorandom Sets.
Electronic Colloquium on Computational Complexity (ECCC), 2008

2007
Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments.
Electronic Colloquium on Computational Complexity (ECCC), 2007

2006
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem.
SIAM J. Comput., 2006

Completeness in Two-Party Secure Computation: A Computational View.
J. Cryptology, 2006

Statistically-Hiding Commitment from Any One-Way Function.
IACR Cryptology ePrint Archive, 2006

Derandomized Constructions of k-Wise (Almost) Independent Permutations
Electronic Colloquium on Computational Complexity (ECCC), 2006

Pseudorandom walks on regular digraphs and the RL vs. L problem.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
On the Power of the Randomized Iterate
Electronic Colloquium on Computational Complexity (ECCC), 2005

On the Error Parameter of Dispersers
Electronic Colloquium on Computational Complexity (ECCC), 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Electronic Colloquium on Computational Complexity (ECCC), 2005

Tight bounds for shared memory systems accessed by Byzantine processes.
Distributed Computing, 2005

Keyword Search and Oblivious Pseudorandom Functions.
Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

On Robust Combiners for Oblivious Transfer and Other Primitives.
Proceedings of the Advances in Cryptology, 2005

2004
Just fast keying: Key agreement in a hostile internet.
ACM Trans. Inf. Syst. Secur., 2004

Number-theoretic constructions of efficient pseudo-random functions.
J. ACM, 2004

Undirected ST-Connectivity in Log-Space
Electronic Colloquium on Computational Complexity (ECCC), 2004

Notions of Reducibility between Cryptographic Primitives.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Immunizing Encryption Schemes from Decryption Errors.
Proceedings of the Advances in Cryptology, 2004

2003
Magic Functions.
J. ACM, 2003

Extractors: optimal up to constant factors.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
Pseudorandom Functions and Factoring.
SIAM J. Comput., 2002

Constructing Pseudo-Random Permutations with a Prescribed Structure.
J. Cryptology, 2002

Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
J. Comput. Syst. Sci., 2002

Tight Bounds for Shared Memory Systems Accessed by Byzantine Processes.
Proceedings of the Distributed Computing, 16th International Conference, 2002

Randomness conductors and constant-degree lossless expanders.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Streaming Computation of Combinatorial Objects.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Efficient, DoS-resistant, secure key exchange for internet protocols.
Proceedings of the 9th ACM Conference on Computer and Communications Security, 2002

2001
Pseudo-Random Functions and Factoring
Electronic Colloquium on Computational Complexity (ECCC), 2001

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Electronic Colloquium on Computational Complexity (ECCC), 2001

On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Priced Oblivious Transfer: How to Sell Digital Goods.
Proceedings of the Advances in Cryptology, 2001

2000
Extracting Randomness via Repeated Condensing
Electronic Colloquium on Computational Complexity (ECCC), 2000

Pseudo-random functions and factoring (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

The Relationship between Public Key Encryption and Oblivious Transfer.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited.
J. Cryptology, 1999

Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions.
J. Comput. Syst. Sci., 1999

Breaking Generalized Diffie-Hellmann Modulo a Composite is no Easier Than Factoring.
Inf. Process. Lett., 1999

On Recycling the Randomness of States in Space Bounded Computation.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Error Reduction for Extractors.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Distributed Pseudo-random Functions and KDCs.
Proceedings of the Advances in Cryptology, 1999

1998
Perfectly One-Way Probabilistic Hash Functions (Preliminary Version).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs (Extended Abstract).
Proceedings of the Advances in Cryptology, 1998

1997
Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring
Electronic Colloquium on Computational Complexity (ECCC), 1997

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited
Electronic Colloquium on Computational Complexity (ECCC), 1997

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1995
Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995


  Loading...