Home Page for Professor Michael Kearns, University of Pennsylvania

MICHAEL KEARNS
Professor and National Center Chair
Department of Computer and Information Science at the University of Pennsylvania
Founding Director, Warren Center for Network and Data Sciences
Founder and former Director, Penn program in Networked and Social Systems Engineering
Secondary Appointments in Economics, Statistics and Data Science (Wharton) and Operations, Information and Decisions (Wharton)

Mailing Address: 509 Levine Hall, 3330 Walnut Street, Philadelphia, PA 19104-6389
Phone: 215.898.7888
3401 Walnut office: 404B
Email: mkearns@cis.upenn.edu
Amazon Email: kearmic@amazon.com
Twitter: @mkearnsupenn

Admin Support, Warren Center and NETS Program Manager and Social Media Outreach:
Lily Hoot
Phone: 215.573.0861
Email: lhoot@seas.upenn.edu

RESEARCH INTERESTS

My research interests include topics in machine learning, artificial intelligence, algorithmic game theory and microeconomics, computational social science, and quantitative finance and algorithmic trading. I often examine problems in these areas using methods and models from theoretical computer science and related disciplines. While much of my work is mathematical in nature, I also often participate in empirical and experimental projects, including applications of machine learning to problems in algorithmic trading and quantitative finance, and human-subject experiments on strategic and economic interaction in social networks.

SITE DIRECTORY

For (in)convenience, most of this site is organized as a single flat html file. The links below let you navigate directly to the various subsections.

Publications Research Group Members Teaching and Tutorial Material Professional Bio Educational Background Editorial and Professional Service Press

Aaron Roth and I have written a general-audience book about the science of designing algorithms that embed social values like privacy and fairness; here is the publisher's description:

Over the course of a generation, algorithms have gone from mathematical abstractions to powerful mediators of daily life. Algorithms have made our lives more efficient, more entertaining, and, sometimes, better informed. At the same time, complex algorithms are increasingly violating the basic rights of individual citizens. Allegedly anonymized datasets routinely leak our most sensitive personal information; statistical models for everything from mortgages to college admissions reflect racial and gender bias. Meanwhile, users manipulate algorithms to "game" search engines, spam filters, online reviewing services, and navigation apps.

Understanding and improving the science behind the algorithms that run our lives is rapidly becoming one of the most pressing issues of this century. Traditional fixes, such as laws, regulations and watchdog groups, have proven woefully inadequate. Reporting from the cutting edge of scientific research, The Ethical Algorithm offers a new approach: a set of principled solutions based on the emerging and exciting science of socially aware algorithm design. Michael Kearns and Aaron Roth explain how we can better embed human principles into machine code - without halting the advance of data-driven scientific exploration. Weaving together innovative research with stories of citizens, scientists, and activists on the front lines, The Ethical Algorithm offers a compelling vision for a future, one in which we can better protect humans from the unintended impacts of algorithms while continuing to inspire wondrous advances in technology.

Here are links to some media related to the book:

A review in Nature.

A review/summary in strategy+business.

A policy briefing for the Brookings Institution on technology regulatory implications.

A talk video filmed at the Carnegie Council for Ethics in International Affairs in NYC, along with a full transcript and slides.

A Penn podcast in which we discuss some of the book's topics.

A piece on the book on NPR Marketplace Morning Report.

Interview on WHYY's Radio Times (at 32 minute mark) November 2019.

An excerpt from the book in Penn Today.

An opinion piece adapted from book themes in Scientific American.

QUICK LINKS

Teaching Fall 2024: CIS 6250, Theory of Machine Learning.
Teaching Spring 2024: CIS 4230/5230, Ethical Algorithm Design.
Warren Center for Network and Data Sciences
Networked and Social Systems Engineering (NETS) Program
Penn undergraduate course Networked Life (NETS 112), Fall 2019 and a condensed video version.
Penn-Lehman Automated Trading Project (inactive)
Tribute Day for Les Valiant, May 2009

Videos of some miscellaneous talks:

"The Ethical Algorithm" (University of Washington, 2019 Taskar Memorial Lecture, general audience)

"The Ethical Algorithm" (Centre for Ethics, University of Toronto 2019, general audience)

"Machine Learning and Social Norms" (Santa Fe Institute 2017, general audience)

Panel discussion on privacy policy and regulation (AT&T Forum 2017, general audience)

"Fair Algorithms for Machine Learning" (ACM EC 2017, technical)

"Games, Networks and People" (NIPS 2014, technical)

"The Complexity of Economics" (Santa Fe Institute 2017; general audience)

"Algorithmic Trading: The Machine Learning Approach", (Quantcon 2015, technical)

BRIEF PROFESSIONAL BIO

Current:

Since 2002 I have been a professor in the Computer and Information Science Department at the University of Pennsylvania, where I hold the National Center Chair. I have secondary appointments in the department of Economics, and in the departments of Statistics and Data Science and Operations, Information and Decisions (OID) in the Wharton School. I am the Founding Director of the Warren Center for Network and Data Sciences, where my Co-Director is Rakesh Vohra. I am the faculty founder and former director of Penn Engineering's Networked and Social Systems Engineering (NETS) Program, whose current directors are Andreas Haeberlen and Aaron Roth. I am a faculty affiliate in Penn's Applied Math and Computational Science graduate program. Until July 2006 I was the co-director of Penn's interdisciplinary Institute for Research in Cognitive Science.

Since June 2020, I have been an Amazon Scholar, focusing on fairness, privacy and other "responsible AI" topics within Amazon Web Services.

I have worked extensively in quantitative and algorithmic trading on Wall Street (including at Lehman Brothers, Bank of America, SAC Capital and Morgan Stanley; see further details below). I often serve as an advisor to technology companies and venture capital firms, and sometimes invest in early-stage technology startups. I occasionally serve as an expert witness or consultant on technology-related legal and regulatory cases.

I am an elected Member/Fellow of the National Academy of Sciences, the American Academy of Arts and Sciences, the Association for Computing Machinery, the Association for the Advancement of Artificial Intelligence, and the Society for the Advancement of Economic Theory.

The Past:

