Research and Publications

My research is in the foundations of computer science and most notably in computational complexity, cryptography and the societal impact of computation. Among my contributions are small-memory deterministic graph walks, explicit constructions of lossless expander-graphs, randomness extractors and pseudorandom functions as well as establishing influential notions in the area of algorithmic fairness such as metric fairness (fairness through awareness) and multicalibration.

Publications appear in chronological order according to the date of first publication. This list may be missing (recent or older) papers so you may want to look at my DBLP page too (even my CV is likely more up to date). Furthermore, the versions here may not be the most up-to-date (but fortunately, most of my collaborators are better at that ;-).

• Moni Naor and Omer Reingold, Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions, in J. Comput. Syst. Sci., vol. 58, no. 2, pp. 336-375, 1999. Preliminary version: FOCS 1995
• Moni Naor and Omer Reingold, On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited, in J. Cryptology, vol. 12, no. 1, pp. 29-66, 1999. Preliminary version: STOC 1997
  • Related: The NR Mode of Operation
• Moni Naor and Omer Reingold, Number-theoretic constructions of efficient pseudo-random functions, in J. ACM, vol. 51, no. 2, pp. 231-262, 2004. Preliminary version: FOCS 1997. Implementation (by Mike Langberg).
• Ran Canetti, Daniele Micciancio, and Omer Reingold, Perfectly One-Way Probabilistic Hash Functions, in STOC, 1998
• Moni Naor and Omer Reingold, From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs, in Advances in Cryptology – CRYPTO ’98, 1998
• Eli Biham, Dan Boneh, and Omer Reingold, Breaking Generalized Diffie-Hellmann Modulo a Composite is no Easier Than Factoring, in Inf. Process. Lett., vol. 70, no. 2, pp. 83-87, 1999
• Ran Raz and Omer Reingold, On Recycling the Randomness of States in Space Bounded Computation, in STOC, 1999
• Ran Raz, Omer Reingold, and Salil P. Vadhan, Extracting all the Randomness and Reducing the Error in Trevisan’s Extractors, in J. Comput. Syst. Sci., vol. 65, no. 1, pp. 97-128, 2002. Preliminary version: STOC 1999.
• Moni Naor, Benny Pinkas, and Omer Reingold, Distributed Pseudo-random Functions and KDCs, in EUROCRYPT, 1999
• Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer, Magic Functions, in J. ACM, vol. 50, no. 6, pp. 852-921, 2003. Preliminary Version: FOCS 1999.
• Ran Raz, Omer Reingold, and Salil P. Vadhan, Error Reduction for Extractors, in FOCS, 1999
• Moni Naor, Omer Reingold, and Alon Rosen, Pseudorandom Functions and Factoring, in SIAM J. Comput., vol. 31, no. 5, pp. 1383-1404, 2002. Preliminary version: STOC 2000.
• Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, and Mahesh Viswanathan, The Relationship between Public Key Encryption and Oblivious Transfer, in FOCS, 2000
• Omer Reingold, Ronen Shaltiel, and Avi Wigderson, Extracting Randomness via Repeated Condensing, in SIAM J. Comput., 35(5), 1185-1209, 2006. Preliminary version: FOCS, 2000
• Omer Reingold, Salil P. Vadhan, and Avi Wigderson, Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors, in FOCS, 2000.  Full Version of part of this work: Annals of Mathematics, vol. 155(1), 2001.
• Cynthia Dwork, Michael Langberg, Moni Naor, Kobbi Nissim, and Omer Reingold, Succinct proofs for NP and spooky interactions, unpublished 2001
• William Aiello, Yuval Ishai, and Omer Reingold, Priced Oblivious Transfer: How to Sell Digital Goods, in Advances in Cryptology – EUROCRYPT 2001
• Moni Naor and Omer Reingold, Constructing Pseudo-Random Permutations with a Prescribed Structure, in J. Cryptology, vol. 15, no. 2, pp. 97-102, 2002. Preliminary version: SODA 2011.
• William Aiello, Steven M. Bellovin, Matt Blaze, Ran Canetti, John Ioannidis, Angelos D. Keromytis, and Omer Reingold, Just fast keying: Key agreement in a hostile internet, in ACM Trans. Inf. Syst. Secur., vol. 7, no. 2, pp. 242-273, 2004. Preliminary Version: Efficient, DoS-Resistant, Secure Key Exchange for Internet Protocols. Security Protocols Workshop 2001: pp. 27-39, 2001.
• Yael Gertner, Tal Malkin, and Omer Reingold, On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates, in FOCS, 2001
• Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, and Avi Wigderson, Randomness conductors and constant-degree lossless expanders, in STOC, 2002
• Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, and Ronen Shaltiel, Streaming Computation of Combinatorial Objects, in IEEE Conference on Computational Complexity (CCC), 2002
• Noga Alon, Michael Merritt, Omer Reingold, Gadi Taubenfeld, and Rebecca N. Wright, Tight bounds for shared memory systems accessed by Byzantine processes, in Distributed Computing, vol. 18, no. 2, pp. 99-109, 2005. Preliminary version: DISC 2002
• Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, and Avi Wigderson, Extractors: optimal up to constant factors, in STOC, ACM, 2003
• Danny Harnik, Moni Naor, Omer Reingold, and Alon Rosen, Completeness in two-party secure computation: a computational view, in , J. Cryptology 19(4), 521-552, 2006. Preliminary version: STOC 2004.
• Omer Reingold, Luca Trevisan, and Salil P. Vadhan, Notions of Reducibility between Cryptographic Primitives, in TCC, Springer, 2004
• C. Dwork, M. Naor, O. Reingold, Immunizing encryption schemes from decryption errors, EUROCRYPT 2004, 342-360, 2004.
• Irit Dinur and Omer Reingold, Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem, in SIAM J. Comput., vol. 36, no. 4, pp. 975-1024, 2006. Preliminary version: FOCS 2004
• O. Reingold, S. Vadhan and A. Wigderson. A Note on Extracting Randomness from Santha-Vazirani Sources, unpublished manuscript.
• Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold, Keyword Search and Oblivious Pseudorandom Functions, in TCC, Springer, 2005
• Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold, and Alon Rosen, On Robust Combiners for Oblivious Transfer and Other Primitives, in EUROCRYPT, Springer, 2005
• Omer Reingold, Undirected connectivity in log-space, in J. ACM, vol. 55, no. 4, 2008 Preliminary version: STOC 2005. Best paper award.
• Eyal Kaplan, Moni Naor, and Omer Reingold, Derandomized Constructions of k-Wise (Almost) Independent Permutations, in Algorithmica, vol. 55, no. 1, pp. 113-133, 2009. Preliminary version: RANDOM 2005.
• Ronen Gradwohl, Guy Kindler, Omer Reingold, and Amnon Ta-Shma, On the Error Parameter of Dispersers, in APPROX-RANDOM, 2005
• Omer Reingold, Luca Trevisan, and Salil P. Vadhan, Pseudorandom walks on regular digraphs and the RL vs. L problem, in STOC, 2006
• Iftach Haitner, Danny Harnik, and Omer Reingold, Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions, in ICALP 2006. Track C best paper award.
• Iftach Haitner, Danny Harnik, and Omer Reingold, On the Power of the Randomized Iterate, SIAM J. Comput. 40(6): 1486-1528 (2011). Preliminary version in CRYPTO 2006. Best paper award.
• Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil P. Vadhan, Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function, in SIAM J. Comput., vol. 39, no. 3, pp. 1153-1218, 2009. Preliminary version of part of the work: STOC 2007.
• Kai-Min Chung, Omer Reingold, and Salil P. Vadhan, S-T Connectivity on Digraphs with a Known Stationary Distribution, in ACM Transactions on Algorithms 7(3): 30 (2011), vol. 14, no. 030, 2011. Preliminary version: CCC 2007.
• Iftach Haitner and Omer Reingold, A New Interactive Hashing Theorem, in J. Cryptology 27(1): 109-138 (2014), Preliminary version: CCC 2007
• Iftach Haitner, Jonathan J. Hoch, Omer Reingold, and Gil Segev, Finding Collisions in Interactive Protocols – A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments,  SIAM J. Comput. 44(1): 193-242 (2015). Preliminary version: FOCS 2007.
• Ronen Gradwohl and Omer Reingold, Fault tolerance in large games, in Games and Economic Behavior 86: 438-457 (2014). Preliminary version: ACM Conference on Electronic Commerce (EC) 2008.
• Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan, Dense Subsets of Pseudorandom Sets, in FOCS 2008
  • Also: Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan, New Proofs of the Green–Tao–Ziegler Dense Model Theorem: An Exposition, 2008
