Academic Appointments


2024-25 Courses


Stanford Advisees


All Publications


  • Oracle Efficient Online Multicalibration and Omniprediction Garg, S., Jung, C., Reingold, O., Roth, A., Woodruff, D. P. SIAM. 2024: 2725-2792
  • 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
  • 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
  • Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers Hu, L., Reingold, O., Banerjee, A., Fukumizu, K. MICROTOME PUBLISHING. 2021
  • 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
  • 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

  • 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
  • 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
  • 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
  • Pseudorandom Generators for Width-3 Branching Programs Meka, R., Reingold, O., Tal, A., Charikar, M., Cohen, E. ASSOC COMPUTING MACHINERY. 2019: 626–37
  • Incremental Deterministic Public-Key Encryption JOURNAL OF CRYPTOLOGY Mironov, I., Pandey, O., Reingold, O., Segev, G. 2018; 31 (1): 134–61
  • Efficient Batch Verification for UP Reingold, O., Rothblum, G. N., Rothblum, R. D., Servedio, R. A. SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS. 2018
  • 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
  • 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
  • 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
  • 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