I spent the decade 1991-2001 in machine learning and AI research at AT&T Bell Labs. (Here is an epic photo of Labs staff from 1995, there are many famous scientists peppered throughout.) During my last four years there, I was the head of the AI department, which conducted a broad range of systems and foundational AI work; I also served briefly as the head of the Secure Systems Research department. The AI department boasted terrific colleagues and friends that included Charles Isbell (now at Georgia Tech), Diane Litman (now at University of Pittsburgh), Michael Littman (later at Rutgers, now at Brown), David McAllester (now at TTI-Chicago), Satinder Singh (now at University of Michigan), Peter Stone (now at University of Texas), and Rich Sutton (now at University of Alberta). Prior to my time as its head, the AI department was shaped by the efforts of a number of notable figures, including Ron Brachman (who originally founded the department; now at Cornell Tech), Henry Kautz (who led the department before heading to the University of Washington; now at the University of Rochester), and Bart Selman (now at Cornell). Before leading the AI group, I was a member of the closely related Machine Learning department at the labs, which was headed by Fernando Pereira (later at Penn, now at Google), and included Michael Collins (later at MIT and Columbia, now at Google), Sanjoy Dasgupta (now at UCSD), Yoav Freund (now at UCSD), Rob Schapire (later at Princeton, now at Microsoft Research), William Cohen (now at CMU), and Yoram Singer (later at Hebrew University and Google, now at Princeton). Other friends and colleagues from Labs days include Sebastian Seung (later at MIT, now at Princeton), Lawrence Saul (later at Penn, now at UCSD), Yann LeCun (now at Facebook and NYU), Roberto Pieraccini (now at Jibo), Esther Levin (now at Point72), Lyn Walker (now at UC Santa Cruz), Corinna Cortes (now at Google), and Vladimir Vapnik (now at Facebook).

I spent 2001 as CTO of the European venture capital firm Syntek Capital, and joined the Penn faculty in January 2002.

From June 2018 to June 2020, I led applied research in the AI Center of Excellence at Morgan Stanley, along with Yuriy Nevmyvaka (with whom I have also collaborated on a number of papers on algorithmic trading ).

From June 2016 to March of 2018, I was the Chief Scientist of MANA Partners, a trading, technology and asset management firm based in NYC. From early 2014 to June 2016, I led a quantitative portfolio management team with Yuriy Nevmyvaka at Engineers Gate. From June 2009 through September 2013, we were PMs in the MultiQuant division of SAC Capital in New York City. From May 2007 through April 2009, we led a quantitative trading team at Bank of America in New York City, working on both proprietary and algorithmic trading strategies within BofA's Electronic Trading Services division. From the Spring of 2002 through May 2007, I was first a consultant to, and later the head of, a quant prop trading team within the Equity Strategies group of Lehman Brothers in New York City.

I spent most of 2011 on sabbatical in Cambridge, England, where I visited the University of Cambridge Economics Department and was a visiting Fellow at Christ's College. I also spent time visiting Microsoft Research Cambridge.

I have served as an advisor to the startups Yodle (acquired by web.com), Wealthfront, Activate Networks, RootMetrics (acquired by IHS), Convertro (acquired by AOL), Invite Media (acquired by Google), SiteAdvisor (founded by Chris Dixon; acquired by McAfee), PayNearMe (formerly known as Kwedit), and Riverhead Networks (acquired by Cisco). I was also involved in Dixon's startup Hunch (acquired by eBay), and have been a consultant to Bessemer Venture Partners.

In the past I have served as a member of the Advanced Technology Advisory Council of PJM Interconnection. the Scientific Advisory Board of Opera Solutions, and the Technical Advisory Board of Microsoft Research Cambridge. I am a former member of the Scientific Advisory Board of the Alan Turing Institute, and of the Market Surveillance Advisory Group of FINRA, and a former external faculty member at the Santa Fe Institute.

EDUCATION

I did my undergraduate studies at the University of California at Berkeley in math and computer science, graduating in 1985. I received a Ph.D. in computer science from Harvard University in 1989. The title of my dissertation was The Computational Complexity of Machine Learning (see Publications below for more information), and Les Valiant was my (superb) advisor. Following postdoctoral positions at the Laboratory for Computer Science at M.I.T. (hosted by Ron Rivest ) and at the International Computer Science Institute (ICSI) in Berkeley (hosted by Dick Karp ), in 1991 I joined the research staff of AT&T Bell Labs, and later the Penn faculty (see professional bio above).

Alongside my formal education, I was strongly influenced by being raised in an academic family, which included my father David R. Kearns (UCSD, Chemistry); his brother, and my uncle Thomas R. Kearns (Amherst College, Philosophy); their father, and my paternal grandfather, Clyde W. Kearns (University of Illinois, Entomology); my mother Alice Chen Kearns, who was an early influence on my writing; and her father, and my maternal grandfather Chen Shou-Yi (Pomona College, Chinese History and Literature).

EDITORIAL AND PROFESSIONAL SERVICE

In the past I have been program chair or co-chair of ACM FAccT, NIPS, AAAI, COLT, and ACM EC. I have also served on the program committees of NIPS, AAAI, IJCAI, COLT, UAI, ICML, STOC, FOCS, and a variety of other acryonyms. I am a member of the NIPS Foundation, and was formerly on the steering committee for the Snowbird Conference on Learning (RIP).

I am currently on the editorial board of the Proceedings of the National Academy of Sciences.

I am currently/recently on the editorial boards of the MIT Press series on Adaptive Computation and Machine Learning, and the journals PNAS Nexus and Market Microstructure and Liquidity.

In the past I have served on the editorial boards of Games and Economic Behavior, the Journal of the ACM, SIAM Journal on Computing, Machine Learning, the Journal of AI Research, and the Journal of Machine Learning Research.

I serve as a member and current chair of the ACM A.M. Turing Award Committee.

I am currently a member of the Emerging Technology Technical Advisory Committee of the U.S. Department of Commerce.

I am a former member of the Computer Science and Telecommunications Board of the National Academies. From 2002-2008 I was a member, vice chair and chair of DARPA's Information Science and Technology (ISAT) study group.

RESEARCH GROUP

Current (alphabetical):

Postdoc Yahav Bechavod (hosted by Aaron Roth )
Doctoral student Natalie Collina (jointly advised with Aaron Roth )
Doctoral student Ira Globus-Harris (jointly advised with Aaron Roth )
Doctoral student Varun Gupta (jointly advised with Aaron Roth )
Doctoral student Georgy Noarov (jointly advised with Aaron Roth )
Doctoral student Mirah Shi (jointly advised with Aaron Roth )
Doctoral student Sikata Sengupta (jointly advised with Aaron Roth and Duncan Watts )

Alumni (reverse chronological):

