Omer Reingold

According to our database, Omer Reingold authored at least 120 papers between 1995 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Oracle Efficient Online Multicalibration and Omniprediction.

Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dissenting Explanations: Leveraging Disagreement to Reduce Model Overreliance.

Omer Reingold, Judy Hanwen Shen, Aditi Talati

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Characterizing notions of omniprediction via multicalibration.

Parikshit Gopalan, Michael P. Kim, Omer Reingold

CoRR, 2023

Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration.

Parikshit Gopalan, Michael P. Kim, Omer Reingold

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Loss Minimization Through the Lens Of Outcome Indistinguishability.

Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Omnipredictors for Constrained Optimization.

Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold, Chutong Yang

Proceedings of the International Conference on Machine Learning, 2023

Bidding Strategies for Proportional Representation in Advertisement Campaigns.

Inbal Livni Navon, Charlotte Peale, Omer Reingold, Judy Hanwen Shen

Proceedings of the 4th Symposium on Foundations of Responsible Computing, 2023

From the Real Towards the Ideal: Risk Prediction in a Better World.

Cynthia Dwork, Omer Reingold, Guy N. Rothblum

Proceedings of the 4th Symposium on Foundations of Responsible Computing, 2023

Generative Models of Huge Objects.

Lunjia Hu, Inbal Livni Navon, Omer Reingold

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Bringing Research-Life to Centerstage.

Omer Reingold

Bull. EATCS, 2022

KL Divergence Estimation with Multi-group Attribution.

Parikshit Gopalan, Nina Narodytska, Omer Reingold, Vatsal Sharan, Udi Wieder

CoRR, 2022

Omnipredictors.

Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, Udi Wieder

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Leximax Approximations and Representative Cohort Selection.

Monika Henzinger, Charlotte Peale, Omer Reingold, Judy Hanwen Shen

Proceedings of the 3rd Symposium on Foundations of Responsible Computing, 2022

Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability.

Lunjia Hu, Charlotte Peale, Omer Reingold

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

Multicalibrated Partitions for Importance Weights.

Parikshit Gopalan, Omer Reingold, Vatsal Sharan, Udi Wieder

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

Beyond Bernoulli: Generating Random Outcomes that cannot be Distinguished from Nature.

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

2021

Deterministic Approximation of Random Walks in Small Space.

Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan

Theory Comput., 2021

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.

Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan

SIAM J. Comput., 2021

Monotone Branching Programs: Pseudorandomness and Circuit Complexity.

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2021

Pseudorandom Generators for Read-Once Monotone Branching Programs.

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan

Proceedings of the Approximation, 2021

Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers.

Lunjia Hu, Omer Reingold

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

Inaccessible Entropy II: IE Functions and Universal One-Way Hashing.

Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil P. Vadhan, Hoeteck Wee

Theory Comput., 2020

Outcome Indistinguishability.

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona

Electron. Colloquium Comput. Complex., 2020

Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions.

Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee

CoRR, 2020

Through the lens of a passionate theoretician.

Omer Reingold

Commun. ACM, 2020

Bounded-Leakage Differential Privacy.

Katrina Ligett, Charlotte Peale, Omer Reingold

Proceedings of the 1st Symposium on Foundations of Responsible Computing, 2020

2019

Learning from Outcomes: Evidence-Based Rankings.

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Tracking and Improving Information in the Service of Fairness.

Sumegha Garg, Michael P. Kim, Omer Reingold

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

2018

Incremental Deterministic Public-Key Encryption.

Ilya Mironov, Omkant Pandey, Omer Reingold, Gil Segev

J. Cryptol., 2018

Efficient Batch Verification for UP.

Omer Reingold, Guy N. Rothblum, Ron Rothblum

Electron. Colloquium Comput. Complex., 2018

Pseudorandom Generators for Width-3 Branching Programs.

Raghu Meka, Omer Reingold, Avishay Tal

Electron. Colloquium Comput. Complex., 2018

On the Communication Complexity of Key-Agreement Protocols.

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2018

Fairness Through Computationally-Bounded Awareness.

Michael P. Kim, Omer Reingold, Guy N. Rothblum

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.

Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum

Proceedings of the 35th International Conference on Machine Learning, 2018

2017

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity.

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Electron. Colloquium Comput. Complex., 2017

Calibration for the (Computationally-Identifiable) Masses.

Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum

CoRR, 2017

Guilt-free data reuse.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

Commun. ACM, 2017

ERA: A Framework for Economic Resource Allocation for the Cloud.

Moshe Babaioff, Yishay Mansour, Noam Nisan, Gali Noti, Carlo Curino, Nar Ganapathy, Ishai Menache, Omer Reingold, Moshe Tennenholtz, Erez Timnat

Proceedings of the 26th International Conference on World Wide Web Companion, 2017

2016

New techniques and tighter bounds for local computation algorithms.

Omer Reingold, Shai Vardi

J. Comput. Syst. Sci., 2016

