Omer Reingold - Microsoft Research

Omer Reingold

Mailing address:

1065 La Avenida
Mountain View,
CA, 94043, US

Phone: +1 650.693.1381

I am a Principal Researcher at Microsoft Research Silicon Valley. My research is in Foundations of Computer Science, mainly in Computational Complexity and Foundations of Cryptography. Much of my research deals with Randomness, Derandomization and Explicit Combinatorial Constructions.

In 2004 I assumed a faculty position in the computer science department of The Weizmann Institute of Science. During the years 1999-2004, I was a member of AT&T Labs, Florham Park, NJ, and a visiting member of the School of Mathematics, Institute for Advanced Study, Princeton, NJ. Earlier, I completed my PhD and a short period of postdoctoral studies at the Weizmann Institute. My PhD advisor was Moni Naor. During the years 1991-1994, I completed my undergraduate studies at Tel-Aviv University. For more details please see my (hopefully not too outdated) CV.

Some General Audience and Survey Talks (more talks in individual paper's pages):

TechFest 2011 Demo (with Cynthia Dwork): On Randomness and Pseudorandomness
The Many Entropies in One-Way Functions, “Barriers in Computational Complexity II” workshop, 2010
Randomness vs. Memory: Prospects and Barriers, “Barriers in Computational Complexity” workshop, 2010
Walk the Walk: On Pseudorandomness, Expansion, and Connectivity, Israel Math Union, 2008. Similar with more focus on pseudorandom walks: Pseudorandom Walks: Looking Random in The Long Run or All The Way?
Expander Graphs: The Unbalanced Case, "Expanders in Pure and Applied Mathematics" workshop, IPAM 2008

General audience talk on TOC, related Hebrew version (not identical), given at the Weizmann Institute around 2007
On Black-Box Separations in Cryptography, TCC 2006
Cryptography: on the Hope for Privacy in a Digital World, Harvard Center for Research on Computation and Society (CRCS) 2005
Randomness Conductors I and II, Institute for Advanced Study, 2002

Why Extractors? Princeton-Area Center for Theory 2001

Online Publications (Under Construction)

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan, Better pseudorandom generators from milder pseudorandom restrictions, in FOCS'12, IEEE, October 2012
Parikshit Gopalan, Raghu Meka, and Omer Reingold, DNF Sparsification and a faster deterministic counting algorithm, in CCC'11, IEEE, June 2012
Ilya Mironov, Omkant Pandey, Omer Reingold, and Gil Segev, Incremental Deterministic Public-Key Encryption, in EUROCRYPT'12, Springer Verlag, April 2012
Moshe Babaioff, Liad Blumrosen, Nicolas Lambert, and Omer Reingold, Only Valuable Experts Can Be Valued, in ACM Conference on Electronic Commerce (EC'11), ACM, June 2011
Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman, Pseudorandom Generators for Combinatorial Shapes, in STOC'11, ACM, May 2011
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
Laura Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder, Balls and Bins: Smaller Hash Families and Faster Evaluation, in FOCS, IEEE, 2011
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), Institute of Electrical and Electronics Engineers, Inc., October 2010
Ronen Gradwohl and Omer Reingold, Partial exposure in large games, in Games and Economic Behavior, vol. 68, no. 2, pp. 602 - 613, 2010
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, (STOC 2010), 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, 2010
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), Association for Computing Machinery, Inc., Bethesda, Maryland, May 2009
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
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), 2009
Klim Efremenko and Omer Reingold, How Well Do Random Walks Parallelize?, in APPROX-RANDOM 2009, 2009
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
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
Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil P. Vadhan, Pseudorandom Bit Generators That Fool Modular Sums, in APPROX-RANDOM 2009, 2009
Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan, Dense Subsets of Pseudorandom Sets, in FOCS, IEEE Computer Society, 2008
Omer Reingold, Undirected connectivity in log-space, in J. ACM, vol. 55, no. 4, 2008
Ronen Gradwohl and Omer Reingold, Fault tolerance in large games, in ACM Conference on Electronic Commerce, ACM, 2008
Iftach Haitner and Omer Reingold, A New Interactive Hashing Theorem, in IEEE Conference on Computational Complexity, IEEE Computer Society, 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, in FOCS, IEEE Computer Society, 2007
Omer Reingold, Luca Trevisan, and Salil P. Vadhan, Pseudorandom walks on regular digraphs and the RL vs. L problem, in STOC, ACM, 2006
Iftach Haitner, Danny Harnik, and Omer Reingold, Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions, in ICALP (2), Springer, 2006
Iftach Haitner, Danny Harnik, and Omer Reingold, On the Power of the Randomized Iterate, in CRYPTO, Springer, 2006
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
Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold, and Alon Rosen, On Robust Combiners for Oblivious Transfer and Other Primitives, in EUROCRYPT, Springer, 2005
Ronen Gradwohl, Guy Kindler, Omer Reingold, and Amnon Ta-Shma, On the Error Parameter of Dispersers, in APPROX-RANDOM, 2005
Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold, Keyword Search and Oblivious Pseudorandom Functions, in TCC, Springer, 2005
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
Danny Harnik, Moni Naor, Omer Reingold, and Alon Rosen, Completeness in two-party secure computation: a computational view, in STOC, ACM, 2004
Omer Reingold, Luca Trevisan, and Salil P. Vadhan, Notions of Reducibility between Cryptographic Primitives, in TCC, Springer, 2004
Moni Naor and Omer Reingold, Number-theoretic constructions of efficient pseudo-random functions, in J. ACM, vol. 51, no. 2, pp. 231-262, 2004
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
Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer, Magic Functions, in J. ACM, vol. 50, no. 6, pp. 852-921, 2003
Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, and Avi Wigderson, Extractors: optimal up to constant factors, in STOC, ACM, 2003
Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, and Avi Wigderson, Randomness conductors and constant-degree lossless expanders, in STOC, 2002
Moni Naor, Omer Reingold, and Alon Rosen, Pseudorandom Functions and Factoring, in SIAM J. Comput., vol. 31, no. 5, pp. 1383-1404, 2002
Moni Naor and Omer Reingold, Constructing Pseudo-Random Permutations with a Prescribed Structure, in J. Cryptology, vol. 15, no. 2, pp. 97-102, 2002
Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, and Ronen Shaltiel, Streaming Computation of Combinatorial Objects, in IEEE Conference on Computational Complexity (CCC), 2002
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
Cynthia Dwork, Michael Langberg, Moni Naor, Kobbi Nissim, and Omer Reingold, Succinct proofs for NP and spooky interactions, 2001
William Aiello, Yuval Ishai, and Omer Reingold, Priced Oblivious Transfer: How to Sell Digital Goods, in Advances in Cryptology - EUROCRYPT 2001, 2001
Yael Gertner, Tal Malkin, and Omer Reingold, On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates, in FOCS, 2001
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 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
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
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, Omer Reingold, and Salil P. Vadhan, Error Reduction for Extractors, in FOCS, 1999
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
Moni Naor, Benny Pinkas, and Omer Reingold, Distributed Pseudo-random Functions and KDCs, in EUROCRYPT, 1999
Ran Raz and Omer Reingold, On Recycling the Randomness of States in Space Bounded Computation, in STOC, 1999
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
Ran Canetti, Daniele Micciancio, and Omer Reingold, Perfectly One-Way Probabilistic Hash Functions, in STOC, 1998

Students, Postdocs and Interns:

Interns:

Postdocs:

Eyal Rozenman

PhD:

MSc:

Sergey Novikov
Klim Efremenko
Tal Kramer
Michal Igell

Some Other Activities:

MSR-SVC Theory Seminar
Editorial and Scientific Boards:
IACR Journal of Cryptology (JofC), Electronic Colloquium on Computational Complexity (ECCC), SIAM Journal on Computing (SICOMP), ACM Transactions on Computation Theory (ToCT).
Program Committees: CRYPTO 2001, RANDOM 2001, FOCS 2002, TCC 2004, EUROCRYPT 2004, ICALP 2005., FOCS 2005, TCC 2007, CRYPTO 2007, RANDOM 2007 (PC Chair), STOC 2008, TCC 2009 (PC Chair), CCC 2010, CCC 2011 (PC Chair)
Online Courses: Topics in Pseudorandomness, Introduction to Computational Learning Theory.

Extra Curricular:

Leah, Yuval and Itai
My short and sweet singing career. Devoted to my one and only L on the occasion of her 33.333 birthday. (With deep apologies to Nat King Cole.)
Playback Theater. Showing at a theater near you ... try it some time.