Former postdoc Jess Sorrell, now on the Johns Hopkins faculty
Former doctoral student Alexander Tolbert, now on the Emory University faculty
Former Masters student Declan Harrison, now an officer in the U.S. Navy
Former doctoral student Emily Diana, now on the research faculty at TTI Chicago, then joining CMU faculty
Former doctoral student Saeed Sharifi-Malvajerdi, now on the research faculty at TTI Chicago
Former doctoral student Chris Jung, now a postdoc at Stanford
Former Warren Center postdoc Travis Dick, now at Google Research NYC
Former Warren Center postdoc Juba Ziani, now on the Georgia Tech faculty
Former doctoral student Hadi Elzayn , now a research scientist at Meta/Facebook
Former doctoral student Seth Neel, now on the Harvard Business School faculty
Former doctoral student Shahin Jabbari, now on the Drexel faculty
Former Warren Center postdoc Jieming Mao, now at Google Research NYC
Former Warren Center postdoc Bo Waggoner, now on the University of Colorado faculty
Former Warren Center postdoc Jamie Morgenstern, now on the University of Washington faculty
Former doctoral student Steven Wu, now on the CMU faculty
Former doctoral student Hoda Heidari, now on the CMU faculty
Former doctoral student Ryan Rogers, now at LinkedIn
Former Warren Center postdoc Grigory Yaroslavtsev, now on the George Mason University faculty
Former graduate student Lili Dworkin now at Recidiviz
Former doctoral student Kareem Amin, now at Google Research NYC
Former research scientist Stephen Judd
Former doctoral student Mickey Brautbar, now at Shipt
Former postdoc Jake Abernethy, now on the Georgia Tech faculty
Former postdoc Karthik Sridharan, now on the Cornell faculty
Former postdoc Kris Iyer, now on the Cornell faculty
Former MD/PhD student Renuka Nayak, now on the UCSF faculty
Former doctoral student Tanmoy Chakraborty, now at Facebook
Former postdoc Umar Syed, now at Google Research NYC
Former doctoral student Jinsong Tan, now at Square
Former postdoc Eugene Vorobeychik, now on the Washington University faculty
Former postdoc Giro Cavallo, now at Yahoo! NYC
Former doctoral student Jenn Wortman Vaughan, now at Microsoft Research NYC
Former postdoc Eyal Even-Dar, now at Final Israel
Former doctoral student Sid Suri, now at Microsoft Research NYC
Former postdoc Sham Kakade, now on the Harvard faculty
Former postdoc Ryan Porter
Former postdoc Luis Ortiz, now on the University of Michigan-Dearborn CS faculty
Former postdoc John Langford, now at Microsoft Research NYC

TEACHING AND TUTORIAL MATERIAL

Teaching Fall 2024: CIS 6250, Theory of Machine Learning.
Teaching Spring 2024: CIS 4230/5230, Ethical Algorithm Design.
Web page for the undergraduate course Networked Life (NETS 112), Fall 2019 and a condensed online video version.
(See also the Fall 2018, Fall 2017, Fall 2016, Fall 2015, Fall 2014, Fall 2013, Fall 2012, Fall 2011 (hosted at Lore), Spring 2010, Spring 2009, Spring 2008, Spring 2007, Spring 2006, Spring 2005, and Spring 2004 offerings.)
Web page for MKSE 150: Market and Social Systems on the Internet, Spring 2013, taught jointly with Aaron Roth.
Web page for the graduate seminar No Regrets in Learning and Game Theory, Spring 2013, run jointly with Aaron Roth.
Here are the slides for my STOC 2012 tutorial on Algorithmic Trading and Computational Finance
Web page for CIS 625, Spring 2018: Computational Learning Theory. Here is the Spring 2016 version, an earlier version with Grigory Yaroslavtsev, an earlier version with Jake Abernethy, and an earlier version with Koby Crammer.
Web page for the graduate seminar course Social Networks and Algorithmic Game Theory, Fall 2009
Web page for CIS 620, Fall 2007: Seminar on Foundations of Cryptography.
Web page for CIS 620, Fall 2006: Seminar on Sponsored Search.
Web page for the graduate seminar CIS 700/04: Advanced Topics in Machine Learning (Fall 2004).
Web page for CIS 700/04: Advanced Topics in Machine Learning (Fall 2003).
Web page for a course on Computational Game Theory (Spring 2003). This was a joint course between CIS and Wharton (listed as CIS 620 and Wharton OPIM 952).
Course web page for CIS 620: Advanced Topics in AI (Spring 2002)
Course web page for CIS 620: Advanced Topics in AI (Spring 1997)
Web page for NIPS 2002 Tutorial on Computational Game Theory.
ACL 1999 Tutorial Slides [PDF]
Course Outline and Material for 1999 Bellairs Institute Workshop
Theoretical Issues in Probabilistic Artificial Intelligence (FOCS 98 Tutorial) [PDF]
A Short Course in Computational Learning Theory: ICML '97 and AAAI '97 Tutorials [PDF]

PRESS/MEDIA

Below are some press/media articles about my research/work, or in which I am quoted, or which I authored. (Some links are behind paywalls or are unfortunately now dead.)

PUBLICATIONS:BOOKS

[PHOTO]

The Ethical Algorithm: The Science of Socially Aware Algorithm Design. The Ethical Algorithm is jointly authored with Aaron Roth, and is a general-audience book about the science of designing algorithms that embed social values like privacy and fairness.

An Introduction to Computational Learning Theory. Jointly authored with Umesh Vazirani of U.C. Berkeley, this MIT Press publication is intended to be an intuitive but precise treatment of some interesting and fundamental topics in computational learning theory. The level is appropriate for graduate students and researchers in machine learning, artificial intelligence, neural networks, and theoretical computer science. The link above is to the MIT Press page that provides a brief description of the book and ordering information. If you have the book and have any questions or comments, please click here to send me mail.

The Computational Complexity of Machine Learning. This revision of my doctoral dissertation was published by the MIT Press as part of the ACM Doctoral Dissertation Award Series. As it is now out of print, I am making it available for downloading below.
[PDF]

PUBLICATIONS: RESEARCH ARTICLES

What follows is a listing of (almost) all of my research papers in (approximately) reverse chronological order. For papers with both a conference and journal version, the paper is usually placed by its first (conference) date. Also, as per the honorable tradition of the theoretical computer science community, on almost all of the papers below that are primarily mathematical in content, authors are listed alphabetically.

Acronyms for conferences and journals include: AAAI: Annual National Conference on Artificial Intelligence; AIES: AAAI/ACM Conference on Artificial Intelligence, Ethics and Society; AISTATS: International Conference on Artificial Intelligence and Statistics; ALT: Algorithmic Learning Theory; COLT: Annual Conference on Computational Learning Theory; EC: ACM Conference on Economics and Computation; FAccT: ACM Conference on Fairness, Accountability and Transparency (formerly FAT* and FATML); FOCS: IEEE Foundations of Computer Science; HCOMP: AAAI Conference on Human Computation and Crowdsourcing; ICCV: International Conference on Computer Vision; ICML: International Conference on Machine Learning; IJCAI: International Joint Conference on Artificial Intelligence; ITCS: Innovations in Theoretical Computer Science; NIPS/NeurIPS: Neural Information Processing Systems; PNAS: Proceedings of the National Academy of Sciences; SaTML: IEEE Conference on Secure and Trustworthy Machine Learning; SODA: ACM Symposium on Discrete Algorithms; STOC: ACM Symposium on the Theory of Computation; UAI: Annual Conference on Uncertainty in Artificial Intelligence; WINE: Workshop on Internet and Network Economics.