Constant-Round Interactive Proofs for Delegating Computation.

Omer Reingold, Ron Rothblum, Guy N. Rothblum

Electron. Colloquium Comput. Complex., 2016

Equality and Social Mobility in Twitter Discussion Groups.

Katherine Ellis, Moisés Goldszmidt, Gert R. G. Lanckriet, Nina Mishra, Omer Reingold

Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, 2016

Adaptive Condorcet-Based Stopping Rules Can Be Efficient.

Omer Reingold, Nina Narodytska

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.

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

SIAM J. Comput., 2015

Preserving Statistical Validity in Adaptive Data Analysis.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Generalization in Adaptive Data Analysis and Holdout Reuse.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

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.

Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum

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.

Iftach Haitner, Omer Reingold

J. Cryptol., 2014

Fault tolerance in large games.

Ronen Gradwohl, Omer Reingold

Games Econ. Behav., 2014

Pseudorandom Graphs in Data Structures.

Omer Reingold, Ron D. Rothblum, Udi Wieder

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Fast Pseudorandomness for Independence and Load Balancing - (Extended Abstract).

Raghu Meka, Omer Reingold, Guy N. Rothblum, Ron D. Rothblum

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Deterministic Coupon Collection and Better Strong Dispersers.

Raghu Meka, Omer Reingold, Yuan Zhou

Proceedings of the Approximation, 2014

2013

Pseudorandomness for Regular Branching Programs via Fourier Analysis.

Omer Reingold, Thomas Steinke, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2013

DNF sparsification and a faster deterministic counting algorithm.

Parikshit Gopalan, Raghu Meka, Omer Reingold

Comput. Complex., 2013

2012

Better pseudorandom generators from milder pseudorandom restrictions.

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2012

DNF Sparsification and a Faster Deterministic Counting.

Parikshit Gopalan, Raghu Meka, Omer Reingold

Electron. Colloquium Comput. Complex., 2012

Fairness through awareness.

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

S-T connectivity on digraphs with a known stationary distribution.

Kai-Min Chung, Omer Reingold, Salil P. Vadhan

ACM Trans. Algorithms, 2011

The Limits of Two-Party Differential Privacy.

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

Electron. Colloquium Comput. Complex., 2011

Balls and Bins: Smaller Hash Families and Faster Evaluation.

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

Electron. Colloquium Comput. Complex., 2011

Only valuable experts can be valued.

Moshe Babaioff, Liad Blumrosen, Nicolas S. Lambert, Omer Reingold

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010

Universal One-Way Hash Functions via Inaccessible Entropy.

Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil P. Vadhan, Hoeteck Wee

IACR Cryptol. ePrint Arch., 2010

Partial exposure in large games.

Ronen Gradwohl, Omer Reingold

Games Econ. Behav., 2010

Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions.

Iftach Haitner, Omer Reingold, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2010

Pseudorandom Generators for Combinatorial Shapes.

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Electron. Colloquium Comput. Complex., 2010

2009

Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.

Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, Salil P. Vadhan

SIAM J. Comput., 2009

Players' Effects Under Limited Independence.

Ronen Gradwohl, Omer Reingold, Ariel Yadin, Amir Yehudayoff

Math. Oper. Res., 2009

Inaccessible Entropy.

Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee

Electron. Colloquium Comput. Complex., 2009

Derandomized Constructions of <i>k</i>-Wise (Almost) Independent Permutations.

Eyal Kaplan, Moni Naor, Omer Reingold

Algorithmica, 2009

On the complexity of differentially private data release: efficient algorithms and hardness results.

Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil P. Vadhan

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Computational Differential Privacy.

Ilya Mironov, Omkant Pandey, Omer Reingold, Salil P. Vadhan

Proceedings of the Advances in Cryptology, 2009

Pseudorandom Bit Generators That Fool Modular Sums.

Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan

Proceedings of the Approximation, 2009

How Well Do Random Walks Parallelize?.

Klim Efremenko, Omer Reingold

Proceedings of the Approximation, 2009

2008

Undirected connectivity in log-space.

Omer Reingold

J. ACM, 2008

Dense Subsets of Pseudorandom Sets.

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2008

2007

Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments.

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

Electron. Colloquium Comput. Complex., 2007

2006

Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem.

Irit Dinur, Omer Reingold

SIAM J. Comput., 2006

Completeness in Two-Party Secure Computation: A Computational View.

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

J. Cryptol., 2006

Statistically-Hiding Commitment from Any One-Way Function.

Iftach Haitner, Omer Reingold

IACR Cryptol. ePrint Arch., 2006

Derandomized Constructions of k-Wise (Almost) Independent Permutations

Eyal Kaplan, Moni Naor, Omer Reingold

Electron. Colloquium Comput. Complex., 2006

Pseudorandom walks on regular digraphs and the RL vs. L problem.

Omer Reingold, Luca Trevisan, Salil P. Vadhan

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions.

Iftach Haitner, Danny Harnik, Omer Reingold

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

