Omer Reingold
Rajeev Motwani Professor of Computer Science
2024-25 Courses
- Departmental Lecture Series
CS 300 (Aut) - Introduction to the Theory of Computation
CS 154 (Aut) - Playback Theater
CS 83N (Aut) -
Independent Studies (12)
- Advanced Reading and Research
CS 499 (Aut, Win, Spr) - Advanced Reading and Research
CS 499P (Aut, Win, Spr) - Curricular Practical Training
CS 390A (Aut, Win, Spr) - Curricular Practical Training
CS 390B (Aut, Win, Spr) - Curricular Practical Training
CS 390C (Aut, Win, Spr) - Independent Project
CS 399 (Aut, Win, Spr) - Independent Work
CS 199 (Aut, Win, Spr) - Independent Work
CS 199P (Aut, Win, Spr) - Part-time Curricular Practical Training
CS 390D (Aut, Win, Spr) - Senior Honors Thesis
MATH 197 (Win, Spr) - Senior Project
CS 191 (Aut, Win, Spr) - Writing Intensive Senior Research Project
CS 191W (Aut, Win, Spr)
- Advanced Reading and Research
-
Prior Year Courses
2023-24 Courses
- Algorithmic Fairness
CS 256 (Win) - Departmental Lecture Series
CS 300 (Aut) - Introduction to the Theory of Computation
CS 154 (Aut) - Playback Theater
CS 83N (Win)
2022-23 Courses
- Algorithmic Fairness
CS 256 (Win) - Departmental Lecture Series
CS 300 (Aut) - Introduction to the Theory of Computation
CS 154 (Aut) - Playback Theater
CS 83N (Win)
2021-22 Courses
- Departmental Lecture Series
CS 300 (Aut) - Introduction to the Theory of Computation
CS 154 (Aut) - Playback Theater
CS 83 (Win) - The Practice of Theory Research
CS 163 (Win)
- Algorithmic Fairness
Stanford Advisees
-
Doctoral Dissertation Reader (AC)
Victor Lecomte -
Postdoctoral Faculty Sponsor
Lee Cohen -
Master's Program Advisor
Myra Deng, Anicet Dushime Wa Mungu, Anne Li, Jerry Tang, Haven Whitney, Luna Yang, Alan Zhang -
Doctoral (Program)
Jabari Hastings, Charlotte Peale, Judy Hanwen Shen
All Publications
-
Oracle Efficient Online Multicalibration and Omniprediction
SIAM. 2024: 2725-2792
View details for Web of Science ID 001267398705014
-
Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration
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
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
2021; 17
View details for DOI 10.4086/toc.2021.v017a004
View details for Web of Science ID 000702767600002
-
Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
MICROTOME PUBLISHING. 2021
View details for Web of Science ID 000659893801087
-
Outcome Indistinguishability
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
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
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
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
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
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
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
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
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
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
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
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018
View details for Web of Science ID 000461823304082
-
Guilt-Free Data Reuse
COMMUNICATIONS OF THE ACM
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
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
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
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
1999; 70 (2): 83-87
View details for Web of Science ID 000080904300006