In addition to the list below, you can also look at my page on Google Scholar, and this DBLP query seems to do a pretty good job of finding those publications that appeared in mainstream CS venues (though not others), and can be useful for generating bibtex citations.

Improving LLM Group Fairness on Tabular Data via In-Context Learning. With V. Cherepanova, C.J. Lee, N. Akpinar, R. Fogliato, M. Bertran, and James Zou. Preprint, 2024.
[arXiv version]

Model Ensembling for Constrained Optimization. With I. Globus-Harris, V. Gupta, and Aaron Roth. Preprint, 2024.
[arXiv version]

Oracle-Efficient Reinforcement Learning for Max Value Ensembles. With M. Hussing, A. Roth, S. Sengupta, and J. Sorrell. NeurIPS 2024.
[arXiv version]

Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerable With M. Bertran, S. Tang, J. Morgenstern, A. Roth, and Z.S. Wu. NeurIPS 2024. (Preliminary version in Theory and Practice of Differential Privacy, 2024.)
[arXiv version]

AI Model Disgorgement: Methods and Choices. With A. Achille, C. Klingenberg, and S. Soatto. PNAS, April 2024.
[PNAS online version] [PDF]

Diversified Ensembling: An Experiment in Crowdsourced Machine Learning. With I. Globus-Harris, D. Harrison, P. Perona, and A. Roth. FAccT 2024.
[arXiv version]

Balanced Filtering via Non-Disclosive Proxies. With S. Deng, E. Diana, and A. Roth. FORC 2024.
[arXiv version]

Improved Differentially Private Regression via Gradient Boosting. With S. Tang, S. Aydore, S. Rho, A. Roth, Y. Wang, Y-X. Wang, and Z.S. Wu. SaTML 2024.
[arXiv version]

Replicable Reinforcement Learning. With E. Eaton, M. Hussing, and J. Sorrell. NeurIPS 2023.
[arXiv version]

Scalable Membership Inference Attacks via Quantile Regression. With M. Bertran, S. Tang, J. Morgenstern, A. Roth, and Z.S. Wu. NeurIPS 2023.
[arXiv version]

Generating Relaxed Synthetic Data Using Adaptive Projection. With S. Aydore, W. Brown, K. Kenthapadi, L. Melis, A. Roth and A. Siva. U.S. Patents No. 11,487,765 and 11,841,863, November 2022 and December 2023.
[765 patent PDF] [863 patent PDF]

Multicalibration as Boosting for Regression. With I. Globus-Harris, D. Harrison, A. Roth and J. Sorrell. ICML 2023.
[arXiv version]

Confidence-Ranked Reconstruction of Census Microdata from Published Statistics. With T. Dick, C. Dwork, T. Liu, A. Roth, G. Vietri, and Z.S. Wu. PNAS, February 2023.
[PNAS version] [arXiv version] [Commentary by U.S. Census researchers] [A silly letter and our response]

Multicalibrated Regression for Downstream Fairness. With I. Globus-Harris, V. Gupta, C. Jung, J. Morgenstern, and A. Roth. AIES 2023.
[arXiv version]

Efficient Stackelberg Strategies for Finitely Repeated Games. With E. Arunachaleswaran and N. Collina. AAMAS 2023.
[arXiv version]

Private Synthetic Data for Multitask Learning and Marginal Queries. With G. Vietri, C. Archambeau, S. Aydore, W. Brown, A. Roth, A. Siva, S. Tang, and Z.S. Wu. NeurIPS 2022.
[arXiv version]

An Algorithmic Framework for Bias Bounties. With I. Globus-Harris and A. Roth. FAccT 2022.
[arXiv version]

Multiaccurate Proxies for Downstream Fairness. With E. Diana, W. Gill, K. Kenthapadi, A. Roth, and S. Sharifi-Malvajerdi. FAccT 2022.
[arXiv version]

Mixed Differential Privacy in Computer Vision. With A. Golatkar, A. Achille, Y. Wang, A. Roth, and S.Soatto. ICCV 2022.
[arXiv version]

Differentially Private Query Release Through Adaptive Projection. With S. Aydore, W. Brown, K. Kenthapadi, L. Melis, A. Roth and A. Siva. ICML 2021.
[arXiv version] [github repo]

Algorithms and Learning for Fair Portfolio Design. With E. Diana, T. Dick, H. Elzayn, A. Roth, Z. Schutzman, S. Sharifi-Malvajerdi, and J. Ziani. ACM EC 2021.
[arXiv version]

Lexicographically Fair Learning: Algorithms and Generalization. With E. Diana, W. Gill, I. Globus-Harris, A. Roth and S. Sharifi-Malvajerdi. Foundations of Responsible Computing (FORC), 2021.
[arXiv version]

An Algorithmic Framework for Fairness Elicitation. With C. Jung, S. Neel, A. Roth, L. Stapleton, and Z.S. Wu. Foundations of Responsible Computing (FORC), 2021.
[arXiv version]

Minimax Group Fairness: Algorithms and Experiments. With E. Diana, W. Gill, K. Kenthapadi, and A. Roth. AIES 2021.
[arXiv version] [github repo]

Optimal, Truthful and Private Securities Lending. With E. Diana, S. Neel, and A. Roth. ACM International Conference on AI in Finance, 2020.
[arXiv version]

Differentially Private Call Auctions and Market Impact. With E. Diana, H. Elzayn, A. Roth, S. Sharifi-Malvajerdi, and J. Ziani. ACM EC 2020.
[arXiv version] [EC version] [EC talk]

Ethical Algorithm Design Should Guide Technology Regulation. With A. Roth. Brookings Institution policy briefing, 2020.
[Brookings link]

Average Individual Fairness: Algorithms, Generalization and Experiments. With A. Roth and S. Sharifi-Malvajerdi. NeurIPS 2019.
[arXiv version]

Equilibrium Characterization for Data Acquisition Games. With H. Elzayn, J. Dong, S. Jabbari, and Z. Schutzman. IJCAI 2019.
[PDF]

Network Formation under Random Attack and Probabilistic Spread. With Y. Chen, S. Jabbari, S. Khanna, and J. Morgenstern. IJCAI 2019.
[arXiv version]

Differentially Private Fair Learning. With M. Jagielski, J. Mao, A. Oprea, A. Roth, S. Sharifi-Malvajerdi, and J. Ullman. ICML 2019.
[arXiv version]

