SITE DIRECTORY
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
RESEARCH INTERESTS
My research interests include topics in
machine learning, algorithmic game theory,
social networks, computational finance, and artificial intelligence.
I often examine problems in these areas using methods and models from theoretical
computer science and related disciplines.
While the majority of my work is mathematical in nature,
I have also participated
in a variety of empirical and experimental projects,
including applications of machine learning to finance,
spoken dialogue systems, and other areas. Most recently, I have been conducting humansubject experiments
on strategic and economic interaction in social networks.
QUICK LINKS
Warren Center for Network and Data Sciences
Networked and Social Systems Engineering (NETS) Program
Penn undergraduate course
Networked Life (NETS 112), Fall 2014
and a condensed
online version at Coursera.
PennLehman Automated Trading Project
(inactive)
Tribute Day for Les Valiant, May 2009
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
Statistics
and
Operations and Information Management (OPIM)
departments of the
Wharton School.
I am the Founding Director of the
Warren Center for Network and Data Sciences,
where my codirector is
Rakesh Vohra.
I am the Faculty Founder of
Penn Engineering's
Networked and Social Systems Engineering (NETS) Program,
whose director is
Ali Jadbabaie,
and whose program's curriculum chair is
Zack Ives.
I am an active member of Penn's machine learning community
PRiML,
and am an affiliated faculty member of Penn's
Applied Math and Computational Science
graduate program.
Until July 2006 I was the
codirector
of Penn's interdisciplinary
Institute for Research in Cognitive Science.
With
Yuriy Nevmyvaka,
I run a trading team at
Engineers Gate,
a quantitative hedge fund based in New York City.
I currently serve as an advisor to the companies
Yodle,
Wealthfront,
Activate Networks,
and
RootMetrics.
I am also involved in the
seedstage fund
Founder Collective.
I am a member of the
Technical Advisory Board of
Microsoft Research Cambridge.
I occasionally serve as an expert witness or consultant on technologyrelated legal and
regulatory cases.
The Past:
I spent the decade 19912001 in basic AI and machine learning research at
Bell Labs
and
AT&T Labs.
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 TTIChicago),
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 Yahoo! Research),
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, now at Columbia),
Sanjoy Dasgupta (now at UCSD),
Yoav Freund (now at UCSD),
Rob Schapire (now at Princeton),
William Cohen (now at CMU), and
Yoram Singer (later at Hebrew University, now at Google).
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 NYU),
Roberto Pieraccini (now at SpeechCycle),
Esther Levin (now at SAC Capital),
Lyn Walker (now at UC Santa Cruz),
Corinna Cortes (now at Google),
and
Vladimir Vapnik (now at Columbia and NEC).
Here is a nice
photo wall of
former AT&T Labs theory and algorithms researchers,
compiled by the great
David S. Johnson.
I spent 2001 as CTO of the European venture capital firm
Syntek Capital,
and joined the Penn faculty in January 2002.
From June 2009 through September 2013, I helped run a quantitative trading team in the MultiQuant division of
SAC Capital
in New York City.
From May 2007 through April 2009,
I 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.
In the past I have served as an advisor to the startups
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,
and a member of the Advanced Technology Advisory Council of
PJM Interconnection.
and the Scientific Advisory Board of
Opera Solutions.
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 born into an academic family, including
my father
David Kearns
(UCSD, Chemistry);
his brother, and my uncle
Tom Kearns
(Amherst College, Philosophy);
their father, and my paternal grandfather,
Clyde Kearns
(University of Illinois, Entomology);
and my maternal grandfather
Chen ShouYi
(Pomona College, History and Literature).
EDITORIAL AND PROFESSIONAL SERVICE
In the past I have been program chair of 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 on the editorial board of the MIT Press series on Adaptive Computation
and Machine Learning.
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 am currently a member of the
Computer Science and Telecommunications Board
of the National Academies.
From 20022008 I was a member, vice chair and chair of
DARPA's Information Science and
Technology (ISAT) study group.
RESEARCH GROUP
Current (alphabetical):
Doctoral student
Kareem Amin
Doctoral student
Lili Dworkin
Doctoral student
Hoda Heidari
(jointly advised with Ali Jadbabaie )
Doctoral student
Shahin Jabbari
Doctoral student
Ryan Rogers
(jointly advised with Aaron Roth )
Doctoral student
Steven Wu
(jointly advised with Aaron Roth )
Research scientist
Stephen Judd
Visiting scientist
Yuriy Nevmyvaka
Alumni (reverse chronological):
Former doctoral student
Mickey Brautbar,
now at Crisply
Former postdoc
Jake Abernethy,
now on the University of Michigan CS faculty
Former postdoc
Kris Iyer,
now on the Cornell ORIE faculty
Former MD/PhD student
Renuka Nayak,
now a clinical fellow at UCSF
Former doctoral student
Tanmoy Chakraborty,
now at Facebook
Former postdoc
Umar Syed,
now at Google NYC
Former doctoral student
Jinsong Tan,
now at Uber
Former postdoc
Eugene Vorobeychik,
now on the Vanderbilt CS faculty
Former postdoc
Giro Cavallo,
now at Yahoo! NYC
Former doctoral student
Jenn Wortman Vaughan,
now at Microsoft Research NYC
Former postdoc
Eyal EvenDar,
now at Final Israel
Former doctoral student
Sid Suri,
now at Microsoft Research NYC
Former postdoc
Sham Kakade,
now at Microsoft Research New England
Former postdoc
Ryan Porter,
now at AMA Capital
Former postdoc
Luis Ortiz,
now on SUNY Stonybrook CS faculty
Former summer postdoctoral visitor
John Langford,
now at Microsoft Research NYC
TEACHING AND TUTORIAL MATERIAL
Web page for the undergraduate course
Networked Life (NETS 112), Fall 2014
and a condensed
online version at Coursera.
(See also the
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 a
graduate course on Computational Learning Theory, Fall 2012
(jointly taught with Jake Abernethy). Here is an
earlier version
(jointly taught 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
[Postscript]
[Compressed Postscript]
[PDF]
Course Outline and Material for
1999 Bellairs Institute Workshop
Theoretical Issues in
Probabilistic Artificial Intelligence
(FOCS 98 Tutorial)
[Postscript]
[Compressed Postscript]
[PDF]
A Short Course in Computational
Learning Theory: ICML '97 and AAAI '97 Tutorials
[Postscript]
[Compressed Postscript]
[PDF]
PRESS/MEDIA
Below are links to some press/media articles related to my work, or in which I am quoted.
(Some links are unfortunately now dead.)
MIT Technology Review article on Cloverpop
Bloomberg News article on HFT and hybrid quant funds, March 2014
Discussions of PAC and SQ learning and their relevance to evolution in
Les Valiant's book "Probably Approximately Correct", June 2013
NPR text and audio on Coursera, online education, and Penn, October 2012
Australian radio program "Future Tense" on "The Algorithm", March 2012
Chapter on biased voting experiments in Garth Sundem's book "Brain Trust",
2012.
ScienceNews article on Princeton fish consensus experiments,
December 2011.
A
profile
of and an
interview
with Les Valiant upon his receiving the 2010 Turing Award,
CACM June 2011.
Profile and lecture overview,
Christ's College Pieces, Lent Term 2011.
Fiscal Times article on machine learning and technology in trading, March 2011,
Wired Magazine article on algorithmic trading, January 2011,
and some
more extensive remarks
and
oneyear followup
on the author's blog.
Science News article on light speed propagation delays in trading, October 2010
Economist article on flash crash autopsy, October 2010
WSJ online post on HFT research, September 2010
Discussion of behavioral social network experiments in Peter Miller's "The Smart Swarm"
(Chapter 3, page 139 forward)
Atlantic article on HFT "crop circles", August 2010
Nature News article on "distributed thinking", August 2010
Wall Street Journal article on machine learning in quant trading, July 2010
and a
related interview on CNBC
New Scientist article on "Why Facebook friends are worth keeping", July 2010;
here is a
free reproduction
Philadelphia Business Journal article on the MKSE program and Networked Life, October 2009
Discussion of behavioral social network experiments in Christakis and Fowler's
"Connected" (page 165 foward)
Philadelphia Inquirer article on networked voting experiments, March 2009
Science Daily article on networked voting experiments, February 2009
The Trade magazine
article natural language processing for algorithmic trading, September 2007
Bloomberg Markets magazine
article on AI on Wall Street, June 2007
SIAM News article on behavioral graph
coloring, November 2006
Philadelphia Inquirer article on network science and
NSA link analysis, May 2006
Chicago Tribune article on privacy in blogs and social networks,
November 2005
Chronicle of Higher Education article on
Facebook and social networks,
May 2004
StarLedger article on the
demise of AT&T Labs, March 2004
Business Week Online article on technology in NASDAQ and
NYSE, September 2003
Philadelphia Inquirer article on ISTAR,
interdependent security, and games on networks, January 2003
Washington Post article on
webbased chatterbots, September 2002
New Scientist article
on the Cobot spoken dialogue system, August 2002
Tornado Insider article on DDoS attacks, January 2002
[Cover]
Tornado Insider article on biometric security, January 2002
Audio of COMNET panel "Staving Off DenialofService Attacks and Detecting Malicious Code"
Tornado Insider article on natural language technology, September 2001
Tornado Insider article on robotics, July 2001
Il Sole 24 Ore profile, June 2001
[English Translation]
Corriere Della Sera profile, May 2001
[English Translation]
Associated Press article on software robots, February 2001
New York Times article on TAC, August 2000
New York Times on Cobot, February 2000
TIME Digital Magazine (now Time On) on Cobot, May 2000
Washington Post article on Cobot, December 2000
New York Times article on boosting, August 1999
PUBLICATIONS:BOOKS

An Introduction to
Computational Learning Theory.
Authored jointly with Prof. Umesh V. 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.
[Postscript]
[Compressed Postscript]
[PDF]
PUBLICATIONS: 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 honored 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;
AISTATS: International Conference on Artificial Intelligence and Statistics;
ALT: Algorithmic Learning Theory;
COLT: Annual Conference on Computational Learning Theory;
EC: ACM Conference on Electronic Commerce;
FOCS: IEEE Foundations of Computer Science;
HCOMP: AAAI Conference on Human Computation and Crowdsourcing;
ICML: International Conference on Machine Learning;
IJCAI: International Joint Conference on Artificial Intelligence;
ITCS: Innovations in Theoretical Computer Science;
NIPS: Neural Information Processing Systems;
PNAS: Proceedings of the National Academy of Science; 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, this
DBLP query
or this
"faceted" version
seem to do a pretty good job of finding my publications that appeared in mainstream CS venues (albeit
with a bit of time lag), and can be useful for
generating bibtex citations.
And here is a listing of my publications generated by
Google Scholar.

Privacy and Truthful Equilibrium Selection for Aggregative Games.
With R. Cummings, A. Roth, and S. Wu.
Preprint, 2014.
[arXiv version]

Online Learning and Profit Maximization from Revealed Preferences.
With K. Amin, R. Cummings, L.Dworkin, and A. Roth.
Preprint, 2014.
[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 GoyalKearns 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 Federal Communications Commission, June 2014.
[PDF (on FCC website)]
[Ex Parte Cover Letter]

PursuitEvasion 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]

Mechanism Design in Large Games: Incentives and Privacy
With M. Pai, A. Roth, and J. Ullman.
ITCS 2014.
[PDF]
[arXiv version]

MarginalstoModels Reducibility.
With T. Roughgarden.
NIPS 2013.
[PDF]

Machine Learning for Market Microstructure and High Frequency Trading.
With Y. Nevmyvaka.
In 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]

StressInduced Changes in Gene Interactions in
Human Cells.
With R. Nayak, W. Bernal, J. Lee, and
V. Cheung. Nucleic Acids Research, 2013, 115.
[PDF]

DepthWorkload Tradeoffs for Workforce Organization.
With H. Heidari.
HCOMP 2013.
[PDF]

LargeScale 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]
[CACM Issue]

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 ThirdParty Randomization in RiskSensitive 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.
[Postscript]
[Compressed Postscript]
[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)
[Postscript]
[Compressed Postscript]
[PDF]
[CACM version]
[Peter Bartlett commentary]
[BofA marketing summary]