On the Power of the Randomized Iterate

Iftach Haitner, Danny Harnik, Omer Reingold

Electron. Colloquium Comput. Complex., 2005

On the Error Parameter of Dispersers

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

Omer Reingold, Luca Trevisan, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2005

Tight bounds for shared memory systems accessed by Byzantine processes.

Noga Alon, Michael Merritt, Omer Reingold, Gadi Taubenfeld, Rebecca N. Wright

Distributed Comput., 2005

Keyword Search and Oblivious Pseudorandom Functions.

Michael J. Freedman, Yuval Ishai, Benny Pinkas, Omer Reingold

Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

On Robust Combiners for Oblivious Transfer and Other Primitives.

Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold, Alon Rosen

Proceedings of the Advances in Cryptology, 2005

2004

Just fast keying: Key agreement in a hostile internet.

William Aiello, Steven M. Bellovin, Matt Blaze, Ran Canetti, John Ioannidis, Angelos D. Keromytis, Omer Reingold

ACM Trans. Inf. Syst. Secur., 2004

Number-theoretic constructions of efficient pseudo-random functions.

Moni Naor, Omer Reingold

J. ACM, 2004

Undirected ST-Connectivity in Log-Space

Omer Reingold

Electron. Colloquium Comput. Complex., 2004

Notions of Reducibility between Cryptographic Primitives.

Omer Reingold, Luca Trevisan, Salil P. Vadhan

Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Immunizing Encryption Schemes from Decryption Errors.

Cynthia Dwork, Moni Naor, Omer Reingold

Proceedings of the Advances in Cryptology, 2004

2003

Magic Functions.

Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer

J. ACM, 2003

Extractors: optimal up to constant factors.

Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Pseudorandom Functions and Factoring.

Moni Naor, Omer Reingold, Alon Rosen

SIAM J. Comput., 2002

Constructing Pseudo-Random Permutations with a Prescribed Structure.

Moni Naor, Omer Reingold

J. Cryptol., 2002

Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.

Ran Raz, Omer Reingold, Salil P. Vadhan

J. Comput. Syst. Sci., 2002

Tight Bounds for Shared Memory Systems Accessed by Byzantine Processes.

Michael Merritt, Omer Reingold, Gadi Taubenfeld, Rebecca N. Wright

Proceedings of the Distributed Computing, 16th International Conference, 2002

Randomness conductors and constant-degree lossless expanders.

Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Streaming Computation of Combinatorial Objects.

Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Efficient, DoS-resistant, secure key exchange for internet protocols.

William Aiello, Steven M. Bellovin, Matt Blaze, John Ioannidis, Omer Reingold, Ran Canetti, Angelos D. Keromytis

Proceedings of the 9th ACM Conference on Computer and Communications Security, 2002

2001

Pseudo-Random Functions and Factoring

Moni Naor, Omer Reingold, Alon Rosen

Electron. Colloquium Comput. Complex., 2001

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

Omer Reingold, Salil P. Vadhan, Avi Wigderson

Electron. Colloquium Comput. Complex., 2001

On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates.

Yael Gertner, Tal Malkin, Omer Reingold

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Priced Oblivious Transfer: How to Sell Digital Goods.

William Aiello, Yuval Ishai, Omer Reingold

Proceedings of the Advances in Cryptology, 2001

2000

Extracting Randomness via Repeated Condensing

Omer Reingold, Ronen Shaltiel, Avi Wigderson

Electron. Colloquium Comput. Complex., 2000

Pseudo-random functions and factoring (extended abstract).

Moni Naor, Omer Reingold, Alon Rosen

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

The Relationship between Public Key Encryption and Oblivious Transfer.

Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited.

Moni Naor, Omer Reingold

J. Cryptol., 1999

Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions.

Moni Naor, Omer Reingold

J. Comput. Syst. Sci., 1999

Breaking Generalized Diffie-Hellmann Modulo a Composite is no Easier Than Factoring.

Eli Biham, Dan Boneh, Omer Reingold

Inf. Process. Lett., 1999

On Recycling the Randomness of States in Space Bounded Computation.

Ran Raz, Omer Reingold

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Error Reduction for Extractors.

Ran Raz, Omer Reingold, Salil P. Vadhan

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Distributed Pseudo-random Functions and KDCs.

Moni Naor, Benny Pinkas, Omer Reingold

Proceedings of the Advances in Cryptology, 1999

1998

Perfectly One-Way Probabilistic Hash Functions (Preliminary Version).

Ran Canetti, Daniele Micciancio, Omer Reingold

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).

Moni Naor, Omer Reingold

Proceedings of the Advances in Cryptology, 1998

1997

Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring

Eli Biham, Dan Boneh, Omer Reingold

Electron. Colloquium Comput. Complex., 1997

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

Moni Naor, Omer Reingold

Electron. Colloquium Comput. Complex., 1997

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract).

Moni Naor, Omer Reingold

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.

Moni Naor, Omer Reingold

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995