Fair Algorithms for Learning in Allocation Problems. With H. Elzayn, S. Jabbari, C. Jung, S. Neel, A. Roth, and Z. Schutzman. ACM FAT* 2019.
[arXiv version]

An Empirical Study of Rich Subgroup Fairness for Machine Learning. With S. Neel, A. Roth, and Z.S. Wu. ACM FAT* 2019.
[arXiv version] [github repo]

Online Learning with an Unknown Fairness Metric. With S. Gillen, C. Jung and A. Roth. NeurIPS 2018.
[arXiv version]

Fairness in Criminal Justice Risk Assessments: The State of the Art. With R. Berk, H. Heidari, S. Jabbari, and A. Roth. Sociological Methods and Research, July 2018.
[arXiv version] [SMR version]

Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness. With S. Neel, A. Roth, and Z.S. Wu. ICML 2018.
[arXiv version] [github repo] [short video] [tcs+ talk video]

Data Intimacy, Machine Learning, and Consumer Privacy. Penn Law CTIC whitepaper, May 2018.
[PDF]

Fair Algorithms for Infinite and Contextual Bandits. With M. Joseph, J. Morgenstern, S. Neel, and A. Roth. AIES 2018. (Earlier version appeared in FATML, 2017.)
[arXiv version] [AIES version]

A Convex Framework for Fair Regression. With R. Berk, H. Heidari, S. Jabbari, M. Joseph, J. Morgenstern, S. Neel, and A. Roth. FATML 2017.
[arXiv version] [FATML version]

Meritocratic Fairness for Cross-Population Selection. With A. Roth and Z.S. Wu. ICML 2017.
[PDF]

Fairness in Reinforcement Learning. With S. Jabbari, M. Joseph, J. Morgenstern, and A. Roth. ICML 2017.
[PDF]

Predicting with Distributions. With Z.S. Wu. COLT 2017.
[COLT version] [arXiv version]

Fairness Incentives for Myopic Agents. With S. Kannan, J. Morgenstern, M. Pai, A. Roth, R. Vorhra, and Z.S. Wu. ACM EC 2017.
[EC version] [arXiv version]

Mathematical Foundations for Social Computing. With Y. Chen, A. Ghosh, T. Roughgarden, and J. Wortman Vaughan. CACM, December 2016.
[PDF]

Fairness in Learning: Classic and Contextual Bandits. With M. Joseph, J. Morgenstern, and A. Roth. NIPS 2016.
[NIPS version] [arXiv version]

Strategic Network Formation with Attack and Immunization. With S. Goyal, S. Jabbari, S. Khanna, and J. Morgenstern. WINE 2016.
[arXiv version]

Tight Policy Regret Bounds for Improving and Decaying Bandits. With H. Heidari and A. Roth. IJCAI 2016.
[PDF]

Private Algorithms for the Protected in Social Network Search. With A. Roth, Z.S. Wu, and G. Yaroslavtsev. PNAS, January 2016.
[PNAS version] [arXiv version]

Robust Mediators in Large Games. With M. Pai, R. Rogers, A. Roth, and J. Ullman. (Subsumes and expands "Mechanism Design in Large Games: Incentives and Privacy", ITCS 2014.)
[arXiv version]

The Small-World Network of Squash. With R. Rayfield. Squash Magazine, October 2015.
[PDF] [online version]

Privacy and Truthful Equilibrium Selection for Aggregative Games. With R. Cummings, A. Roth, and Z.S. Wu. WINE 2015.
[PDF] [arXiv version]

From "In" to "Over": Behavioral Experiments on Whole-Network Computation. With L. Dworkin. HCOMP 2015.
[PDF]

Online Learning and Profit Maximization from Revealed Preferences. With K. Amin, R. Cummings, L.Dworkin, and A. Roth. AAAI 2015.
[AAAI version] [arXiv version]

Competitive Contagion in Networks. With H. Heidari and S. Goyal. To appear in Games and Economic Behavior. (This paper is an expanded version of the Goyal-Kearns STOC 2012 paper, and contains a number of new results.)
[PDF]

A Computational Study of Feasible Repackings in the FCC Incentive Auctions. With L.Dworkin. White paper filed with the Federal Communications Commission, June 2014.
[arXiv version] [Ex Parte Cover Letter]

Pursuit-Evasion Without Regret, with an Application to Trading. With L.Dworkin and Y. Nevmyvaka. ICML 2014.
[PDF]

Learning from Contagion (Without Timestamps) With K. Amin and H. Heidari. ICML 2014.
[PDF]

New Models for Competitive Contagion. With M. Draief and H. Heidari. AAAI 2014.
[PDF]

Efficient Inference for Complex Queries on Complex Distributions. With L. Dworkin and L. Xia. AISTATS 2014.
[PDF]

Marginals-to-Models Reducibility. With T. Roughgarden. NIPS 2013.
[PDF]

Machine Learning for Market Microstructure and High Frequency Trading. With Y. Nevmyvaka. High Frequency Trading - New Realities for Traders, Markets and Regulators , M. O'Hara, M. Lopez de Prado, D. Easley, editors. Risk Books, 2013.
[PDF] [publisher link]

Stress-Induced Changes in Gene Interactions in Human Cells. With R. Nayak, W. Bernal, J. Lee, and V. Cheung. Nucleic Acids Research, 2013, 1-15.
[PDF]

Depth-Workload Tradeoffs for Workforce Organization. With H. Heidari. HCOMP 2013.
[PDF]

Large-Scale Bandit Problems and KWIK Learning. With J. Abernethy, K. Amin, and M. Draief. ICML 2013.
[PDF]

Experiments in Social Computation. Communications of the ACM, October 2012.
[PDF]

Budget Optimization for Sponsored Search: Censored Learning in MDPs. With K. Amin, P. Key and A. Schwaighofer. UAI 2012.
[PDF]

Behavioral Experiments on a Network Formation Game. With S. Judd and Y. Vorobeychik. ACM EC 2012.
[PDF]

Competitive Contagion in Networks. With S. Goyal. STOC 2012.
[PDF]

Colonel Blotto on Facebook: The Effect of Social Relations on Strategic Interaction. with P. Kohli, Y. Bachrach, D. Stillwell, R. Herbrich, T. Graepel. ACM Web Science, 2012.
[PDF]

Learning and Predicting Dynamic Behavior with Graphical Multiagent Models. With Q. Duong, M. Wellman, and S. Singh. AAMAS 2012.
[PDF]

Behavioral Conflict and Fairness in Social Networks. With S. Judd and E. Vorobeychik. WINE 2011.
[PDF]

A Clustering Coefficient Network Formation Game. With M. Brautbar. Symposium on Algorithmic Game Theory (SAGT), 2011.
[PDF]

