2021

Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, Keziah Naggita:
The Strategic Perceptron. EC 2021: 6-25

Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev:
Adversarial laws of large numbers and optimal regret in online classification. STOC 2021: 447-455

Shweta Agrawal, Shafi Goldwasser, Saleet Mossel: Deniable Fully Homomorphic Encryption from LWE will be published in CRYPTO 2021

Pranjal Awasthi, Alex Beutel, Matthäus Kleindessner, Jamie Morgenstern, Xuezhi Wang:
Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information. FAccT 2021: 206-214

Yahav Bechavod, Katrina Ligett, Zhiwei Steven Wu, Juba Ziani:
Gaming Helps! Learning from Strategic Interactions in Natural Dynamics. AISTATS 2021: 1234-1242

Multiparty Reusable Non-Interactive Secure Computation from LWE. Fabrice Benhamouda, Aayush Jain, Ilan Komargodski, Huijia Lin. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2021).

Avrim Blum, Paul Gölz:
Incentive-Compatible Kidney Exchange in a Slightly Semi-Random Model.EC 2021: 138-156

Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, Han Shao:
One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning. ICML 2021: 1005-1014

Avrim Blum, Shelby Heinecke, Lev Reyzin:
Communication-Aware Collaborative Learning. AAAI 2021: 6786-6793

Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Surbhi Goel, Anthimos Vardis Kandiros: Statistical Estimation from Dependent Data. In the 34th Annual Conference on Learning Theory (ICML), 2021.

Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Anthimos Vardis Kandiros: Learning Ising Models from One or Multiple Samples. In the 53rd ACM Symposium on Theory of Computing (STOC), 2021.

Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, Emmanouil Zampetakis: A Statistical Taylor Theorem and Extrapolation of Truncated Densities. In the 34th Annual Conference on Learning Theory (COLT), 2021.

Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis: The Complexity of Constrained Min-Max Optimization.
In the 53rd ACM Symposium on Theory of Computing (STOC), 2021.

Toward Better Generalization Bounds with Locally Elastic Stability Zhun Deng, Hangfeng He, Weijie J. Su, ICML 2021 (April)

Zhun Deng, Jiaoyang Huang, Kenji Kawaguchi The Role of Gradient Noise in the Optimization of Neural Networks, manuscript

Jelena Diakonikolas, Constantinos Daskalakis, Michael I. Jordan: Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization.
In the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.

Algorithms and Learning for Fair Portfolio Design. Emily Diana, Travis Dick, Hadi Elzayn, Michael Kearns, Aaron Roth, Zachary Schutzman, Saeed Sharifi-Malvajerdi, Juba Ziani. EC 2021

Lexicographically Fair Learning: Algorithms and Generalization. Emily Diana, Wesley Gill, Ira Globus-Harris, Michael Kearns, Aaron Roth, Saeed Sharifi-Malvajerdi. FORC 2021

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona. Outcome Indistinguishability. STOC 2021 (June), and in the non-archival track of the Foundations of Responsible Computing conference, 2021.

C. Dwork, W. Su, and L. Zhang, Differentially Private False Discovery Rate Control, to appear, J. Privacy and Confidentiality, 2021 (in copyediting)

C. Dwork and M. Minow, Trust and Distrust in Artificial Intelligence, to appear, Daedalus (Journal of the American Academy of Arts and Sciences), 2021

Talya Eden, Saleet Mossel, Ronitt, Rubinfeld: Sampling Multiple Edges Efficiently. Will be published in APPROX/RANDOM 2021

Vikas K. Garg, Adam Tauman Kalai, Katrina Ligett, Zhiwei Steven Wu:
Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalization. AISTATS 2021: 3574-3582

Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification. Romain Gay, Aayush Jain, Huijia Lin, Amit Sahai. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2021).

Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam:
On the Pseudo-Deterministic Query Complexity of NP Search Problems.Computational Complexity Conference 2021: 36:1-36:22

S. Goldwasser, G. N. Rothblum, J. Shafer and A. Yehudayoff, Interactive Proofs for Verifying Machine Learning. Innovations in Theoretical Computer Science conference (ITCS) 2021: 41:1-41:19.

Parikshit Gopalan, Omer Reingold, Vatsal Sharan, Udi Wieder:
Multicalibrated Partitions for Importance Weights. CoRR abs/2103.05853 (2021)

Oblivious Transfer is in MiniQCrypt. Alex B. Grilo, Huijia Lin, Fang Song, Vinod VaikuntanathanThe 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2021). 24th Annual Conference on Quantum Information Processing (QIP 2021). Plenary Talk at QIP 2021.

Ofer Grossman, Justin Holmgren, “Error Correcting Codes for Uncompressed Messages”, ITCS 2021