• Ronen Gradwohl, Omer Reingold, Ariel Yadin, and Amir Yehudayoff, Players’ Effects Under Limited Independence, in Math. Oper. Res., vol. 34, no. 4, pp. 971-980, 2009
• Iftach Haitner, Omer Reingold, Salil P. Vadhan, and Hoeteck Wee, Inaccessible entropy, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, (STOC) 2009
• Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan, On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results, in Proceedings of the 41th Annual ACM Symposium on Theory of Computing (STOC)  2009
• Ilya Mironov, Omkant Pandey, Omer Reingold and Salil Vadhan: Computational Differential Privacy. CRYPTO 2009: 126-142.
• Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil P. Vadhan, Pseudorandom Bit Generators That Fool Modular Sums, in APPROX-RANDOM 2009
• Klim Efremenko and Omer Reingold, How Well Do Random Walks Parallelize?, in APPROX-RANDOM 2009
• Iftach Haitner, Omer Reingold, and Salil P. Vadhan, Efficiency improvements in constructing pseudorandom generators from one-way functions, in Proceedings of the 42nd ACM Symposium on Theory of Computing, SIAM J. Comput. 42(3): 1405-1430 (2013). Preliminary version: STOC 2010
• Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil P. Vadhan, and Hoeteck Wee, Universal One-Way Hash Functions via Inaccessible Entropy, in Advances in Cryptology – EUROCRYPT 2010
• Ronen Gradwohl and Omer Reingold, Partial exposure in large games, in Games and Economic Behavior, vol. 68, no. 2, pp. 602 – 613, 2010
• Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil Vadhan, The Limits of Two-Party Differential Privacy, in 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2010
• Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman, Pseudorandom Generators for Combinatorial Shapes, in SIAM J. Comput. 42(3): 1051-1076 (2013).  Preliminary version: STOC 2011
• Moshe Babaioff, Liad Blumrosen, Nicolas Lambert, and Omer Reingold, Only Valuable Experts Can Be Valued, in ACM Conference on Electronic Commerce (EC) 2011
• Laura Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder, Balls and Bins: Smaller Hash Families and Faster Evaluation, in SIAM J. Comput. 42(3): 1030-1050 (2013). Preliminary version: FOCS 2011
• Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Rich Zemel, Fairness Through Awareness, Innovations in Theoretical Computer Science (ITCS) 2012
• Ilya Mironov, Omkant Pandey, Omer Reingold, and Gil Segev, Incremental Deterministic Public-Key Encryption, in J. Cryptology 31(1): 134-161 (2018). Preliminary version: EUROCRYPT’ 2012
• Parikshit Gopalan, Raghu Meka, and Omer Reingold, DNF Sparsification and a faster deterministic counting algorithm, in Computational Complexity 22(2): 275-310 (2013). Preliminary version in CCC 2012
• Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan, Better pseudorandom generators from milder pseudorandom restrictions, in FOCS 2012
• Omer Reingold, Thomas Steinke, Salil P. Vadhan: Pseudorandomness for Regular Branching Programs via Fourier Analysis. APPROX-RANDOM 2013: 655-670
• Omer Reingold, Ron D. Rothblum, Udi Wieder: Pseudorandom Graphs in Data Structures. ICALP (1) 2014: 943-954
• Raghu Meka, Omer Reingold, Guy N. Rothblum, Ron D. Rothblum: Fast Pseudorandomness for Independence and Load Balancing, ICALP (1) 2014: 859-870
• Raghu Meka, Omer Reingold, Yuan Zhou: Deterministic Coupon Collection and Better Strong Dispersers. APPROX-RANDOM 2014: 872-884
• Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth: Preserving Statistical Validity in Adaptive Data Analysis. STOC 2015: 117-126
• Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth: The reusable holdout: Preserving validity in adaptive data analysis, Science 7 August 2015: Vol. 349 no. 6248 pp. 636-638
• Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum: Pure Differential Privacy for Rectangle Queries via Private Partitions, ASIACRYPT (2) 2015: 735-751
• Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth: Generalization in Adaptive Data Analysis and Holdout Reuse, NIPS 2015: 2350-2358
• Kat Ellis, Moises Goldszmidt, Gert Lanckriet, Nina Mishra and Omer Reingold, Attention Exchange: Equality and Social Mobility in Online Communities, WSDM 2016: 523-532
• Omer Reingold; Guy N. Rothblum; Ron D. Rothblum, Constant-Round Interactive Proofs for Delegating Computation, STOC 2016: 49-62
• Omer Reingold, Nina Narodytska: Adaptive Condorcet-Based Stopping Rules Can Be Efficient. ECAI 2016: 1704-1705
• Omer Reingold, Shai Vardi: New techniques and tighter bounds for local computation algorithms. J. Comput. Syst. Sci. 82(7): 1180-1200 (2016)
• Moshe Babaioff, Yishay Mansour, Noam Nisan, Gali Noti, Carlo Curino, Nar Ganapathy, Ishai Menache, Omer Reingold, Moshe Tennenholtz, Erez Timnat: ERA: A Framework for Economic Resource Allocation for the Cloud. WWW (Companion Volume) 2017: 635-642
• Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth: Guilt-free data reuse. Commun. ACM 60(4): 86-93 (2017)
• Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan, Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. FOCS 2017: 801-812, 2017
• Eshan Chattopadhyay, Pooya Hatami, Omer Reingold and Avishay Tal, Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity, STOC 2018: 363-375 2018
• Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold and Guy N. Rothblum, Calibration for the (Computationally-Identifiable) Masses, ICML 1944-1953, 2018
• Omer Reingold, Guy N. Rothblum and Ron Rothblum, Efficient Batch Verification for UP, CCC 2018: 22:1-22:23,
• Raghu Meka, Omer Reingold, Avishay Tal, Pseudorandom Generators for Width-3 Branching Programs, 2018
• Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold and Amir Yehudayoff, On the Communication Complexity of Key-Agreement Protocols, 2018
• Michael P. Kim, Omer Reingold and Guy N. Rothblum, Fairness Through Computationally-Bounded Awareness, 2018

Unpublished Manuscripts

• Moni Naor and Omer Reingold, A Pseudo-Random Encryption Mode, manuscript
• C. Dwork, M. Langberg, M. Naor, K. Nissim and O. Reingold, Succinct proofs for NP and spooky interactions, manuscript, 2001.
• O. Reingold, S. Vadhan and A. Wigderson. A Note on Extracting Randomness from Santha-Vazirani Sources, manuscript 2004.
•  Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan, New Proofs of the Green–Tao–Ziegler Dense Model Theorem: An Exposition, manuscript 2008

And now for something completely different:

• Moni Naor, Yael Naor and Omer Reingold, Applied Kid Cryptography or How to convince your children you are not cheating, August 98. At: J. of Craptology vol. 0(1), April 1999. Also see: The Puzzler page.