Graphical Models for Bandit Problems. With K. Amin and U. Syed. UAI 2011.
[PDF]

Bandits, Query Learning, and the Haystack Dimension. With K. Amin and U. Syed. COLT 2011. (K. Amin, Best Student Presentation at NY Academy of Sciences ML workshop)
[PDF]

Market Making and Mean Reversion. With T. Chakraborty. ACM EC 2011.
[PDF]

Designing a Digital Future: Federally Funded Research and Development in Networking and Information Technology. PCAST Working Group. Report to the President and Congress, December 2010.
[PDF] [Related Material]

Empirical Limitations on High Frequency Trading Profitability. With A. Kulesza and Y. Nevmyvaka. Journal of Trading, Fall 2010. (JOT Best Paper Award for 2010)
[SSRN version] [arXiv version] [JOT link]

Behavioral Dynamics and Influence in Networked Coloring and Consensus. With S. Judd and Y. Vorobeychik. PNAS, August 2010.
[PDF] [PNAS link]

Private and Third-Party Randomization in Risk-Sensitive Equilibrium Concepts. With M. Brautbar, U. Syed. AAAI 2010.
[PDF]

A Behavioral Study of Bargaining in Social Networks. With T. Chakraborty, S. Judd, J. Tan. ACM EC 2010.
[PDF]

Local Algorithms for Finding Interesting Individuals in Large Networks. With M. Brautbar. Innovations in Theoretical Computer Science (ITCS), 2010.
[PDF]

Coexpression Network Based on Natural Variation in Human Gene Expression Reveals Gene Interactions and Functions. With R. Nayak, R. Spielman, V. Cheung. Genome Science, November 2009.
[Web Link] [PDF] [Cover Image]

Censored Exploration and the Dark Pool Problem. With K. Ganchev, Y. Nevmyvaka, J. Wortman. UAI 2009. Journal version in CACM, May 2010. (UAI Best Student Paper Award, K. Ganchev and J. Wortman)
[PDF] [CACM version] [Peter Bartlett commentary] [BofA marketing summary]

Networked Bargaining: Algorithms and Structural Results. With T. Chakraborty and S. Khanna. ACM EC 2009.
[PDF]

Behavioral Experiments on Biased Voting in Networks. With S. Judd, J. Tan and J. Wortman. PNAS, January 2009.
[PDF]

Biased Voting and the Democratic Primary Problem. With J. Tan. WINE 2008.
[PDF]

Bargaining Solutions in a Social Network. With T. Chakraborty. WINE 2008.
[PDF]

Learning from Collective Behavior. With J. Wortman. COLT 2008.
[PDF]

Behavioral Experiments in Networked Trade. With S. Judd. ACM EC 2008.
[PDF]

Graphical Games. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, editors, Cambridge University Press, September, 2007.
[PDF]

Sponsored Search with Contexts. With E. Even-Dar and J. Wortman. WINE 2007. The following longer version appeared in the Third Workshop on Sponsored Search Auctions, WWW 2007.
[PDF]

Empirical Price Modeling for Sponsored Search. With K. Ganchev, A. Kulesza, J. Tan, R. Gabbard, Q. Liu. WINE 2007. The following longer version appeared in the Third Workshop on Sponsored Search Auctions, WWW 2007.
[PDF]

A Network Formation Game for Bipartite Exchange Economies. With E. Even-Dar and S. Suri. ACM SODA 2007.
[PDF] [Extended Version, PDF]

Privacy-Preserving Belief Propagation and Sampling. With J. Tan and J. Wortman. NIPS 2007.
[PDF]

Regret to the Best vs. Regret to the Average. With E. Even-Dar, Y. Mansour, and J. Wortman. COLT 2007. Journal version in Machine Learning Journal, volume 71, 2008. (J. Wortman, COLT Best Student Paper Award)
[COLT Version] [MLJ Version]

A Small World Threshold for Economic Network Formation. With E. Even-Dar. NIPS 2006.
[PDF]

An Experimental Study of the Coloring Problem on Human Subject Networks. With S. Suri and N. Montfort. Science 313(5788), August 2006, pp. 824-827.
[Abstract] [Full Paper] [PDF]

Networks Preserving Evolutionary Stability and the Power of Randomization. With S. Suri. ACM Conference on Electronic Commerce (EC), 2006.
[PDF]

(In)Stability Properties of Limit Order Dynamics. With E. Even-Dar, S. Kakade, and Y. Mansour. ACM Conference on Electronic Commerce (EC), 2006.
[PDF]

Reinforcement Learning for Optimized Trade Execution. With Y. Nevmyvaka and Y. Feng. ICML 2006.
[PDF]

Risk-Sensitive Online Learning. With E. Even-Dar and J. Wortman. ALT 2006. This is a corrected version posted Oct 4 2006. This version corrects errors in the section of experimental results published in the ALT 2006 proceedings.
[PDF]

Learning from Multiple Sources. With K. Crammer and J. Wortman. NIPS 2006; also in JMLR 2008.
[PDF] [Journal Version PDF]

Economics, Computer Science, and Policy.
Issues in Science and Technology, Winter 2005.
[Article in PDF]
[Cover Image]
Electronic Trading in Order-Driven Markets: Efficient Execution. With Y. Nevmyvaka, A. Papandreou and K. Sycara. IEEE Conference on Electronic Commerce (CEC), 2005.
[PDF]

Trading in Markovian Price Models. With S. Kakade. COLT 2005.
[PDF]

Learning from Data of Variable Quality. With K. Crammer and J. Wortman. NIPS 2005.
[PDF]

Economic Properties of Social Networks. With S. Kakade, L. Ortiz, R. Pemantle, and S. Suri. Proceedings of NIPS 2004.
[PDF]

Graphical Economics. With S. Kakade and L. Ortiz. Proceedings of COLT 2004.
[PDF]

Competitive Algorithms for VWAP and Limit Order Trading. With S. Kakade, Y. Mansour and L. Ortiz. Proceedings of the ACM Conference on Electronic Commerce (EC), 2004.
[PDF]

Algorithms for Interdependent Security Games. With L. Ortiz. NIPS 2003.
[PDF]

Correlated Equilibria in Graphical Games. With S. Kakade, J. Langford, and L. Ortiz. ACM Conference on Electronic Commerce (EC), 2003.
[PDF]

The Penn-Lehman Automated Trading Project. With L. Ortiz. IEEE Intelligent Systems, Nov/Dec 2003.
IEEE version [PDF] Long version [PDF]

Exploration in Metric State Spaces. With S. Kakade and J. Langford. ICML 2003.
[PDF]

Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System. With S. Singh, D. Litman, M. Walker. Journal of Artificial Intelligence Research, 2002.
[PDF]