H. Heidari, S. Barocas, J. Kleinberg, K. Levy. On Modeling Human Perceptions of Allocation Policies with Uncertain Outcomes. Proc. 22nd ACM Conference on Economics and Computation (EC), 2021. Exemplary Applied Modeling Award at EC 2021.

H. Heidari, J. Kleinberg. Allocating Opportunities in a Dynamic Model of Intergenerational Mobility. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2021. Best CS Paper Award at FAccT 2021

Lunjia Hu, Omer Reingold:
Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers. AISTATS 2021: 1558-1566

Indistinguishability Obfuscation from Well-Founded Assumptions. Aayush Jain, Huijia Lin, Amit Sahai. The 53rd ACM Symposium on Theory of Computing (STOC 2021). Best Paper Award.

An Algorithmic Framework for Fairness Elicitation. Christopher Jung, Michael Kearns, Seth Neel, Aaron Roth, Logan Stapleton, Zhiwei Steven Wu. FORC 2021

Moment Multicalibration for Uncertainty Estimation. Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, Rakesh Vohra. COLT 2021.

Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, Moshe Shenfeld:
A new analysis of differential privacy’s generalization guarantees (invited paper). STOC 2021: 9

Kenji Kawaguchi, Linjun Zhang, Zhun Deng, Dynamics of Learning Nonlinear Representations in Supervised Learning, in submission.

J. Kleinberg, M. Raghavan. Algorithmic Monoculture and Social Welfare. Proc. National Academy of Sciences, 118(22), 1 June 2021.

James Lucas, Mengye Ren, Irene Raissa Kameni, Toniann Pitassi, Richard S. Zemel:
Theoretical bounds on estimation error for meta-learning. ICLR 2021

Boaz Menuhin, Moni Naor:
Keep That Card in Mind: Card Guessing with Limited Memory. Electron. Colloquium Comput. Complex. 28: 96 (2021)

Marcel Neunhoeffer, Zhiwei Steven Wu, and Cynthia Dwork, Private post-gan boosting, ICLR 2021 (November), 2007.11934.pdf (arxiv.org) and TPDP 2020 poster.

Pipeline Interventions. Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, Juba Ziani. ITCS 2021

G. N. Rothblum and Gal Yona, Multi-group Agnostic PAC Learnability. International Conference on Machine Learning (ICML) 2021: to appear.

How Does Mixup Help With Robustness and Generalization? Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, James Zou, ICLR 2021 (May), Spotlight, top 6% among submissions.

When and How Mixup Improves Calibration Linjun Zhang, Zhun Deng, Kenji Kawaguchi, James Zou. In submission.

2020

Pranjal Awasthi, Matthäus Kleindessner, Jamie Morgenstern:
Equalized odds postprocessing under imperfect group information. AISTATS 2020: 1770-1780

N. Barda, D. Riesel, A. Akriv, J. Levy, U. Finkel, G. Yona, D. Greenfeld, S. Sheiba, J. Somer, E. Bachmat, G. N. Rothblum, U. Shalit, D. Netzer, R. Balicer and N. Dagan, Developing a COVID-19 Mortality Risk Prediction Model when Individual-Level Data are Not Available. Nature Communications 11, 4439 (2020).

 N. Barda, G. Yona, G. N. Rothblum, P. Greenland, M. Leibowitz, R. Balicer, E. Bachmat and N. Dagan, Addressing Bias in Prediction Models by Improving Subpopulation Calibration. Journal of the American Medical Informatics Association (JAMIA). 28(3): 549-558 (2020).

Yahav Bechavod, Christopher Jung, Zhiwei Steven Wu (2020) Metric-Free Individual Fairness in Online Learning. NeurIPS 2020.

Avrim Blum, Technical perspective: Algorithm selection as a learning problem. Commun. ACM 63(6): 86 (2020)

Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, Ankit Sharma (2020). Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries. Oper. Res. 68(1): 16-34.

Avrim Blum, Thodoris Lykouris (2020). Advancing Subgroup Fairness via Sleeping Experts. ITCS: 55:1-55:24

Avrim Blum, Kevin Stangl (2020). Recovering from Biased Data: Can Fairness Constraints Improve Accuracy? FORC: 3:1-3:20

Yang Cai, Federico Echenique, Hu Fu, Katrina Ligett, Adam Wierman, Juba Ziani:
Third-Party Data Providers Ruin Simple Mechanisms. Proc. ACM Meas. Anal. Comput. Syst. 4(1): 12:1-12:31 (2020)

Alexandra Chouldechova, Aaron Roth (2020) A snapshot of the frontiers of fairness in machine learning. Commun. ACM 63(5): 82-89

