Omer Reingold
According to our database^{1},
Omer Reingold
authored at least 96 papers
between 1995 and 2019.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2014, "For contributions to the study of pseudorandomness, derandomization, and cryptography.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at viaf.org

at id.loc.gov

at dl.acm.org
On csauthors.net:
Bibliography
2019
Learning from Outcomes: EvidenceBased 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 PublicKey Encryption.
J. Cryptology, 2018
Efficient Batch Verification for UP.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Pseudorandom Generators for Width3 Branching Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2018
On the Communication Complexity of KeyAgreement Protocols.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Fairness Through ComputationallyBounded Awareness.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
Multicalibration: Calibration for the (ComputationallyIdentifiable) 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 (ComputationallyIdentifiable) Masses.
CoRR, 2017
Guiltfree 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
ConstantRound 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 CondorcetBased Stopping Rules Can Be Efficient.
Proceedings of the ECAI 2016  22nd European Conference on Artificial Intelligence, 29 August2 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 FortySeventh 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
ST connectivity on digraphs with a known stationary distribution.
ACM Trans. Algorithms, 2011
The Limits of TwoParty 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 (EC2011), 2011
2010
Universal OneWay 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 Oneway 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 ZeroKnowledge Arguments from Any OneWay 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 kWise (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 logspace.
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 StatisticallyHiding 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 TwoParty Secure Computation: A Computational View.
J. Cryptology, 2006
StatisticallyHiding Commitment from Any OneWay Function.
IACR Cryptology ePrint Archive, 2006
Derandomized Constructions of kWise (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 OneWay 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
Numbertheoretic constructions of efficient pseudorandom functions.
J. ACM, 2004
Undirected STConnectivity in LogSpace
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 PseudoRandom 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 constantdegree 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, DoSresistant, secure key exchange for internet protocols.
Proceedings of the 9th ACM Conference on Computer and Communications Security, 2002
2001
PseudoRandom Functions and Factoring
Electronic Colloquium on Computational Complexity (ECCC), 2001
Entropy Waves, the ZigZag Graph Product, and New ConstantDegree 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
Pseudorandom functions and factoring (extended abstract).
Proceedings of the ThirtySecond 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: LubyRackoff Revisited.
J. Cryptology, 1999
Synthesizers and Their Application to the Parallel Construction of PseudoRandom Functions.
J. Comput. Syst. Sci., 1999
Breaking Generalized DiffieHellmann 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 ThirtyFirst 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 Pseudorandom Functions and KDCs.
Proceedings of the Advances in Cryptology, 1999
1998
Perfectly OneWay 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 PseudoRandom Functions from MACs (Extended Abstract).
Proceedings of the Advances in Cryptology, 1998
1997
Generalized DiffieHellman Modulo a Composite is not Weaker than Factoring
Electronic Colloquium on Computational Complexity (ECCC), 1997
On the Construction of PseudoRandom Permutations: LubyRackoff Revisited
Electronic Colloquium on Computational Complexity (ECCC), 1997
On the Construction of PseudoRandom Permutations: LubyRackoff Revisited (Extended Abstract).
Proceedings of the TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
1995
Synthesizers and Their Application to the Parallel Construction of PsuedoRandom Functions.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995