Nash Propagation for Loopy Graphical Games. With L. Ortiz. Proceedings of NIPS 2002.
[PDF]

Efficient Nash Computation in Large Population Games with Bounded Influence. With Y. Mansour. Proceedings of UAI 2002.
[PDF]

A Note on the Representational Incompatabilty of Function Approximation and Factored Dynamics. With E. Allender, S. Arora, C. Moore, A. Russell. Proceedings of NIPS 2002.
[PDF]

CobotDS: A Spoken Dialogue System for Chat. With C. Isbell, S. Singh, D. Litman, J. Howe. Proceedings of AAAI 2002.
[PDF]

An Efficient Exact Algorithm for Singly Connected Graphical Games. With M. Littman, S. Singh. 2001. NIPS 2001.
[PDF]

NOTE: The main result of the paper above --- an efficient algorithm claimed to find a single exact Nash equilibrium in tree graphical games --- is unfortunately wrong. This was discovered and discussed in the very nice paper by Elkind, Goldberg and Goldberg, which can be found here. The problem of efficiently computing an exact Nash equilibrium in trees remains open (though EG&G demonstrate that no two-pass algorithm can suffice). The original polynomial-time approximate Nash algorithm from the K., Littman, Singh UAI 2001 paper is unaffected by these developments, as is its NashProp generalization in the Ortiz and K. 2002 NIPS paper.

Graphical Models for Game Theory. With M. Littman, S. Singh. 2001. UAI 2001.
[PDF]

ATTac-2000: An Adaptive Autonomous Bidding Agent. With P. Stone, M. Littman, S. Singh. Journal of Artificial Intelligence Research . Earlier version in Proceedings of Agents 2001.
[PDF]
New York Times article on TAC

A Social Reinforcement Learning Agent. With C. Shelton, C. Isbell, S. Singh, P. Stone. Proceedings of Agents 2001. Winner of Best Paper Award at the Conference.
[PDF]

Nash Convergence of Gradient Dynamics in General-Sum Games. With S. Singh, Y. Mansour. Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, pages 541-548, 2000.
[PDF]

Fast Planning in Stochastic Games. With Y. Mansour, S. Singh. Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, pages 309-316, 2000.
[PDF]

Bias-Variance Error Bounds for Temporal Difference Updates. With S. Singh. Proceedings of the 13th Annual Conference on Computational Learning Theory, 2000, pages 142--147.
[PDF]

Approximate Planning in Large POMDPs via Reusable Trajectories. With Y. Mansour and A. Ng. Advances in Neural Information Processing Systems 12, MIT Press, 2000.
[PDF] [Long Version]

Testing Problems with Sub-Learning Sample Complexity. With D. Ron. Journal of Computer and System Sciences, 61, pp. 428-456, 2000. Earlier version in Proceedings of the 12th Annual Workshop on Computational Learning Theory.
[PDF]

Cobot in LambdaMOO: A Social Statistics Agent. With C. Isbell, D. Kormann, S. Singh, P. Stone. Proceedings of the 17th National Conference on Artificial Intelligence, pp. 36-41, 2000, AAAI Press/MIT Press.
[PDF]

Empirical Evaluation of a Reinforcement Learning Spoken Dialogue System. With S. Singh, D. Litman, M. Walker. Proceedings of the 17th National Conference on Artificial Intelligence, pp. 645-651, 2000, AAAI Press/MIT Press.
[PDF]

Automatic Optimization of Dialogue Management. With D. Litman, S. Singh, M. Walker. Appeared in COLING 2000.
[PDF]

A Boosting Approach to Topic Spotting on Subdialogues. With K. Myers, S. Singh, M. Walker. Appeared in ICML 2000.
[PDF]

Reinforcement Learning for Spoken Dialogue Systems. With S. Singh, D. Litman and M. Walker. Advances in Neural Information Processing Systems 12, MIT Press, 2000.
[PDF]

Automatic Detection of Poor Speech Recognition at the Dialogue Level. With D. Litman and M. Walker. Proceedings of the 37th Annual Meeting for Computational Linguistics, 1999, pages 309-316.
[PDF]

A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes. With Y. Mansour and A. Ng. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence Morgan Kaufmann, 1999, pages 1324--1331. Also appeared in a special issue of the journal Machine Learning, 2002.
[PDF, Journal Version]

Efficient Reinforcement Learning in Factored MDPs. With D. Koller. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1999, pages 740--747.
[PDF]

Finite-Sample Rates of Convergence for Q-Learning and Indirect Methods. With S. Singh. Advances in Neural Information Processing Systems 11, The MIT Press, 1999, pages 996--1002.
[PDF]

Inference in Multilayer Networks via Large Deviation Bounds. with L. Saul. Advances in Neural Information Processing Systems 11, The MIT Press, 1999, pages 260--266.
[PDF]

Large Deviation Methods for Approximate Probabilistic Inference, with Rates of Convergence. With L. Saul. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, 1998, pages 311--319.
[PDF]

Exact Inference of Hidden Structure from Sample Data in Noisy-OR Networks. With Y. Mansour. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, 1998, pages 304--310.
[PDF]

Near-Optimal Reinforcement Learning in Polynomial Time. With S. Singh. Proceedings of the 15th International Conference on Machine Learning, pp. 260-268, 1998, Morgan Kaufmann. Appeared in a special issue of the journal Machine Learning.
[PDF]

A Fast, Bottom-Up Decision Tree Pruning Algorithm with Near-Optimal Generalization. With Y. Mansour. Proceedings of the 15th International Conference on Machine Learning, 1998, Morgan Kaufmann, pages 269--277.
[PDF]

An Information-Theoretic Analysis of Hard and Soft Assignment Methods for Clustering. with Y. Mansour and A. Ng. Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, pp. 282-293, 1997, Morgan Kaufmann.
[PDF]

Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation. With D. Ron. Neural Computation 11(6), pages 1427-1453, 1999. Earlier version in Proceedings of the Tenth Annual Conference on Computational Learning Theory, ACM Press, 1997, pages 152--162.
[PDF]

Boosting Theory Towards Practice: Recent Developments in Decision Tree Induction and the Weak Learning Framework. Abstract accompanying invited talk given at AAAI '96, Portland, Oregon, August 1996.
[PDF]

Applying the Weak Learning Framework to Understand and Improve C4.5. With T. Dietterich and Y. Mansour. Proceedings of the 13th International Conference on Machine Learning, pp. 96-104, 1996, Morgan Kaufmann.
[PDF]