Networked Bargaining: Algorithms and Structural Results.
With T. Chakraborty and S. Khanna.
ACM EC 2009.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[PDF]

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

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

Behavioral Experiments in Networked Trade.
With S. Judd.
ACM EC 2008.
[Postscript]
[Compressed Postscript]
[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. EvenDar and J. Wortman.
WINE 2007.
The following longer version appeared in the
Third Workshop on Sponsored Search Auctions, WWW 2007.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[PDF]

A Network Formation Game for Bipartite Exchange Economies.
With E. EvenDar and S. Suri.
ACM SODA 2007.
[Postscript]
[Compressed Postscript]
[PDF]
[Extended Version, PDF]

PrivacyPreserving Belief Propagation and Sampling.
With J. Tan and J. Wortman.
NIPS 2007.
[Postscript]
[Compressed Postscript]
[PDF]

Regret to the Best vs. Regret to the Average.
With E. EvenDar, Y. Mansour, and J. Wortman.
COLT 2007.
(J. Wortman, COLT Best Student Paper Award)
[Postscript]
[Compressed Postscript]
[PDF]

A Small World Threshold for Economic Network Formation.
With E. EvenDar.
NIPS 2006.
[Postscript]
[Compressed Postscript]
[PDF]

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

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

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

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

RiskSensitive
Online Learning.
With E. EvenDar 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.
[Postscript]
[Compressed Postscript]
[PDF]

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

Economics, Computer Science, and Policy.
Issues in Science and Technology,
Winter 2005.
[Article in PDF]
[Cover Image]

Electronic Trading in OrderDriven 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.
[Postscript]
[Compressed Postscript]
[PDF]

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

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

Graphical Economics.
With S. Kakade and L. Ortiz.
Proceedings of COLT 2004.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[PDF]

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

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

The PennLehman Automated Trading Project.
With L. Ortiz.
IEEE Intelligent Systems, Nov/Dec 2003.
IEEE version [PDF]
Long version [Postscript]
Long version [Compressed Postscript]
Long version [PDF]

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

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

Efficient Nash Computation in Large Population Games
with Bounded Influence.
With Y. Mansour.
Proceedings of UAI 2002.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[PDF]

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

An Efficient Exact Algorithm
for Singly Connected Graphical Games.
With M. Littman, S. Singh. 2001. NIPS 2001.
[Postscript]
[Compressed Postscript]
[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 twopass algorithm can suffice). The
original polynomialtime
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.
[Postscript]
[Compressed Postscript]
[PDF]

ATTac2000: An
Adaptive Autonomous Bidding Agent.
With P. Stone, M. Littman, S. Singh.
Journal of Artificial Intelligence Research .
Earlier version in Proceedings of Agents 2001.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[PDF]

Nash Convergence of
Gradient Dynamics in GeneralSum Games.
With S. Singh, Y. Mansour.
Proceedings of the Sixteenth Conference on Uncertainty in
Artificial Intelligence, Morgan Kaufmann, pages 541548, 2000.
[Postscript]
[Compressed Postscript]
[PDF]

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

BiasVariance Error Bounds
for Temporal Difference Updates.
With S. Singh.
Proceedings of the 13th Annual Conference on
Computational Learning Theory, 2000,
pages 142147.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[PDF]

Testing Problems
with SubLearning Sample Complexity.
With D. Ron.
Journal of Computer and System Sciences,
61, pp. 428456, 2000.
Earlier version in Proceedings of the 12th Annual Workshop on
Computational Learning Theory.
[Postscript]
[Compressed Postscript]
[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. 3641, 2000, AAAI Press/MIT Press.
[Postscript]
[Compressed Postscript]
[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. 645651,
2000, AAAI Press/MIT Press.
[Postscript]
[Compressed Postscript]
[PDF]

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

A Boosting Approach to Topic
Spotting on Subdialogues.
With K. Myers, S. Singh, M. Walker.
Appeared in ICML 2000.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[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 309316.
[Postscript]
[Compressed Postscript]
[PDF]

A Sparse Sampling Algorithm for NearOptimal
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 13241331.
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 740747.
[Postscript]
[Compressed Postscript]
[PDF]

FiniteSample Rates of Convergence for
QLearning and Indirect Methods.
With S. Singh.
Advances in Neural Information Processing Systems 11,
The MIT Press,
1999,
pages 9961002.
[Postscript]
[Compressed Postscript]
[PDF]

Inference in Multilayer
Networks via Large Deviation Bounds.
with L. Saul.
Advances in Neural Information Processing Systems 11,
The MIT Press,
1999,
pages 260266.
[Postscript]
[Compressed Postscript]
[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 311319.
[Postscript]
[Compressed Postscript]
[PDF]

Exact Inference of Hidden
Structure from Sample Data in NoisyOR Networks.
With Y. Mansour.
Proceedings of the Fourteenth Conference on Uncertainty in
Artificial Intelligence,
Morgan Kaufmann,
1998,
pages 304310.
[Postscript]
[Compressed Postscript]
[PDF]

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

A Fast, BottomUp
Decision Tree Pruning Algorithm with NearOptimal
Generalization.
With Y. Mansour.
Proceedings of the 15th International Conference
on Machine Learning, 1998,
Morgan Kaufmann,
pages 269277.
[Postscript]
[Compressed Postscript]
[PDF]

An InformationTheoretic
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. 282293, 1997, Morgan Kaufmann.
[Postscript]
[Compressed Postscript]
[PDF]

Algorithmic
Stability and SanityCheck
Bounds for LeaveOneOut CrossValidation.
With D. Ron.
Neural Computation 11(6), pages 14271453, 1999.
Earlier version in Proceedings of the Tenth Annual Conference on
Computational Learning Theory,
ACM Press,
1997,
pages 152162.
[Postscript]
[Compressed Postscript]
[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.
[Postscript]
[Compressed Postscript]
[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. 96104, 1996, Morgan Kaufmann.
[Postscript]
[Compressed Postscript]
[PDF]

On the Boosting Ability of TopDown
Decision Tree Learning Algorithms.
With Y. Mansour.
Journal of Computer and Systems Sciences, 58(1), 1999,
pages 109128. Earlier version in
Proceedings of the 28th ACM Symposium on the
Theory of Computing, pp.459468, 1996, ACM Press.
[Postscript]
[Compressed Postscript]
[PDF]

A Bound on the Error of Cross
Validation Using
the Approximation and Estimation Rates, with Consequences for the
TrainingTest Split.
Neural Computation 9(5), 1997, pages 11431161.
Earlier version in Advances in Neural Information Processing Systems 8,
The MIT Press,
pages 183189,
1996.
[Postscript]
[Compressed Postscript]
[PDF]

An Experimental and Theoretical Comparison
of Model Selection Methods.
With Y. Mansour, A. Ng, and D. Ron.
Machine Learning 27(1), 1997, pages 750.
Earlier version in Proceedings of the
Eighth ACM Conference on Computational Learning Theory,
ACM Press,
1995,
pages 2130.
[Postscript]
[Compressed Postscript]
[PDF]

On the Consequences of the
Statistical Mechanics Theory of Learning Curves for
the Model Selection Problem.
Neural Networks: The Statistical Mechanics
Perspective, pp. 277284, 1995, World Scientific.
[Postscript]
[Compressed Postscript]
[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. 332341, 1995, IEEE Press.
[Postscript]
[Compressed Postscript]
[PDF]

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

On the Complexity of Teaching.
With S. Goldman.
Journal of Computer and Systems Sciences,
50(1), pp. 2031, 1995.
[Postscript]
[Compressed Postscript]
[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. 273282, 1994, ACM Press.
[Postscript]
[Compressed Postscript]
[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. 278291, 1994, SpringerVerlag.
[Postscript]
[Compressed Postscript]
[PDF]

Rigorous Learning
Curve Bounds from Statistical
Mechanics.
With D. Haussler, H.S. Seung, and N. Tishby.
Machine Learning,25, 1996,
pages 195236.
Earlier version in
ACM Conference
on Computational Learning Theory, pp. 7687, 1994,
ACM Press.
[Postscript]
[Compressed Postscript]
[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. 253262, 1994, ACM Press.
[Postscript]
[Compressed Postscript]
[PDF]

Efficient NoiseTolerant
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. 392401, 1993, ACM Press.
[Postscript]
[Compressed Postscript]
[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. 315324, 1993, ACM Press.
[Postscript]
[Compressed Postscript]
[PDF]

Learning from a Population of
Hypotheses.
With S. Seung. Machine Learning
18, pp. 255276, 1995. Earlier version in Proceedings of the
Sixth Annual Workshop on Computational Learning Theory,
pp. 101110, 1993, ACM Press.
[Postscript]
[Compressed Postscript]
[PDF]

Towards Efficient
Agnostic Learning.
With R. Schapire and L. Sellie.
Machine Learning 17, pp. 115141, 1994.
Earlier version in Proceedings of the Fifth Annual Workshop on
Computational Learning Theory, pp. 341352, 1992, ACM Press.
[Postscript]
[Compressed Postscript]
[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. 83113, 1994.
Earlier version in Proceedings of the Fourth Annual Workshop on Computational
Learning Theory, pp. 6174, 1991, Morgan Kaufmann.
[PDF]

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

Estimating AverageCase 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. 129161, 1991.
[PDF]

Efficient Distributionfree
Learning of Probabilistic Concepts.
With R. Schapire.
Journal of Computer and System Sciences
48(3), pp. 464497. Earlier version in Proceedings of the 31st Annual
IEEE Symposium on Foundations of Computer Science,
pp. 382391, 1990, IEEE Press.
[Postscript]
[Compressed Postscript]
[PDF]

Exact Identification of
Readonce Formulas Using Fixed
Points of Amplification Functions.
With S. Goldman and R. Schapire. SIAM Journal
on Computing 22(4), pp. 705726. Earlier version in
Proceedings of the 31st IEEE Symposium on Foundations
of Computer Science, pp. 193202, 1990, IEEE Press.
[Postscript]
[Compressed Postscript]
[PDF]

A PolynomialTime Algorithm for learning kvariable 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. 6795, 1994.
Earlier version in Proceedings of the 21st ACM Symposium on the Theory
of Computing, pp. 433444, 1989, ACM Press.
[Postscript]
[Compressed Postscript]
[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. 247261, 1989. Earlier version in Proceedings of the 1988 Workshop
on Computational Learning Theory,
pp. 139154, 1988, Morgan Kaufmann.
[Postscript]
[Compressed Postscript]
[PDF]

Learning in the Presence of
Malicious Errors.
With M. Li.
SIAM Journal on Computing 22(4), pp. 807837, 1993.
Earlier version in Proceedings of the 20th ACM Symposium on the
Theory of Computing, pp. 267280, 1988, ACM Press.
[Postscript]
[Compressed Postscript]
[PDF]

Thoughts on Hypothesis Boosting.
Unpublished manuscript, 1988. Project
for Ron Rivest's machine learning course at MIT.
[Postscript]
[Compressed Postscript]
[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. 285195,
1987, ACM Press.
[Postscript]
[Compressed Postscript]
[PDF]

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

Recent Results in Boolean
Concept Learning.
With M. Li, L. Pitt and L. Valiant.
Proceedings of the Fourth International Workshop
on Machine Learning, pp. 337352, 1987, Morgan Kaufmann.
[Postscript]
[Compressed Postscript]
[PDF]
Last Modified: October 1, 2014
www.digits.net
WM
3YC