Omer Reingold

All Publications

• Dissenting Explanations: Leveraging Disagreement to Reduce Model Overreliance Reingold, O., Shen, J., Talati, A., Wooldridge, M., Dy, J., Natarajan, S. ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE. 2024: 21537-21544

  View details for Web of Science ID 001239984900072

• Oracle Efficient Online Multicalibration and Omniprediction Garg, S., Jung, C., Reingold, O., Roth, A., Woodruff, D. P. SIAM. 2024: 2725-2792

  View details for Web of Science ID 001267398705014

• Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration Gopalan, P., Kim, M. P., Reingold, O., Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023

  View details for Web of Science ID 001229826601014

• Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences of the United States of America Kim, M. P., Kern, C., Goldwasser, S., Kreuter, F., Reingold, O. 1800; 119 (4)

  Abstract

  The gold-standard approaches for gleaning statistically valid conclusions from data involve random sampling from the population. Collecting properly randomized data, however, can be challenging, so modern statistical methods, including propensity score reweighting, aim to enable valid inferences when random sampling is not feasible. We put forth an approach for making inferences based on available data from a source population that may differ in composition in unknown ways from an eventual target population. Whereas propensity scoring requires a separate estimation procedure for each different target population, we show how to build a single estimator, based on source data alone, that allows for efficient and accurate estimates on any downstream target data. We demonstrate, theoretically and empirically, that our target-independent approach to inference, which we dub "universal adaptability," is competitive with target-specific approaches that rely on propensity scoring. Our approach builds on a surprising connection between the problem of inferences in unspecified target populations and the multicalibration problem, studied in the burgeoning field of algorithmic fairness. We show how the multicalibration framework can be employed to yield valid inferences from a single source population across a diverse set of target populations.

  View details for DOI 10.1073/pnas.2108097119

  View details for PubMedID 35046023

• Deterministic Approximation of Random Walks in Small Space THEORY OF COMPUTING Murtagh, J., Reingold, O., Sidford, A., Vadhan, S. 2021; 17

  View details for DOI 10.4086/toc.2021.v017a004

  View details for Web of Science ID 000702767600002

• Outcome Indistinguishability Dwork, C., Kim, M. P., Reingold, O., Rothblum, G. N., Yona, G., Khuller, S., Williams, V. V. ASSOC COMPUTING MACHINERY. 2021: 1095-1108

  View details for DOI 10.1145/3406325.3451064

  View details for Web of Science ID 000810492500097

• DERANDOMIZATION BEYOND CONNECTIVITY: UNDIRECTED LAPLACIAN SYSTEMS IN NEARLY LOGARITHMIC SPACE SIAM JOURNAL ON COMPUTING Murtagh, J., Reingold, O., Sidford, A., Vadhan, S. 2021; 50 (6): 1892-1922

  View details for DOI 10.1137/20M134109X

  View details for Web of Science ID 000748782500005

• CONSTANT-ROUND INTERACTIVE PROOFS FOR DELEGATING COMPUTATION SIAM JOURNAL ON COMPUTING Reingold, O., Rothblum, G. N., Rothblum, R. D. 2021; 50 (3)

  View details for DOI 10.1137/16M1096773

  View details for Web of Science ID 000674143400005

• Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers Hu, L., Reingold, O., Banerjee, A., Fukumizu, K. MICROTOME PUBLISHING. 2021

  View details for Web of Science ID 000659893801087

• Inaccessible Entropy II: IE Functions and Universal One-Way Hashing THEORY OF COMPUTING Haitner, I., Holenstein, T., Reingold, O., Vadhan, S., Wee, H. 2020; 16

  View details for DOI 10.4086/toc.2020.v016a008

  View details for Web of Science ID 000576957900001

• Through the Lens of a Passionate Theoretician COMMUNICATIONS OF THE ACM Reingold, O. 2020; 63 (3): 25–27

  View details for DOI 10.1145/3378543

  View details for Web of Science ID 000582584200014

• Learning from Outcomes: Evidence-Based Rankings Dwork, C., Kim, M. P., Reingold, O., Rothblum, G. N., Yona, G., IEEE IEEE COMPUTER SOC. 2019: 106–25

  View details for DOI 10.1109/FOCS.2019.00016

  View details for Web of Science ID 000510015300007

• Tracking and Improving Information in the Service of Fairness Garg, S., Kim, M. P., Reingold, O., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2019: 809–24

  View details for DOI 10.1145/3328526.3329624

  View details for Web of Science ID 000483848100096

• Pseudorandom Generators for Width-3 Branching Programs Meka, R., Reingold, O., Tal, A., Charikar, M., Cohen, E. ASSOC COMPUTING MACHINERY. 2019: 626–37

  View details for DOI 10.1145/3313276.3316319

  View details for Web of Science ID 000523199100057

• Incremental Deterministic Public-Key Encryption JOURNAL OF CRYPTOLOGY Mironov, I., Pandey, O., Reingold, O., Segev, G. 2018; 31 (1): 134–61

  View details for DOI 10.1007/s00145-017-9252-1

  View details for Web of Science ID 000419451900005

• Efficient Batch Verification for UP Reingold, O., Rothblum, G. N., Rothblum, R. D., Servedio, R. A. SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS. 2018

  View details for DOI 10.4230/LIPIcs.CCC.2018.22

  View details for Web of Science ID 000495013500022

• Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity Chattopadhyay, E., Hatami, P., Reingold, O., Tal, A., Diakonikolas, Kempe, D., Henzinger, M. ASSOC COMPUTING MACHINERY. 2018: 363–75

  View details for DOI 10.1145/3188745.3188800

  View details for Web of Science ID 000458175600034

• Fairness Through Computationally-Bounded Awareness Kim, M. P., Reingold, O., Rothblum, G. N., Bengio, S., Wallach, H., Larochelle, H., Grauman, K., CesaBianchi, N., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018

  View details for Web of Science ID 000461823304082

• Guilt-Free Data Reuse COMMUNICATIONS OF THE ACM Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A. 2017; 60 (4): 86-93

  View details for DOI 10.1145/3051088

  View details for Web of Science ID 000398920900029

• Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space Murtagh, J., Reingold, O., Sidford, A., Vadhan, S., IEEE IEEE. 2017: 801–12

  View details for DOI 10.1109/FOCS.2017.79

  View details for Web of Science ID 000417425300070

• FINDING COLLISIONS IN INTERACTIVE PROTOCOLS-TIGHT LOWER BOUNDS ON THE ROUND AND COMMUNICATION COMPLEXITIES OF STATISTICALLY HIDING COMMITMENTS SIAM JOURNAL ON COMPUTING Haitner, I., Hoch, J. J., Reingold, O., Segev, G. 2015; 44 (1): 193-242

  View details for DOI 10.1137/130938438

  View details for Web of Science ID 000353967100007

• BALLS AND BINS: SMALLER HASH FAMILIES AND FASTER EVALUATION SIAM JOURNAL ON COMPUTING Celis, L. E., Reingold, O., Segev, G., Wieder, U. 2013; 42 (3): 1030-1050

  View details for DOI 10.1137/120871626

  View details for Web of Science ID 000323888700009

• Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring INFORMATION PROCESSING LETTERS Biham, E., Boneh, D., Reingold, O. 1999; 70 (2): 83-87

  View details for Web of Science ID 000080904300006