On the Boosting Ability of Top-Down Decision Tree Learning Algorithms. With Y. Mansour. Journal of Computer and Systems Sciences, 58(1), 1999, pages 109-128. Earlier version in Proceedings of the 28th ACM Symposium on the Theory of Computing, pp.459-468, 1996, ACM Press.
[PDF]

A Bound on the Error of Cross Validation Using the Approximation and Estimation Rates, with Consequences for the Training-Test Split. Neural Computation 9(5), 1997, pages 1143--1161. Earlier version in Advances in Neural Information Processing Systems 8, The MIT Press, pages 183--189, 1996.
[PDF]

An Experimental and Theoretical Comparison of Model Selection Methods. With Y. Mansour, A. Ng, and D. Ron. Machine Learning 27(1), 1997, pages 7--50. Earlier version in Proceedings of the Eighth ACM Conference on Computational Learning Theory, ACM Press, 1995, pages 21--30.
[COLT version] [MLJ version]

On the Consequences of the Statistical Mechanics Theory of Learning Curves for the Model Selection Problem. Neural Networks: The Statistical Mechanics Perspective, pp. 277-284, 1995, World Scientific.
[PDF]

Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries. With Y. Freund, Y. Mansour, D. Ron, R. Rubinfeld, and R. Schapire. Proceedings of the 36th IEEE Symposium on the Foundations of Computer Science, pp. 332-341, 1995, IEEE Press.
[PDF]

Horn Approximations of Empirical Data. With H. Kautz and B. Selman. Artificial Intelligence, 74(1), pages 129-145, 1995.
[PDF]

On the Complexity of Teaching. With S. Goldman. Journal of Computer and Systems Sciences, 50(1), pp. 20-31, 1995.
[PDF]

On the Learnability of Discrete Distributions. With Y. Mansour, R. Rubinfeld, D. Ron, R. Schapire, and L. Sellie. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pp. 273-282, 1994, ACM Press.
[PDF]

Cryptographic Primitives Based on Hard Learning Problems. With A. Blum, M. Furst, and R. Lipton. Advances in Cryptology, Lecture Notes in Computer Science, Volume 773, pp. 278-291, 1994, Springer-Verlag.
[PDF]

Rigorous Learning Curve Bounds from Statistical Mechanics. With D. Haussler, H.S. Seung, and N. Tishby. Machine Learning,25, 1996, pages 195--236. Earlier version in ACM Conference on Computational Learning Theory, pp. 76-87, 1994, ACM Press.
[PDF]

The Minimal Disagreement Parity Problem as a Hard Satisfiability Problem. With J. Crawford and R. Schapire. Unpublished manuscript, 1994.
[PDF]

Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis. With A. Blum, M. Furst, J. Jackson, Y. Mansour, and S. Rudich. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pp. 253-262, 1994, ACM Press.
[PDF]

Efficient Noise-Tolerant Learning from Statistical Queries. Journal of the ACM , 45(6), pp. 983 --- 1006, 1998. Earlier version in Proceedings of the 25th ACM Symposium on the Theory of Computing, pp. 392-401, 1993, ACM Press.
[PDF]

Efficient Learning of Typical Finite Automata from Random Walks. With Y. Freund, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie. Proceedings of the 25th ACM Symposium on the Theory of Computing, pp. 315-324, 1993, ACM Press.
[PDF]

Learning from a Population of Hypotheses. With S. Seung. Machine Learning 18, pp. 255-276, 1995. Earlier version in Proceedings of the Sixth Annual Workshop on Computational Learning Theory, pp. 101-110, 1993, ACM Press.
[PDF]

Towards Efficient Agnostic Learning. With R. Schapire and L. Sellie. Machine Learning 17, pp. 115-141, 1994. Earlier version in Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 341-352, 1992, ACM Press.
[PDF]

Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension. With D. Haussler and R. Schapire. Machine Learning 14, pp. 83-113, 1994. Earlier version in Proceedings of the Fourth Annual Workshop on Computational Learning Theory, pp. 61-74, 1991, Morgan Kaufmann.
[PDF]

Oblivious PAC Learning of Concept Hierarchies. AAAI 1992.
[PDF]

Estimating Average-Case Learning Curves Using Bayesian, Statistical Physics, and VC Dimension Methods. With D. Haussler, M. Opper, and R. Schapire. NIPS 1991.
[PDF]

Equivalence of Models for Polynomial Learnability. With D. Haussler, N. Littlestone, and M. Warmuth. Information and Computation 95(2), pp. 129-161, 1991.
[PDF]

Efficient Distribution-free Learning of Probabilistic Concepts. With R. Schapire. Journal of Computer and System Sciences 48(3), pp. 464-497. Earlier version in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 382-391, 1990, IEEE Press.
[PDF]

Exact Identification of Read-once Formulas Using Fixed Points of Amplification Functions. With S. Goldman and R. Schapire. SIAM Journal on Computing 22(4), pp. 705-726. Earlier version in Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pp. 193-202, 1990, IEEE Press.
[PDF]

A Polynomial-Time Algorithm for Learning k-Variable Pattern Languages from Examples. With L. Pitt. COLT 1989. (Unfortunately missing references, bib file got corrupted)
[PDF]

Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. With L. Valiant. Journal of the ACM 41(1), pp. 67-95, 1994. Earlier version in Proceedings of the 21st ACM Symposium on the Theory of Computing, pp. 433-444, 1989, ACM Press.
[PDF]

A General Lower Bound on the Number of Examples Needed for Learning. With A. Ehrenfeucht, D. Haussler, and L. Valiant. Information and Computation 82(3), pp. 247-261, 1989. Earlier version in Proceedings of the 1988 Workshop on Computational Learning Theory, pp. 139-154, 1988, Morgan Kaufmann.
[PDF]

Learning in the Presence of Malicious Errors. With M. Li. SIAM Journal on Computing 22(4), pp. 807-837, 1993. Earlier version in Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 267-280, 1988, ACM Press.
[PDF]

Thoughts on Hypothesis Boosting. Unpublished manuscript, 1988. Project for Ron Rivest's machine learning course at MIT.
[PDF]

On the Learnability of Boolean Formulae. With M. Li, L. Pitt, and L. Valiant. Proceedings of the 19th ACM Symposium on the Theory of Computing, pp. 285-195, 1987, ACM Press.
[PDF]

Learning Boolean Formulae. With M. Li and L. Valiant. Journal of the ACM 41(6), pp. 1298-1328, 1995. Earlier version in Proceedings of the 19th ACM Symposium on the Theory of Computing, pp. 285-195, 1987, ACM Press.
[PDF]

Recent Results in Boolean Concept Learning. With M. Li, L. Pitt and L. Valiant. Proceedings of the Fourth International Conference on Machine Learning, pp. 337-352, 1987, Morgan Kaufmann.
[PDF]

Last Modified: December 11, 2024.

3YC