A Theoretical View of Adversarial Domain Generalization in the Hierarchical Model Setting Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, Pragya Sur. In submission.

Interpreting Robust Optimization via Adversarial Influence Functions Zhun Deng, Cynthia Dwork, Jialiang Wang, Linjun Zhang,  ICML 2020.

Towards Understanding the Dynamics of the First-Order Adversaries  Zhun Deng, Hangfeng He, Jiaoyang Huang, Weijie J. Su,  ICML 2020.

Kenji Kawaguchi, Linjun Zhang, Zhun Deng, Dynamics of Learning Nonlinear Representations in Supervised Learning, in submission.

Kate Donahue, Jon M. Kleinberg (2020) Fairness and utilization in allocating resources with uncertain demand. FAT*: 658-668

C. Dwork and C. Ilvento, Consistent Integer, Non-Negative, Hierarchical Histograms without Integer Programming, TPDP (poster), November 2020. 

Cynthia Dwork, Christina Ilvento, Meena Jagadeesan (2020) Individual Fairness in Pipelines. FORC: 7:1-7:22

Cynthia Dwork, Christina Ilvento, Guy N. Rothblum, Pragya Sur (2020) Abstracting Fairness: Oracles, Metrics, and Interpretability. FORC: 8:1-8:16

Sanjam Garg, Shafi Goldwasser, Prashant Nalini Vasudevan:
Formalizing Data Deletion in the Context of the Right to Be Forgotten. EUROCRYPT (2) 2020: 373-402

Amirata Ghorbani, Michael P. Kim, James Zou. A Distributional Framework for Data Valuation. ICML 2020.

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-Deterministic Streaming. ITCS 2020

Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, Omar Montasser:
Identifying unpredictable test examples with worst-case guarantees. ITA 2020: 1-14

Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, Omar Montasser:
Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples. NeurIPS 2020

Ofer Grossman, Justin Holmgren, Eylon Yogev, “Transparent Error Correcting in a Computationally Bounded World”, TCC 2020

Andrew Ilyas, Emmanouil Zampetakis, Constantinos Daskalakis (2020) A Theoretical and Practical Framework for Regression and Classification from Truncated Samples. AISTATS: 4463-4473

Christopher Jung, Sampath Kannan, Changhwa Lee, Mallesh M. Pai, Aaron Roth, Rakesh Vohra (2020) Fair Prediction with Endogenous Behavior. EC: 677-678

Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, Uri Stemmer:
Privately Learning Thresholds: Closing the Exponential Gap. COLT 2020: 2263-2285

Michael P. Kim, Aleksandra Korolova, Guy N. Rothblum, Gal Yona (2020) Preference-informed fairness. FAT*: 546

Michael P. Kim, Aleksandra Korolova, Guy N. Rothblum, Gal Yona (2020) Preference-informed fairness. ITCS: 16:1-16:23

Margaret Mitchell, Dylan Baker, Nyalleng Moorosi, Emily Denton, Ben Hutchinson, Alex Hanna, Timnit Gebru, Jamie Morgenstern:
Diversity and Inclusion Metrics in Subset Selection. AIES 2020: 117-123

Moni Naor, Neil Vexler:
Can Two Walk Together: Privacy Enhancing Methods and Preventing Tracking of Users. FORC 2020: 4:1-4:20

Manish Raghavan, Solon Barocas, Jon M. Kleinberg, Karen Levy (2020) Mitigating bias in algorithmic hiring: evaluating claims and practices. FAT*: 469-481

G. N. Rothblum and R. D. Rothblum, Batch Verification and Proofs of Proximity with Polylog Overhead. Theory of Cryptography Conference (TCC) (2) 2020: 108-138.

Aditya Saraf, Anna R. Karlin, Jamie Morgenstern:
Competition Alleviates Present Bias in Task Completion.WINE 2020: 266-279

Decision-Aware Conditional GANs for Time Series Data He Sun, Zhun Deng, Hui Chen, David Parkes Manuscript

Shavit, Y., Edelman, B., & Axelrod, B. (2020, November). Causal strategic linear regression. In International Conference on Machine Learning (pp. 8676-8686). PMLR. Causal Strategic Linear Regression (mlr.press)

Selected earlier publications

Rediet Abebe, Jon M. Kleinberg, David C. Parkes (2017) Fair Division via Social Comparison. AAMAS: 281-289

Amihood Amir, Oren Kapah, Tsvi Kopelowitz, Moni Naor, Ely Porat (2016) The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets. SPAA: 367-375

Yahav Bechavod, Katrina Ligett, Aaron Roth, Bo Waggoner, Steven Z. Wu (2019) Equal Opportunity in Online Classification with Partial Feedback. NeurIPS: 8972-8982

Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis (2018) Efficient Statistics, in High Dimensions, from Truncated Samples. FOCS: 639-649

Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis (2019) Computationally and Statistically Efficient Truncated Regression. COLT: 955-960

Cynthia Dwork (2017) What’s Fair? KDD: 1

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel (2012) Fairness through awareness. ITCS: 214-226

Cynthia Dwork, Christina Ilvento (2019) Fairness Under Composition. ITCS: 33:1-33:20

Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, Mark D. M. Leiserson (2018) Decoupled Classifiers for Group-Fair and Efficient Machine Learning. FAT: 119-133

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona (2019) Learning from Outcomes: Evidence-Based Rankings. FOCS: 106-125

Hadi Elzayn, Shahin Jabbari, Christopher Jung, Michael J. Kearns, Seth Neel, Aaron Roth, Zachary Schutzman (2019) Fair Algorithms for Learning in Allocation Problems. FAT: 170-179

Sumegha Garg, Michael P. Kim, Omer Reingold (2019) Tracking and Improving Information in the Service of Fairness. EC: 809-824

Stephen Gillen, Christopher Jung, Michael J. Kearns, Aaron Roth (2018) Online Learning with an Unknown Fairness Metric. NeurIPS: 2605-2614

Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum (2018) Multicalibration: Calibration for the (Computationally-Identifiable) Masses. ICML: 1944-1953

Nicole Immorlica, Katrina Ligett, and Juba Ziani (2019) Access to Population-Level Signaling as a Source of Inequality. FAT*

Shahin Jabbari, Matthew Joseph, Michael J. Kearns, Jamie Morgenstern, Aaron Roth (2017) Fairness in Reinforcement Learning. ICML: 1617-1626

Matthew Jagielski, Michael J. Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, Jonathan Ullman (2019) Differentially Private Fair Learning. ICML: 3000-3008

Matthew Joseph, Michael J. Kearns, Jamie Morgenstern, Seth Neel, Aaron Roth (2018) Meritocratic Fairness for Infinite and Contextual Bandits. AIES: 158-163

Matthew Joseph, Michael J. Kearns, Jamie H. Morgenstern, Aaron Roth (2016) Fairness in Learning: Classic and Contextual Bandits. NIPS: 325-333

Sampath Kannan, Michael J. Kearns, Jamie Morgenstern, Mallesh M. Pai, Aaron Roth, Rakesh V. Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, Nati Srebro (2018) On preserving non-discrimination when combining expert advice. NeurIPS: 8386-8397 EC 2017: 369-386

Sampath Kannan, Aaron Roth, Juba Ziani (2019) Downstream Effects of Affirmative Action. FAT: 240-248

Michael J. Kearns, Seth Neel, Aaron Roth, Zhiwei Steven Wu (2018) Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness. ICML: 2569-2577

Michael J. Kearns, Seth Neel, Aaron Roth, Zhiwei Steven Wu (2019) An Empirical Study of Rich Subgroup Fairness for Machine Learning. FAT: 100-109

Michael P. Kim, Omer Reingold, Guy N. Rothblum (2018) Fairness Through Computationally-Bounded Awareness. NeurIPS: 4847-4857

Jon M. Kleinberg (2018) Inherent Trade-Offs in Algorithmic Fairness. SIGMETRICS (Abstracts): 40

Jon M. Kleinberg, Sendhil Mullainathan (2019) Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability. EC: 807-808

Jon M. Kleinberg, Sendhil Mullainathan, Manish Raghavan (2017) Inherent Trade-Offs in the Fair Determination of Risk Scores. ITCS: 43:1-43:23

Jon M. Kleinberg, Sigal Oren, Manish Raghavan (2016) Planning Problems for Sophisticated Agents with Present Bias. EC: 343-360

Jon M. Kleinberg, Sigal Oren, Manish Raghavan (2017) Planning with Multiple Biases. EC: 567-584

Jon M. Kleinberg, Manish Raghavan (2018) Selection Problems in the Presence of Implicit Bias. ITCS: 33:1-33:17

Moni Naor. (2005) On fairness in the carpool problem. J. Algorithms 55(1): 93-98

Geoff Pleiss, Manish Raghavan, Felix Wu, Jon M. Kleinberg, Kilian Q. Weinberger (2017) On Fairness and Calibration. NIPS: 5680-5689

Saeed Sharifi-Malvajerdi, Michael J. Kearns, Aaron Roth (2019) Average Individual Fairness: Algorithms, Generalization and Experiments. NeurIPS: 8240-8249

Gal Yona, Guy N. Rothblum (2018) Probably Approximately Metric-Fair Learning. ICML: 5666-5674

Richard S. Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, Cynthia Dwork (2013) Learning Fair Representations. ICML (3): 325-333