home | research interests | survey talks

2017

• Collaborative PAC Learning. With Nika Haghtalab, Ariel Procaccia, and Mingda Qiao. NIPS 2017. We consider a collaborative PAC learning model, in which k players attempt to learn the same underlying concept. We ask how much more information is required to learn an accurate classifier for all players simultaneously. We refer to the ratio between the sample-complexity of collaborative PAC learning and the sample-complexity of single-player PAC learning as the overhead. We design learning algorithms with only O(ln k) and O((ln k)^2) overhead respectively in the personalized and centralized variants our model. In contrast, not sharing information among players would incur overhead O(k). We complement our upper bounds with an Omega(ln k) lower bound, showing that our results are tight up to a logarithmic factor.

• Lifelong Learning in Costly Feature Spaces. With Nina Balcan and Vaishnavh Nagarajan. ALT 2017. In this work we study lifelong and representation learning for structured target functions including decision trees and polynomials. More specifically, we consider learning a series of target functions, where each can be represented as, say, a decision tree, and all these decision trees share pieces in common that we call "meta-features". As we learn target functions, our aim is to learn these meta-features in a way that allows us to learn new target functions more cheaply. We specifically focus on reducing the number of feature evaluations that need to be performed in the learning process, motivated by applications such as medical diagnosis where decision trees are popular in part due to their ability to make predictions based on a small number of features of any given example.

• Efficient Co-Training of Linear Separators under Weak Dependence. With Yishay Mansour. COLT 2017. We develop the first polynomial-time algorithm for co-training of homogeneous linear separators under weak dependence, a relaxation of the condition of independence given the label. Our algorithm learns from purely unlabeled data, except for a single labeled example to break symmetry of the two classes, and works for any data distribution having an inverse-polynomial margin and with center of mass at the origin.

• Efficient PAC Learning from the Crowd. With Pranjal Awasthi, Nika Haghtalab, and Yishay Mansour. COLT 2017. Standard approaches to crowdsourcing view the process of acquiring labeled data separately from the process of learning a classifier, which can lead to computational and statistical inefficiencies. For example, learning from poorly-labeled data can be computationally hard, and efforts to eliminate noise through voting often require a large number of queries per example. In this paper, we show how by interleaving the process of labeling and learning, we can attain computational efficiency with much less overhead in the labeling cost. In particular, we consider a setting where a certain alpha fraction of labelers actually know the true target function and label data correctly, whereas the remaining 1-alpha fraction have other arbitrary functions in mind. When alpha is greater than 1/2, we show that any class that can be efficiently PAC-learned from non-noisy data can still be efficiently learned in this setting with only a constant-factor blowup in total number of labels requested. When alpha is less than 1/2, we can do this with only an additional constant number of queries to a known-correct labeling oracle. All algorithms require asking any given labeler only O(1) labeling questions.

• Opting into Optimal Matchings. With Ioannis Caragiannis, Nika Haghtalab, Ariel Procaccia, Eviatar Procaccia, and Rohit Vaish. SODA 2017, pages 2351-2363. We consider design of optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs). In particular, each player---who is associated with a subset of vertices---should be guaranteed to match at least as many of his own vertices when he opts into the matching mechanism as when he opts out. We offer a new perspective on this problem by considering an arbitrary graph, but assuming that vertices are associated with players at random. Our main result is that under certain conditions, any fixed optimal matching is likely to be individually rational up to lower-order terms. We also show that a simple and practical mechanism is (fully) individually rational, and likely to be optimal up to lower-order terms. We discuss the implications of our results for market design in general, and kidney exchange in particular.

2016

• Sparse Approximation via Generating Point Sets. With Sariel Har-Peled and Benjamin Raichel. SODA 2016. We consider the following problem: given a collection P of n objects (represented as points in the unit ball in R^d), find a small subset T of P such that each object in P is close to a sparse convex combination of objects in T. E.g., if we allow T=P then this is trivial with sparsity 1, and for some sets P (e.g., random points in the unit ball) there is no such small set T. Let k_opt = k_opt(P,epsilon) be the size of the smallest subset T_opt such that every point in P is within distance epsilon of the convex hull of T_opt. Our goal is to find a set T of k_alg points and distance epsilon_alg such that every point in P is within distance epsilon_alg to a sparse combination of points in T, where k_alg and epsilon_alg are not too much larger than k_opt and epsilon_opt. We give several efficient algorithms with different guarantees of this form.

• On the Computational Hardness of Manipulating Pairwise Voting Rules. With Rohit Vaish, Neeldhara Misra, and Shivani Agarwal. AAMAS 2016, pages 358-367. In this work we study the computational tractability of manipulating voting rules when the input is a collection of incomplete pairwise preferences. We show that in this scenario, manipulation can be computationally hard even for a single manipulator.

• Semi-Supervised Learning. Entry in the Encyclopedia of Algorithms, pages 1936-1941, 2016.

2015

• Efficient Representations for Lifelong Learning and Autoencoding. With Nina Balcan and Santosh Vempala. COLT 2015. In this work we pose and provide efficient algorithms for several natural theoretical formulations of life-long learning. Specifically, we consider the problem of learning many different target functions over time, that share certain commonalities that are initially unknown to the learning algorithm. Our aim is to learn new internal representations as the algorithm learns new target functions, that capture this commonality and allow subsequent learning tasks to be solved more efficiently and from less data. We develop efficient algorithms for two very different kinds of commonalities that target functions might share: one based on learning common low-dimensional and unions of low-dimensional subspaces and one based on learning nonlinear Boolean combinations of features. Our algorithms for learning Boolean feature combinations additionally have a dual interpretation, and can be viewed as giving an efficient procedure for constructing near-optimal sparse Boolean autoencoders under a natural "anchor-set" assumption.

• The Ladder: A Reliable Leaderboard for Machine Learning Competitions. With Moritz Hardt. ICML 2015. We consider the problem of maintaining an accurate leaderboard for a machine learning competition that faithfully represents the quality of the best submission of each competing team. What makes this challenging is that participants may repeatedly evaluate their submissions on the leaderboard, and in the process overfit to the holdout data that supports it. Moreover, we (the organizers) cannot control the capacity or complexity of the rules participants are using. In this work, we introduce a notion of leaderboard accuracy tailored to the format of a competition. We introduce a natural algorithm called the Ladder and demonstrate that it simultaneously supports strong theoretical guarantees in a fully adaptive model of estimation, withstands practical adversarial attacks, and achieves high utility on real submission files from a Kaggle competition. Notably, we are able to sidestep a powerful recent hardness result for adaptive risk estimation that rules out algorithms such as ours under a seemingly very similar notion of accuracy. On a practical note, we provide a parameter-free variant of our algorithm that can be easily deployed.

• Learning What's Going On: Reconstructing Preferences and Priorities from Opaque Transactions. With Yishay Mansour and Jamie Morgenstern. ACM-EC 2015. We consider a setting where n buyers, with combinatorial preferences over m items, and a seller, running a priority-based allocation mechanism, repeatedly interact. Our goal, from observing limited information about the results of these interactions, is to reconstruct both the preferences of the buyers and the mechanism of the seller. More specifically, we consider an online setting where at each stage, a subset of the buyers arrive and are allocated items, according to some unknown priority that the seller has among the buyers. Our learning algorithm observes only which buyers arrive and the allocation produced (or some function of the allocation, such as just which buyers received positive utility and which did not), and its goal is to predict the outcome for future subsets of buyers. We derive mistake bound algorithms for additive, unit-demand and single minded buyers. We also consider the case where buyers' utilities for a fixed bundle can change between stages due to different (observed) prices.

• Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries. With John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, and Ankit Sharma. ACM-EC 2015. We consider the problem of finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. More specifically, we are given an initial graph G, where each edge may be "faulty" (succeeding or failing independently with success probability p) and we have the ability to query edges to determine which have succeeded or failed. We give algorithms that from a limited number of queries, and a limited number of rounds of queries, can find a matching nearly as high as the true maximum matching in the graph of live edges. Our motivation comes from the problem of kidney exchange, and we also empirically explore the application of (adaptations of) these algorithms to the kidney exchange problem, where patients with end-stage renal failure swap willing but incompatible donors. We show on both generated data and on real data from the first 169 match runs of the UNOS nationwide kidney exchange that even a very small number of non-adaptive edge queries per vertex results in large gains in expected successful matches.

• Commitment Without Regrets: Online Learning in Stackelberg Security Games. With Nina Balcan, Nika Haghtalab, and Ariel D. Procaccia. ACM-EC 2015. In a Stackelberg Security Game, a defender commits to a randomized deployment of security resources, and an attacker best-responds by attacking a target that maximizes his utility. Here, we consider the case that there are k different types of attackers (each type has its own payoff matrix) and that a series of attackers of these types are arriving over time. After each attacker arrives, the defender receives some feedback (observing either the current attacker type or merely which target was attacked). We design no-regret algorithms whose regret (when compared to the best fixed strategy in hindsight) is polynomial in the parameters of the game, and sublinear in the number of time steps.

• Privacy-preserving Public Information in Sequential Games. With Jamie Morgenstern, Ankit Sharma, and Adam Smith. ITCS 2015. We consider settings where competitors for limited resources want to maintain privacy of their actions and yet also coordinate so as to not all chase the same resources and end up with low overall social welfare. We consider a sequential-move setting and explore whether "noisy" information about the current state can be publicly announced in a manner that both (a) provably maintains privacy and (b) sufficies to keep play from reaching bad game-states. We show that in many games of interest, this is indeed possible. We model behavior of players in this imperfect information setting in two ways -- greedy and undominated strategic behaviors, and we prove guarantees on social welfare that certain kinds of privacy-preserving information can help attain. Furthermore, we design a counter with improved privacy guarantees under continual observation.

• Learning Valuation Distributions from Partial Observation. With Yishay Mansour and Jamie Morgenstern. AAAI 2015. Auction theory traditionally assumes that bidders' valuation distributions are known to the auctioneer, such as in the revenue-optimal Myerson auction. However, this theory does not describe how the auctioneer comes to possess this information. In this work, we consider the problem of learning bidders' valuation distributions from much weaker forms of observations. Specifically, we consider a setting where there is a repeated sealed-bid auction, where all we can observe for each round is who won, but not how much they bid or paid. We can also participate (i.e., submit a bid) ourselves, and observe when we win. From this information, our goal is to (approximately) recover the inherently recoverable part of the underlying bid distributions for each bidder. We also consider extensions where different subsets of bidders participate in each round, and where bidders' valuations have a common-value component added to their independent private values.

• Online Allocation and Pricing with Economies of Scale. With Yishay Mansour and Liu Yang. WINE 2015. We consider the problem of online allocation of goods that have a decreasing marginal cost per item to the seller, when customers are unit-demand and arrive one at a time, each with a valuation function on items sampled iid from some unknown distribution over valuation functions. Our strategy operates by using an initial sample to learn enough about the distribution to determine how best to allocate to future customers, together with an analysis of structural properties of optimal solutions that allow for uniform convergence analysis. We show, for instance, if customers have {0,1} valuations over items, and the goal of the allocator is to give each customer an item he or she values, we can efficiently produce such an allocation with cost at most a constant factor greater than the minimum over such allocations in hindsight, so long as the marginal costs do not decrease too rapidly. We also give a bicriteria approximation to social welfare for the case of more general valuation functions when the allocator is budget constrained.

2014

• Active Learning and Best-Response Dynamics. With Nina Balcan, Chris Berlind, Emma Cohen, Kaushik Patnaik, and Le Song. Proc. 27th Annual Conference on Neural Information Processing Systems (NIPS) 2014. We examine a setting where low-power distributed sensors are each making highly noisy measurements of some unknown target function. A center wants to accurately learn this function by querying a small number of sensors, which ordinarily would be impossible due to the high noise rate. The question we address is whether local communication among sensors, together with natural best-response dynamics in an appropriately-defined game, can denoise the system without destroying the true signal and allow the center to succeed from only a small number of active queries. By using techniques from game theory and empirical processes, we prove positive (and negative) results on the denoising power of several natural dynamics. We then show experimentally that when combined with recent agnostic active learning algorithms, this process can achieve low error from very few queries, performing substantially better than active or passive learning without these denoising dynamics as well as passive learning with denoising.

• Learning Mixtures of Ranking Models. With Pranjal Awasthi, Or Sheffet, and Aravindan Vijayaraghavan. Proc. 27th Annual Conference on Neural Information Processing Systems (NIPS) 2014. This work concerns the problem of learning probabilistic models for ranking data in a heterogeneous population. The specific problem we study is learning the parameters of a Mallows Mixture Model. Despite being widely studied, current heuristics for this problem do not have theoretical guarantees and can get stuck in bad local optima. We present the first polynomial time algorithm which provably learns the parameters of a mixture of two Mallows models. A key component of our algorithm is a novel use of tensor decomposition techniques to learn the top-k prefix in both the rankings. Before this work, even the question of identifiability in the case of a mixture of two Mallows models was unresolved.

• Learning Optimal Commitment to Overcome Insecurity. With Nika Haghtalab and Ariel Procaccia. Proc. 27th Annual Conference on Neural Information Processing Systems (NIPS) 2014. Algorithms for Stackelberg security games compute an optimal strategy for the defender to commit to under the assumption the attacker will best-respond. Doing so generally requires knowledge of what the attacker's payoffs are. In this work, we design an algorithm that optimizes the defender's strategy with no prior information, by observing the attacker's responses to randomized deployments of resources and learning his priorities. In contrast to previous work, our algorithm requires a number of queries that is polynomial in the representation of the game.

• Lazy Defenders Are Almost Optimal Against Diligent Attackers. With Nika Haghtalab and Ariel Procaccia. Proc. 28th AAAI Conference on Artificial Intelligence (AAAI), 2014.
  Most work on Stackelberg security games assumes that the attacker can perfectly observe (and therefore will optimally respond to) the defender's randomized assignment of resources to targets. This assumption has been challenged by recent papers, which designed tailor-made algorithms that compute optimal defender strategies for security games with limited surveillance. We analytically demonstrate that in zero-sum security games, lazy defenders, who simply keep optimizing against perfectly informed attackers, are almost optimal against a wide range of attackers with more limited information. This result suggests that in many cases limited surveillance may not need to be explicitly addressed.

• Estimating Accuracy from Unlabeled Data . With Anthony Platanios (lead author) and Tom Mitchell. UAI 2014.
  We propose an approach for using unlabeled data to estimate the true accuracy of learned classifiers, given access to multiple classifiers making different "kinds" of errors. We first show how to estimate error rates exactly from unlabeled data when given at least three classifiers that make independent errors, based on their rates of agreement. We then show that even when the competing classifiers do not make independent errors, both their accuracies and error dependencies can be estimated by making certain relaxed assumptions. Experiments on two real-world data sets produce estimates within a few percent of the true accuracy, using solely unlabeled data.

2013

• Fast Private Data Release Algorithms for Sparse Queries. With Aaron Roth. RANDOM 2013.
  We revisit the problem of accurately and efficiently answering large classes of statistical queries while preserving differential privacy. In this paper we consider the class of sparse queries, which take non-zero values on only polynomially many universe elements. We give efficient query release algorithms for this class, in both the interactive and the non-interactive setting. Our algorithms also achieve better accuracy bounds than existing general techniques do when applied to sparse queries in that our bounds are independent of the universe size. In fact, even the runtime of our interactive mechanism is independent of the universe size, and so can be implemented in the ``infinite universe'' model in which no finite universe need be specified by the data curator.

• Exploiting Ontology Structures and Unlabeled Data for Learning. With Nina Balcan and Yishay Mansour. ICML 2013.
  We present and analyze a theoretical model designed to understand and explain the effectiveness of ontologies for learning multiple related tasks from primarily unlabeled data, motivated by the success of the CMU NELL (Never-Ending Language Learning) system. We present both information-theoretic results as well as efficient algorithms. We show in this model that an ontology, which specifies the relationships between multiple outputs, in some cases is sufficient to completely learn a classification using a large unlabeled data source. (The paper linked to here is a longer version of what appears in ICML2013).

• Harnessing the Power of Two Crossmatches. With Anupam Gupta, Ariel Procaccia, and Ankit Sharma. ACM-EC 2013.
  Kidney exchanges allow incompatible donor-patient pairs to swap kidneys, but each donation must pass three tests: blood, tissue, and crossmatch. In practice a matching is computed based on the first two tests, and then a single crossmatch test is performed for each matched patient. In this paper, we ask: if we were allowed to perform two crossmatches per patient, how could we best do so to maximize the number of matched patients? Our main result is a polynomial time algorithm for this problem that almost surely computes optimal --- up to lower order terms --- solutions on random large kidney exchange instances.

• Differentially Private Data Analysis of Social Networks via Restricted Sensitivity. With Jeremiah Blocki, Anupam Datta, and Or Sheffet. ITCS 2013.
  We introduce the notion of restricted sensitivity as an alternative to global and smooth sensitivity to improve accuracy in differentially private data analysis. Restricted sensitivity is similar to global sensitivity except instead of quantifying over all possible datasets, we take advantage of any beliefs about the dataset that a querier may have, to quantify over only a restricted class of datasets. Specifically, given a query f and a hypothesis H about the structure of a dataset D, we show generically how to transform f into a new query f_H whose global sensitivity (over all datasets including those that do not satisfy H) matches the sensitivity of f only over deviations that remain within H. Moreover, if the belief of the querier is correct (i.e., D is in H) then f_H(D) = f(D). Thus, we maintain privacy whether or not D is in H and (when restricted sensitivity is low) provide accurate results in the event that H holds true. We then demonstrate the usefulness of this notion by applying it to the task of answering queries regarding social-networks, in both edge-adjacency and vertex-adjacency models.

• Learnability of DNF with Representation-Specific Queries. With Liu Yang and Jaime Carbonell. ITCS 2013.
  We study the problem of PAC learning the class of DNF formulas with the aid of pairwise queries that, given two positive examples, return whether or not the examples satisfy at least one term in common in the target formula. We also consider numerical queries that return the number of terms in common satisfied by the two examples. We provide both positive and negative results for learning with such queries under both uniform and general distributions. For example, for boolean queries, we show that learning an arbitrary DNF target under an arbitrary distribution is no easier than in the traditional PAC model. On the other hand, for numerical queries, we show we can learn arbitrary DNF formulas under the uniform distribution, and in the process, we give an algorithm for learning a sum of monotone terms from labeled data only. We also present a number of results for various DNF subclasses.

2012

• Active Property Testing. With Nina Balcan, Eric Blais, and Liu Yang. FOCS 2012. [arXiv (full version)]
  In this work, we define, analyze, and develop algorithms for the problem of property testing in a framework motivated by active learning. In this framework (as in most machine learning applications), one cannot obtain labels for arbitrary points in the input space; instead, one can only request labels from points in a given (polynomially) large unlabeled sample taken from the underlying distribution. We present both general results for this model as well as testers for various important classes. For example, we show that testing unions of d intervals can be done with O(1) label requests in this setting, a result that also yields improvements in both the full query and passive testing models as well. For testing linear separators in R^n over the Gaussian distribution, we show that both active and passive testing can be done with O(sqrt(n)) queries, substantially less than the Omega(n) needed for learning, with near-matching lower bounds. We also present a method for building testable properties out of others in this model, which we then use to provide testers for a number of assumptions used in semi-supervised learning. Finally, we develop a general notion of the testing dimension of a given property with respect to a given distribution, that we show characterizes (up to constant factors) the intrinsic number of label requests needed to test that property. We then use these dimensions to prove a number of lower bounds, including for linear separators and the class of dictator functions. Our work brings together tools from a range of areas including U-statistics, noise-sensitivity, self-correction, and spectral analysis of random matrices, and develops new tools that may be of independent interest.

• The Johnson-Lindenstrauss transform itself preserves differential privacy. With Jeremiah Blocki, Anupam Datta, and Or Sheffet (lead author). FOCS 2012.
  We show that the Johnson-Lindenstrauss transform provides a novel way of preserving differential privacy. In particular, if we take two databases, D and D', such that (i) D'-D is a rank-1 matrix of bounded norm and (ii) all singular values of D and D' are sufficiently large, then multiplying either D or D' with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a (S,V-S)-cut in a graph. We show that the JL transform allows us to publish a sanitized graph that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only O(|S|/epsilon) random noise to any given query w.h.p. Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform other methods on small cuts (|S| = o(n)). We also apply our technique to the task of estimating the variance of a given matrix in any given direction.

• Additive Approximation for Near-perfect Phylogeny Construction. With Pranjal Awasthi, Jamie Morgenstern, and Or Sheffet. APPROX 2012. [arXiv]
  We study the problem of constructing phylogenetic trees for a given set of species, formulated as that of finding a minimum Steiner tree on n points over the Boolean hypercube of dimension d. It is known that an optimal tree can be found in linear time if there is a perfect phylogeny: i.e., the cost of the optimal phylogeny is exactly d (deleting irrelevant coordinates). Moreover, if the data is a near-perfect phylogeny--the cost of the optimal tree is d+q for small q--it is known that an exact solution can be found in time polynomial in n and d, but exponential in q [BDHRS06]. Here, we give an algorithm running time time polynomial in n, d, and q that finds a phylogenetic tree of cost d+O(q^2). We also discuss the motivation and reasoning for studying such additive approximations.

• Distributed Learning, Communication Complexity, and Privacy. With Nina Balcan, Shai Fine, and Yishay Mansour. COLT 2012.
  Suppose you have two databases: one with the positive examples and another with the negative examples. How much communication between them is needed to learn a good hypothesis? In this work we examine this basic question and its generalizations, as well as related issues such as privacy. Broadly, we consider a framework where data is distributed among several locations, and our goal is to learn a low-error hypothesis over the joint distribution using as little communication, and as few rounds of communication, as possible. Our general results show that in addition to VC-dimension and covering number, quantities such as the teaching-dimension and mistake-bound of a class play an important role in determining communication requirements. Moreover, boosting can be performed in a generic manner in the distributed setting to achieve communication with only logarithmic dependence on 1/epsilon for any concept class. We also present tight results for a number of common specific concept classes including conjunctions, parity functions, and decision lists. For linear separators, we show that for non-concentrated distributions, we can use a version of the Perceptron algorithm to learn with much less communication than the number of updates given by the usual margin bounds. We additionally present an analysis of privacy, considering both differential privacy and a notion of distributional privacy that is especially appealing in this context.

2011

• Welfare and Profit Maximization with Production Costs. With Anupam Gupta, Yishay Mansour, and Ankit Sharma. FOCS, 2011.
  Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize social welfare or profit. The problem has been well-studied in the case of limited supply (one copy of each item), and in the case of digital goods (the seller can produce additional copies at no cost). Yet in the case of resources---oil, labor, computing cycles, etc.---neither of these abstractions is just right: additional supplies of these resources can be found, but at increasing difficulty (marginal cost) as resources are depleted. In this work, we initiate the study of combinatorial pricing under increasing marginal cost. The goal is to sell these goods, using posted prices, to buyers arriving online with unknown and arbitrary combinatorial valuation functions to maximize either the social welfare, or the seller's profit. We give algorithms that achieve constant factor approximations for a class of natural cost functions---linear, low-degree polynomial, logarithmic---and that give logarithmic approximations for more general increasing marginal cost functions (along with a necessary additive loss). We show that these bounds are essentially best possible for these settings.

• Center-based Clustering under Perturbation Stability. With Pranjal Awasthi and Or Sheffet. Information Processing Letters, 112(1-2):49-54, Jan 2012. doi:10.1016/j.ipl.2011.10.002
  In this paper we give algorithms for k-median, k-means, and other center-based clustering objectives, for instances that are stable to small constant-factor perturbations of the input. This notion of stability was studied by Bilu and Linial [BL10] in the context of the max-cut problem, where they showed that one could optimally solve max-cut instances stable to perturbations of size sqrt(n). In this work we show that stability to factor-3 perturbations is sufficient to find optimal solutions for any center-based clustering objective (such as k-median, k-means, and k-center) in the case of finite metrics without Steiner points, and that stability to factor 2 + sqrt(3) perturbations is sufficient for the case of general metrics. Specifically, we show that for such instances, the popular Single-Linkage algorithm combined with dynamic programming will find the optimal clustering.

2010

• A Discriminative Model for Semi-Supervised Learning. With Nina Balcan. JACM Vol 57, Issue 3, 2010. This is an expanded and more in-depth version of our COLT'05 paper "A PAC-style Model for Learning from Labeled and Unlabeled Data". See details below.

• Trading off Mistakes and Don't-Know Predictions. With Amin Sayedi and Morteza Zadimoghaddam. NIPS 2010.
  We consider an online learning framework in which the agent is allowed to say ``I don't know'' and analyze the achievable tradeoffs between saying ``I don't know'' and making mistakes. If mistakes have the same cost as don't-knows, the model reduces to the standard mistake-bound model, and if mistakes have infinite cost, the model reduces to KWIK framework introduced by Li, Littman, and Walsh. We propose a general, though inefficient, algorithm for general finite concept classes that minimizes the number of don't-know predictions subject to a given bound on the number of allowed mistakes. We then present specific polynomial-time algorithms for the concept classes of monotone disjunctions and linear separators with a margin.

• Stability yields a PTAS for k-Median and k-Means Clustering. With Pranjal Awasthi and Or Sheffet. FOCS 2010. [longer version]
  Ostrovsky et al. [ORSS06] show that given n points in Euclidean space such that the optimal (k-1)-means clustering is a factor 1/epsilon^2 more expensive than the best k-means clustering, one can get a (1+f(epsilon))-approximation to k-means in time poly(n,k) by using a variant of Lloyd's algorithm. In this work we show we can replace the "1/epsilon^2" with just "1+alpha" for any constant alpha>0 and obtain a PTAS. In particular, under this assumption, for any epsilon>0 we can achieve a 1+epsilon approximation for k-means in time polynomial in n and k, and exponential in 1/epsilon and 1/alpha (our running time is n^O(1) * (k log n)^poly(1/epsilon,1/alpha).). We thus decouple the strength of the assumption from the quality of the approximation ratio. We give a PTAS for k-median in finite metrics under the analogous assumption. We also show we can obtain a PTAS under the assumption of Balcan-Blum-Gupta09 (see below) that all 1+alpha approximations are delta-close to a desired target clustering, in the case that all target clusters have size greater than 2delta n and alpha is constant. Note that the point of BBG09 is that the true goal in clustering is usually to get close to the target rather than to achieve a good objective value. From this perspective, our advance is that for k-means in Euclidean spaces we reduce the distance of the clustering found to the target from O(delta) to delta when all target clusters are large, and for k-median we improve the "largeness" condition in BBG09 needed to get exactly delta-close from O(delta*n) to delta*n. Our results are based on a new notion of clustering stability.

• On Nash-Equilibria of Approximation-Stable Games. With Pranjal Awasthi, Nina Balcan, Or Sheffet and Santosh Vempala. SAGT 2010. Journal version in Current Science, Vol 103, Issue 9, November 10, 2012.
  In this paper, we define the notion of games that are approximation stable, meaning that all epsilon-equilibria are contained inside a small ball of radius Delta around a true equilibrium, which is a natural condition if you want play to be predictable even if players are only at approximate equilibrium. Many natural small games such as matching pennies and rock-paper-scissors are indeed approximation stable. We show both upper and lower bounds on size of supports of approximate equilibria in such games, yielding more efficient algorithms for computing approximate equilibria as Delta gets close to epsilon. We also consider an inverse condition, namely that all non-approximate equilibria are far from some true equilibrium, and give an efficient algorithm for games satisfying that condition.

• Improved Guarantees for Agnostic Learning of Disjunctions. With Pranjal Awasthi and Or Sheffet. COLT 2010.
  Given some arbitrary distribution D over {0,1}^n and arbitrary target function c, the goal in agnostic learning of disjunctions is to achieve an error rate comparable to the error OPT of the best disjunction with respect to (D,c). In recent work, [Peleg07] shows how to achieve a bound of O(sqrt(n)*OPT) + epsilon in polynomial time. In this paper we improve on Peleg's bound, giving a polynomial-time algorithm achieving a bound of O(n^{1/3 + alpha}*OPT) + epsilon, for any constant alpha>0. The heart of the algorithm is a method for weak-learning when OPT = O(1/n^{1/3+alpha}), which can then be fed into existing agnostic boosting procedures to achieve the desired guarantee.

• Circumventing the Price of Anarchy: Leading Dynamics to Good behavior. With Nina Balcan and Yishay Mansour. ICS 2010. Journal version combining this work and "Improved equilibria via public service advertising" (SODA 2009) appears in SIAM J. Computing, 42(1), 230-264, 2013.
  We explore the problem of how self-interested agents with some knowledge of the game might be able to quickly find their way to states of quality close to the best equilibrium in games with high price of anarchy but low price of stability. We consider two natural learning models in which players adaptively decide between greedy behavior and following a proposed good but untrusted strategy and analyze two important classes of games in this context, fair cost-sharing and consensus games. These games both have very high Price of Anarchy and yet we show that behavior in these models can efficiently reach low-cost states.

2009

• Thoughts on Clustering . Essay for the 2009 NIPS Workshop "Clustering: Science or Art?"

• Tracking Dynamic Sources of Malicious Activity at Internet-Scale. With Shobha Venkataraman, Dawn Song, Subhabrata Sen, and Oliver Spatscheck. NIPS 2009.
  We consider the problem of discovering dynamic malicious regions on the Internet. We model this problem as one of adaptively pruning a known decision tree (in particular, the IP address-space tree), but with additional challenges: (1) severe space requirements, since the underlying decision tree has over 4 billion leaves, and (2) a changing target function, since malicious activity on the Internet is dynamic. We present a novel algorithm that addresses this problem, by combining "experts" and online paging algorithms. We prove guarantees on our algorithm's performance as a function of the best possible pruning of a similar size, and our experiments show that our algorithm achieves high accuracy on large real-world data sets, improving over existing approaches.

• The Price of Uncertainty. With Nina Balcan and Yishay Mansour. ACM-EC 2009. [slides]
  We study the degree to which small fluctuations in costs in well-studied potential games can impact the result of natural best-response and improved-response dynamics. We consider a wide variety of potential games including fair cost-sharing games, set-cover games, routing games, and job-scheduling games. We show that in certain cases, even extremely small fluctuations can cause these dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large degrees of fluctuation. We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show that in certain cases (e.g., fair cost-sharing, set-covering, job-scheduling) even a single Byzantine player can cause best-response dynamics to transition to states of substantially higher cost, whereas in others (e.g., the class of beta-nice games which includes routing, market-sharing and many others) these dynamics are much more resilient.

• Approximate Clustering without the Approximation. With Nina Balcan and Anupam Gupta. SODA 2009. Journal version: Clustering Under Approximation Stability, JACM, Volume 60, Issue 2, April 2013. [unofficial local copy]
  For most clustering problems, our true goal is to classify the points correctly, and commonly studied objectives such as k-median, k-means, and min-sum are really only a proxy. That is, there is some unknown correct clustering (grouping proteins by their function or grouping images by who is in them) and the implicit hope is that approximately optimizing these objectives will in fact produce a clustering that is close pointwise to the correct answer. In this paper, we show that if we make this implicit assumption explicit---that is, if we assume that any c-approximation to the given clustering objective F is epsilon-close to the target---then we can produce clusterings that are O(epsilon)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, for k-median and k-means objectives, we show that we can achieve this guarantee for any constant c > 1, and for min-sum objective we can do this for any constant c > 2. Our results also highlight a difference between assuming that the optimal solution to, say, the k-median objective is epsilon-close to the target, and assuming that any approximately optimal solution is epsilon-close to the target. In the former case, the problem of finding a solution that is O(epsilon)-close to the target remains computationally hard, and yet for the latter we have an efficient algorithm.

• Improved Equilibria via Public Service Advertising. With Nina Balcan and Yishay Mansour. SODA 2009.
  Many natural games have both good and bad Nash equilibria. In such cases, one could hope to improve poor behavior by a "public service advertising campaign" encouraging players to follow a good equilibrium, and if every player follows the advice then we are done. However, it is a bit much to assume that everyone will follow along. In this paper we consider the question of to what extent can such an advertising campaign cause behavior to switch from a bad equilibrium to a good one even if only a fraction of people actually follow the given advice, and do so only temporarily. Unlike in the ``value of altruism'' model, we assume everyone will ultimately act in their own interest. We analyze this question for several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, and party affiliation games (which include consensus and cut games). We show that for some of these games (such as fair cost sharing), a random alpha fraction of the population following the given advice is sufficient to get a guarantee within an O(1/alpha) factor of the price of stability for any alpha > 0. However, for some games (such as party affiliation games), there is a strict threshold (in this case, alpha < 1/2 yields almost no benefit, yet alpha > 1/2 is enough to reach near-optimal behavior), and for some games, such as scheduling, no value alpha < 1 is sufficient.

2008

• Clustering with Interactive Feedback. With Nina Balcan. ALT 2008.
  We initiate a theoretical study of the problem of clustering data under interactive feedback. We introduce a query-based model in which users can provide feedback to a clustering algorithm in a natural way via split and merge requests. We then analyze the ``clusterability'' of different concept classes in this framework --- the ability to cluster correctly with a bounded number of requests under only the assumption that each cluster can be described by a concept in the class --- and provide efficient algorithms as well as information-theoretic upper and lower bounds.

• Improved Guarantees for Learning via Similarity Functions. With Nina Balcan and Nati Srebro. COLT 2008.
  We provide a new broader notion of a "good similarity function" that improves in two important ways upon the notion in [BB06]. First, as before, any large-margin kernel is also a good similarity function in our sense, but now with a much milder degradation of the parameters. Second, we can show that for distribution-specific PAC learning, the new notion is strictly more powerful that the traditional notion of a large-margin kernel: although any concept class that can be learned with some kernel function can also be learned using our new similarity based approach, the reverse is not true. (In contrast, the [BB06] definition is no more powerful than kernels for distribution-specific learning.) Our new notion of similarity relies upon L_1 regularized learning, and our separation result is related to a separation result between what is learnable with L_1 vs. L_2 regularization.

• Item Pricing for Revenue Maximization. With Nina Balcan and Yishay Mansour. ACM-EC 2008.
  This paper considers the problem of pricing items to maximize revenue from buyers with unknown complex preferences over bundles, and presents two main results. (1) for the case of unlimited supply, a random single price achieves a logarithmic approximation for buyers with general valuation functions (not just single-minded or unit-demand as was previously known). (2) for the case of limited supply, a random single price (with buyers arriving in an arbitrary order) achieves an exp(sqrt(log(n)loglog(n))) approximation, with a near-matching lower bound. Also includes results for multi-unit auctions and "simple submodular" valuations. An earlier tech report with just the first result appears here.

• A Discriminative Framework for Clustering via Similarity Functions. With Nina Balcan and Santosh Vempala. STOC 2008. [full version (2009)]
  Theoretical treatments of clustering from pairwise similarity information typically view the similarity information as ground-truth and then design algorithms to (approximately) optimize various graph-based objective functions. However, in most applications, this similarity information is merely based on some heuristic: the true goal is to cluster the points correctly rather than to optimize any specific graph property. In this work, we develop a theoretical framework for clustering from this perspective. In particular, motivated by work in learning theory that asks ``what natural properties of a similarity (or kernel) function are sufficient to be able to learn well?'' we ask ``what natural properties of a similarity function are sufficient to be able to cluster well?'' Our approach can be viewed as developing a PAC model for clustering, where the natural object of study, rather than being a concept class, is more like a class of (concept, distribution) pairs.

• Regret Minimization and the Price of Total Anarchy. With MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth. STOC 2008.
  This paper proposes weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium, we assume only that selfish players play so as to minimize their own regret. Regret minimization can be done via simple, efficient algorithms even in many settings where the number of action choices for each player is exponential in the natural parameters of the problem. We prove that despite our weakened assumptions, in several broad classes of games, this ``price of total anarchy'' matches the Nash price of anarchy, even though play may never converge to Nash equilibrium. We also show that the price of total anarchy is in many cases resilient to the presence of Byzantine players, about whom we make no assumptions.

• A Learning Theory Approach to Non-Interactive Database Privacy. With Katrina Ligett and Aaron Roth. STOC 2008. Journal version: JACM, Volume 60, Issue 2, April 2013. [unofficial local copy]
  We demonstrate that, ignoring computational constraints, it is possible to release databases preserving differential privacy that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We also present an efficient algorithm for "large margin halfspace" queries. In addition, inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than differential privacy.

• Veritas: Combining expert opinions without labeled data.. With Sharath Cholleti (lead author), Sally Goldman, David Politte, and Steven Don. International Journal on Artificial Intelligence Tools, 2009: 633-651. (originally appeared in ICTAI, 2008).
  Looks at a boosting-based method for combining expert opinions when only unlabeled data is present, motivated by the problem of segmenting lung nodules in CT scans.

• Limits of Learning-based Signature Generation with Adversaries. With Shobha Venkataraman (lead author) and Dawn Song. Network and Distributed Systems Security Symposium (NDSS) 2008.
  We give limits on the accuracy of pattern-extraction algorithms for signature generation in an adversarial setting, by adapting and extending lower bounds for online learning in the mistake-bound model, when there are limits on the number of allowed mistakes of different types.

2007

• Mechanism Design, Machine Learning, and Pricing Problems. With Nina Balcan. SIGecom Exchanges 2007, special issue on Combinatorial Auctions.
  Short survey article on machine learning techniques for mechanism design.

• A Theory of Loss-Leaders: Making Money by Pricing Below Cost. With Nina Balcan, T-H. Hubert Chan and MohammadTaghi Hajiaghayi. WINE 2007.

• Separating Populations with Wide Data: a Spectral Analysis. With Amin Coja-Oghlan, Alan Frieze, and Shuheng Zhou. 18th International Symposium on Algorithms and Computation (ISAAC 2007). LNCS 4835, pp. 439-451.
  We consider the problem of partitioning a small data sample drawn from a mixture of k product distributions. We are interested in the case that individual features are of low average quality gamma, and we want to use as few of them as possible to correctly partition the sample. We analyze a spectral technique that is able to approximately optimize the total data size---the product of number of data points n and the number of features K---needed to correctly perform this partitioning as a function of 1/gamma for K>n. Our goal is motivated by an application in clustering individuals according to their population of origin using markers, when the divergence between any two of the populations is small.

• Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. With David Abraham and Tuomas Sandholm. ACM-EC 2007.
  Shows how MIP techniques can be used to get a more scalable and robust algorithm for solving optimization problems involved in clearing paired-donation kidney exchanges. Algorithm is currently in use by the Alliance for Paired Donation.

• Learning, Regret Minimization, and Equilibria [ps]. With Yishay Mansour. Book chapter in Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani, eds. [Slides for related talk]
  Book chapter describing connections between online learning and game theory. Includes description of algorithms for combining expert advice (minimizing external regret), algorithms for the stronger goal of minimizing internal regret, algorithms for the limited-feedback (multi-arm bandit) setting, and connections between these and minimax optimality (for zero-sum games) and correlated equilibria (for general-sum games). Also discusses how such algorithms will approach Nash equilibrium in non-atomic routing games.

• FiG: Automatic Fingerprint Generation. With Juan Caballero, Shobha Venkataraman, Pongsin Poosankam, Min Gyung Kang, and Dawn Song. In NDSS 2007.

• Open Problems in Efficient Semi-Supervised PAC Learning. With Nina Balcan. COLT'07 Open Problems List.
  Open problems about computationally-efficient semi-supervised learning that I would love to see solved (small monetary rewards offered).

2006

• On a Theory of Learning with Similarity Functions. With Nina Balcan. International Conference on Machine Learning (ICML), pp. 73-80, 2006. Journal version combines this conference paper with subsequent paper of Nati Srebro from COLT 2007: Machine Learning Journal 72(1-2):89-112, August, 2008. DOI 10.1007/s10994-008-5059-5. [NIPS'05 workshop talk] [Cornell'07 colloquium talk (broader)]
  Kernel functions have become an extremely popular tool in machine learning. They have an attractive theory that describes a kernel function as being good for a given learning problem if data is separable by a large margin in a (possibly very high-dimensional) implicit space defined by the kernel. This theory, however, has a bit of a disconnect with the intuition of a good kernel as a good similarity function. In this work we develop an alternative theory of learning with similarity functions more generally (i.e., sufficient conditions for a similarity function to allow one to learn well) that does not require reference to implicit spaces, and does not require the function to be positive semi-definite. Our results also generalize the standard theory in the sense that any good kernel function under the usual definition can be shown to also be a good similarity function under our definition (though with some loss in the parameters). In this way, we provide the first steps towards a theory of kernels that describes the effectiveness of a given kernel function in terms of natural similarity-based properties.

• Routing without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games. With Eyal Even-Dar and Katrina Ligett. PODC, pp. 45-52, 2006. [Slides for related talk]
  A number of no-regret algorithms have been developed in the game-theory and online learning literature. This paper considers the question: if each player in a routing game uses a no-regret strategy to choose their route on day t+1 based on their experience on days 1,...,t, what can we say about the overall behavior of the system? The main result of this paper is that in the Roughgarden-Tardos setting of multicommodity flow and infinitesimal agents, if each player uses a no-regret strategy then a 1-epsilon fraction of the daily flows will be epsilon-Nash (almost all users having only a small incentive to deviate) where epsilon approaches 0 at a rate that depends polynomially on the players' regret bounds and the maximum slope of any latency function.

• Approximation Algorithms and Online Mechanisms for Item Pricing. With Nina Balcan. Theory of Computing, 3/9:179-195, 2007. Originally appeared in ACM Conference on Electronic Commerce, pp. 29-35, 2006. [Slides for talk given at Spencer06-60]
  Presents approximation and online algorithms for a number of problems of pricing items so as to maximize a seller's revenue in an unlimited supply setting. Our main result is an O(k)-approximation for pricing items to single-minded bidders who each want at most k items. For the case k=2 (where we get a 4-approximation) this can be viewed as the following graph vertex pricing problem: given a graph G with valuations v_e on the edges, find prices p_i for the vertices to maximize sum_{e=(i,j): v_e >= p_i+p_j} p_i + p_j. We also show how these algorithms can be applied to the online setting, in which customers arrive over time and must be presented with prices that depend only on information gained from customers seen in the past.

• A Random-Surfer Web-Graph Model With Hubert Chan and Mugizi Rwebangira. ANALCO '06.
  This paper gives theoretical and experimental results on a random-surfer model for construction of a random graph. In this model, a new node connects to the existing graph by choosing a start node at random and then performing a short random walk, flipping a coin at each node visited to decide whether or not to stop and connect there. Our understanding of this model is still quite preliminary, though. Many open questions.

• Random Projection, Margins, Kernels, and Feature-Selection [ps]. LNCS 3940, pp. 52-68, 2006. Survey article based on an invited talk given at the 2005 PASCAL Workshop on Subspace, Latent Structure and Feature selection techniques.
  Random projection is a simple technique that has had a number of applications in algorithm design. In the context of machine learning, it can provide insight into questions such as ``why is a learning problem easier if data is separable by a large margin?'' and ``in what sense is choosing a kernel much like choosing a set of features?'' This article is intended to provide an introduction to random projection and to survey some simple learning algorithms and other applications to learning based on it. Portions of this article are based on work in [BB05,BBV04] joint with Nina Balcan and Santosh Vempala.

2005

• Reducing Mechanism Design to Algorithm Design via Machine Learning [short version, long version]. With Nina Balcan, Jason Hartline, and Yishay Mansour. JCSS 74:1245-1270, 2008 (JCSS special issue on Learning Theory). Originally appeared as "Mechanism Design via Machine Learning", FOCS 2005. [slides]
  Examines how sample-complexity arguments in machine learning can be used to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide class of revenue-maximizing pricing problems.

• From External to Internal Regret [local ps] [local pdf]. With Yishay Mansour. JMLR 8(Jun):1307--1324, 2007. Originally appeared in COLT 2005.
  Gives a generic method for converting external-regret algorithms to internal-regret algorithms, along with a specific algorithm for the bandit setting. Also gives a new simple method for a generalized "sleeping experts" setting. If you are interested in this paper you should definitely also check out Stoltz and Lugosi, "Internal Regret in On-Line Portfolio Selection", MLJ 59 (1/2), 2005. Their paper gives a different conversion procedure and has a number of other results. See also Gilles Stoltz's PhD thesis.

• A Discriminative Model for Semi-Supervised Learning. With Nina Balcan. JACM Vol 57, Issue 3, 2010. (Original COLT '05 paper titled "A PAC-style Model for Learning from Labeled and Unlabeled Data")
  This paper gives an extension to the PAC model that allows one to discuss ways of using unlabeled data to help with learning. The basic idea is that rather than "learning a class C", one instead talks of "learning a class C under compatibility notion χ", where χ(h,D) tells how a-priori compatible a proposed hypothesis h is with respect to a given distribution D. E.g., if you believe there should be a large-margin separator then your χ would give a low score to h's with large probability mass near the separating hyperplane. Or in co-training, χ would penalize hypotheses (h_1,h_2) such that Pr_x(h_1(x) ≠ h_2(x)) is large. If χ is "legal" (in a sense defined in the paper) then we can use this model to give sample-complexity bounds for both labeled and unlabeled data, and talk about conditions under which unlabeled data can significantly reduce the number of labeled examples needed. We also talk about well-justified ways of performing regularization in this setting and give a number of algorithmic results as well.

• Practical Privacy: The SuLQ Framework. With Cynthia Dwork, Frank McSherry, and Kobbi Nissim. PODS 2005.

• New Streaming Algorithms for Fast Detection of Superspreaders. With Shobha Venkataraman, Dawn Song, and Phillip Gibbons. NDSS 2005.
  Experimental and theoretical work on streaming algorithms (one pass, logarithmic memory) for detecting sources that send to many distinct destinations. That is, given a sequence of (x,y) pairs, you want to identify those x's that have appeared paired with many different y's.

• Near-Optimal Online Auctions. With Jason Hartline. SODA 2005, pages 1156--1163.
  Uses an approach based on an online learning algorithm of Kalai to get improved bounds for the problem of adaptive pricing of a digital good. We consider both the online auction and posted price settings.

2004

• Co-Training and Expansion: Towards Bridging Theory and Practice. With Nina Balcan and Ke Yang. NIPS 2004.
  This paper looks at conditions needed for co-training to succeed in terms of expansion properties of the underlying distribution. Proves bounds for the case that we have base learning algorithms able to make only one-sided error (i.e., learn from positive data only). Expansion is a much weaker condition than those considered previously, such as independence given the label, and appears to be the "right" condition on the distribution needed in order for co-training to work well when the base algorithms have only 1-sided error.

• Kernels as Features: On Kernels, Margins, and Low-dimensional Mappings [local copy]. With Nina Balcan and Santosh Vempala. Machine Learning, 65:79-94, 2006, DOI: 10.1007/s10994-006-7550-1. Extended abstract in 15th International Conference on Algorithmic Learning Theory (ALT '04). Springer LNAI 3244, pp. 194-205, 2004. [talk ppt] Here is a related survey article.
  Kernel functions are typically viewed as implicit mappings to a high-dimensional space that allow one to "magically" get the power of that space without having to pay for it, if data is separable in that space by a large margin. In this paper we show that in the presence of a large margin, a kernel can instead be efficiently converted into a mapping to a low dimensional space. In particular, we give an efficient procedure that, given black-box access to the kernel and unlabeled data, generates a small number of features that approximately preserve both separability and margin.

• Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds. With Dawn Song and Shobha Venkataraman. 7th International Symposium on Recent Advances in Intrusion Detection (RAID '04). Springer LNCS 3224, pp. 258-277, 2004.
  Use analysis of random walks to detect stepping-stone attacks under the "maximum delay bound" assumption. Gives learning-style bounds on number of packets that need to be observed to perform detection at a desired confidence level.

• Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. With Brendan McMahan. COLT '04, pages 109-123.
  We show how the recent, elegant result of Kalai and Vempala for online geometric optimization can be extended to the "bandit" version of the problem, in which one is only told of the cost incurred and not the full cost vector, even in the repeated-game setting (an adaptive adversary).

• Semi-Supervised Learning Using Randomized Mincuts. With John Lafferty, Mugizi Robert Rwebangira, and Rajashekar Reddy. ICML '04.
  We consider a randomized version of the mincut approach to learning from labeled and unlabeled data (see paper with Shuchi Chawla from 2001), and motivate it from both a sample-complexity perspective and from the goal of approximating Markov Random Field per-node probabilities.

• Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows. With Nikhil Bansal, Shuchi Chawla, and Adam Meyerson. STOC '04, pages 166-174.
  Consider a version of the metric TSP problem in which each node has a value and the goal is to collect as much value as possible, *but* each node also has a deadline and only counts if it is reached by its deadline. (More generally, nodes might have release dates too.) We give an O(log n) apx for deadlines, O(min[log^2 n, log D_max]) for time-windows, and a bicriteria approximation with the interesting property that it can achieve an O(k)-approximation while violating the deadlines by only a (1 + 1/2^k) factor. Big open question: can you get a constant factor apx?

2003

• Approximation Algorithms for Orienteering and Discounted-Reward TSP [local copy]. With Shuchi Chawla, David Karger, Adam Meyerson, Maria Minkoff, and Terran Lane. SIAM J. Computing 37(2):653-670, 2007. An earlier version appears in FOCS'03, pages 46-55. Also available as Tech report CMU-CS-03-121.
  We give a constant-factor approximation algorithm for the rooted Orienteering problem on general graphs, and for a new problem that we call the Discounted-Reward TSP. Given a weighted graph with rewards on nodes, and a start node s, the goal in the Orienteering Problem is to find a path that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor gamma, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by gamma^t. This is similar to the objective in MDPs except we only receive a reward the first time a node is visited.

• Scheduling for Flow-Time with Admission Control. With Nikhil Bansal, Shuchi Chawla, and Kedar Dhamdhere. ESA '03, pages 43-54.
  Considers the problem of job scheduling to minimize flow time, when the server is allowed to reject jobs at some penalty. This can be thought of the problem of managing your to-do list, when your cost function is the total amount of time that jobs are sitting on your stack plus a cost for each job that you say "no" to. E.g., if you initially agree to a task (like refereeing a paper) and then six months later you realize you cannot do it and say no, you pay both for the "no" and for the six months it has been sitting on your desk. We give 2-competitive online algorithms for the case of unweighted flow time and uniform costs, and extend some of our results to the case of weighted flow time and machines with varying speeds. We also give a resource augmentation result for the case of arbitrary penalties and present a number of lower bounds.

• Preference Elicitation and Query Learning. With Jeffrey Jackson, Tuomas Sandholm, and Martin Zinkevich. Journal of Machine Learning Research 5:649--667, 2004 (special issue on Learning Theory). Extended abstract appears in COLT '03.
  Explores the connection between "preference elicitation", a problem that arises in combinatorial auctions, and the problem of learning via queries. Preference elicitation can be thought of as a kind of learning problem with multiple target concepts, but where the goal is not to identify the concepts so much as it is to produce an "optimal example".

• PAC-MDL Bounds. With John Langford. COLT '03.
  Attempts to unify a number of bounds (including VC-dimension and PAC-Bayes) in a single MDL framework. In this setting, Alice has a set of labeled examples, Bob has the same examples but without labels, and Alice's job is to communicate the labels to Bob using only a small number of bits. The standard Occam's razor results say that if Alice can do this by sending a hypothesis (a function h(x) over single examples that Bob would then run m times) then she can be confident in the predictive ability of that hypothesis. But what about other methods of communicating labels? Extending Occam's razor to generic communication schemes requires a bit of "definition design" but can then encompass the more powerful VC-dimension and PAC-Bayes bounds.

• Planning in the Presence of Cost Functions Controlled by an Adversary. With Brendan McMahan and Geoff Gordon. ICML '03.
  Looks at fast algorithms for finding "minimax optimal plans" in a certain adversarial MDP setting. Includes some experimental results on a robot navigation domain.

• Open problem: Learning a function of r relevant variables. COLT 2003 open problems session.

• On Statistical Query Sampling and NMR Quantum Computing. With Ke Yang. 18th IEEE Conference on Computational Complexity (CCC '03).
  We introduce a problem called Statistical Query Sampling that models an issue that arises in NMR quantum computing. We give a number of lower bounds for this problem, and relate it to the (more standard) problem of Statistical Query Learning.

• On Polynomial-Time Preference Elicitation with Value Queries. With Martin Zinkevich and Tuomas Sandholm. ACM Conference on Electronic Commerce, 2003.
  We consider the question of whether interesting classes of preferences can be elicited in polynomial time using value queries. Building on known results on Membership Query learning, we show that read-once formulas over a set of gates motivated from a shopping-agent scenario can be elicited in polynomial time, as well as a class of preferences we call "toolbox DNF". We also give a number of (positive and negative) results for the subsequent allocation problem. For instance, we show how network flow can be used to do allocation efficiently with two bidders with toolbox-DNF preferences.

• Combining Online Algorithms for Rejection and Acceptance. With Yossi Azar and Yishay Mansour. SPAA '03, pages 159-163. Combined with subsequent paper by David Bunde and Yishay Mansour in journal version appearing in Theory of Computing, 1:105-117, 2005.
  The call-control problem has the interesting property that in some versions one can design online algorithms with good competitive ratio in terms of fraction of calls accepted, in some versions one can design algorithms with good C.R. in terms of the fraction rejected, and in some versions one can do both, but in the last case, the algorithms tend to be very different. We consider the problem: given an algorithm A with competitive ratio c_A for fraction accepted, and an algorithm R with ratio c_R in terms of fraction rejected, can we combine them into a single algorithm that is good under both measures? We do this achieving ratio O(c_A^2) [improved in journal version to O(c_A)] for acceptance and O(c_A c_R) for rejection.

• Online Oblivious Routing. With Nikhil Bansal, Shuchi Chawla, and Adam Meyerson. 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA '03), pages 44-49.
  Uses online learning tools to develop a polynomial-time algorithm for performing nearly as well as the best fixed routing in hindsight, in a repeated "oblivious routing game". In this setting the algorithm is allowed to choose a new routing each night, but is still oblivious to the demands that will occur the next day. Our result is a strengthening of a recent result of Azar et al., who gave a polynomial time algorithm to find the minimax optimal strategy in this game. It is a strengthening in that it achieves a competitive ratio arbitrarily to close to that of Azar et al., while at the same time performing nearly as well as the optimal static routing for the sequence of demands that actually occurred.

• Online Learning in Online Auctions. With Vijay Kumar, Atri Rudra, and Felix Wu. SODA '03, pages 202-204. The link points to a somewhat longer version.
  Describes how the Weighted-Majority algorithm can be used to get improved bounds for online auctions of digital goods, as well as for the posted price setting (that corresponds to a "bandit" version of the problem: the auctioneer has to pick a price first, and then only gets the single bit back indicating whether or not the buyer purchased). Also gives some lower bounds.

2002

• Correlation Clustering [local copy]. With Nikhil Bansal and Shuchi Chawla. Machine Learning 56(1-3):89-113, 2004 (Special Issue on Theoretical Advances in Data Clustering). An earlier version appears in FOCS '02, pages 238--247.
  Considers a clustering problem motivated by machine-learning style applications, from the perspective of approximation algorithms. We give a constant-factor approximation under a cost measure and a PTAS under a benefit measure. A nice feature of this clustering formulation is that one does not need to specify the desired number of clusters in advance.

• Smoothed Analysis of the Perceptron Algorithm for Linear Programming. With John Dunagan. SODA '02, pages 905--914.
  This paper shows that the simple Perceptron algorithm has good behavior for linear programming (polynomial-time whp) in the smoothed analysis model of Spielman-Teng. Spielman-Teng had shown this for a specific version of the Simplex algorithm. It is interesting that the bounds for the Perceptron algorithm are better than those known for Simplex in this model, as a function of most of the parameters. The one exception is the "epsilon" term (e.g., if you are interested in a bound that holds on 99% of the instances, then the Perceptron bounds are better, but Perceptron has an epsilon chance of taking time Omega(1/epsilon^2), so does badly in expectation). However, I think the real difference is that Perceptron solves only the feasibility problem, and not the optimization problem. Normally, these are equivalent by simple reduction, but it is not clear that reduction makes sense in the smoothed-analysis model, because it involves a binary-search that will surely create ill-conditioned instances. So, it could well be that feasibility is a strictly easier problem than optimization in this model.

• Online Algorithms for Market Clearing. With Tuomas Sandholm and Martin Zinkevich. JACM 53(5): 845-879, 2006. Extended abstract in SODA '02, pages 971-980.
  We consider the problem of market clearing in a double auction (exchange) where buyers and sellers arrive and depart online. We give algorithms with optimal competitive ratios for several natural objectives and also give a few results having to do with learning and incentive-compatibility.

• Static Optimality and Dynamic Search-Optimality in Lists and Trees. With Shuchi Chawla and Adam Kalai. Algorithmica 36(3):249-260, 2003 (special issue on online algorithms). Originally appeared in Proceedings of the 13th Annual Symposium on Discrete Algorithms (SODA), pages 1--8, 2002.
  This paper uses notions from online learning to attack several problems in adaptive data-structures.

2001

• Admission Control to Minimize Rejections. With Adam Kalai and Jon Kleinberg. Internet Mathematics 1(2):165--176, 2004. Originally appeared in Proceedings of WADS'01 (LNCS 2125, pp.155-164, 2001).
  Studies admission control from the perspective of approximately minimizing rejections, getting a factor of 2 for a collection of natural problems. This can make more sense than the usual perspective (apx maximizing the number of acceptances) if we are not highly overloaded (e.g., if optimal can accept 99% of requests).

• Learning from Labeled and Unlabeled Data using Graph Mincuts. With Shuchi Chawla. ICML '01, pp. 19-26.
  A natural extension of nearest-neighbor algorithms, when you add in unlabeled data, leads to viewing learning as a mincut problem. This paper explores this connection and gives some empirical results.

2000

• FeatureBoost: A Meta Learning Algorithm that Improves Model Robustness. With Joseph O'Sullivan, John Langford, and Rich Caruana. ICML '00, pp. 703--710.
  How can you make learning algorithms less "lazy", so that they search for multiple "really-different" prediction rules, in case we are later faced with data in which features are corrupted or obscured?

• Noise-tolerant Learning, the Parity problem, and the Statistical Query model. With Adam Kalai and Hal Wasserman. JACM 50(4): 506-519 (2003). Extended abstract in STOC'00, pp. 435--440.
  This paper gives a slightly sub-exponential algorithm for learning parity in the presence of random noise. Scaling the problem down gives the first known example of a problem that can be learned in polynomial time from noisy data but cannot be learned in polynomial time in the Statistical Query model of Kearns.

1999

• Finely-competitive Paging. With Carl Burch and Adam Kalai. FOCS'99, pp. 450--458.
  Using ideas from online learning, we give a paging algorithm with especially good behavior under a fine-grained notion of competitive ratio. For instance, the algorithm gives near-optimal performance when the request stream can be partitioned unto a small number of working sets. Unfortunately, the algorithm itself is not computationally efficient.

• Probabilistic Planning in the Graphplan Framework. With John Langford. 5th European Conference on Planning (ECP'99). See the PGP web page.
  Approaches probabilistic planning from the Graphplan perspective. The result ends up looking at lot like a game-tree search, but using the planning graph to quickly prune states that can be guaranteed not to reach the goals in time.

• Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation. With Adam Kalai and John Langford. Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT '99), pp. 203--208.
  We show that for k>2, k-fold CV is at least slightly better than simply using a hold-out set of 1/k of the examples, in terms of the quality of the error estimate. We also analyze a "progressive validation" approach (similar to a method used by Littlestone for converting online algorithms to batch) that we show is in many ways as good as the hold-out, while using on average half as many examples for testing.

• Microchoice Bounds and Self Bounding Learning Algorithms. With John Langford. Machine Learning 51(2): 165-179 (2003). Originally appeared in Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT '99), pp. 209--214.
  Gives adaptive sample-complexity bounds for learning algorithms that work by making a sequence of small choices. These allow for a computationally-efficient version of Freund's Query-Trees.

• On-line Algorithms for Combining Language Models. With Stan Chen, Adam Kalai, and Roni Rosenfeld. In Proceedings of the International Conference on Accoustics, Speech, and Signal Processing (ICASSP '99).  [postscript] [gzipped postscript]
  Uses online portfolio-selection algorithms in the context of combining language models, with experimental comparisons.

1998

• On Learning Monotone Boolean Functions. With Carl Burch and John Langford. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS '98).
  For learning an arbitrary monotone Boolean function over the uniform distribution, we give a simple algorithm that achieves error rate at most 1/2 - Omega(1/sqrt(n)), and show that no algorithm can do better than 1/2 - omega(log(n)/sqrt(n)) from a polynomial size sample. These improve over the previous best upper and lower bounds.

• Combining Labeled and Unlabeled Data with Co-Training [pdf]. With Tom Mitchell. Proceedings of the 11th Annual Conference on Computational Learning Theory, pages 92--100, 1998. (The document linked to here fixes some minor bugs in the COLT version).
  Introduces and studies Co-Training, a natural approach to using unlabeled data when we have two different sources of information about each example. The idea is to train two classifiers, one using each type of information. We can then search over the unlabeled data to find examples where one classifier is confident and the other is not, and then use the label given by the confident classifier as training data for the other. In the process of analyzing this setting, we also give new results (see lemma 1) on PAC learning with noise when the positive and negative noise rates are different.

• On a Theory of Computing Symposia. With Prabhakar Raghavan. International Conference on Fun with Algorithms (FUN '98). Also appeared in SIGACT News, September 1998.
  How can you get the advantages of parallel sessions while still allowing attendees to see all the talks they wanted? The answer is to have four sessions, with each talk given twice! This paper explores a number of properties of this approach, along with connections to flows and expanders.

• Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems. With Goran Konjevod, R. Ravi, and Santosh Vempala. Theoretical Computer Science, 235(1):25--42, 2000. (Special issue in honor of Manuel Blum's 60th Birthday!) Extended abstract in Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC '98).

• A Note on Learning from Multiple-Instance Examples. With Adam Kalai. Machine Learning, 30:23--29, 1998.

1997

• Universal Portfolios With and Without Transaction Costs. With Adam Kalai. Machine Learning, 35: 193--205, 1999 (special issue for COLT '97). Originally appeared in Proceedings of the 10th Annual Conference on Computational Learning Theory, pages 309--313, July 1997.

• On-line Learning and the Metrical Task System Problem. With Carl Burch. Machine Learning, 39: 35--58, 2000. Originally appeared in Proceedings of the 10th Annual Conference on Computational Learning Theory (COLT '97), pages 45--53.

• A polylog(n)-competitive algorithm for metrical task systems. With Yair Bartal, Carl Burch, and Andrew Tomkins. Proceedings of the 29th Annual Symposium on the Theory of Computing (STOC '97), pages 711--719.

• An O~(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs. With David Karger. Information Processing Letters, 61(1):49--53, January 1997.

1996

• On-Line Algorithms in Machine Learning (a survey). This is a survey paper for a talk given at the Dagstuhl workshop on On-Line algorithms (June '96). Appears as Chapter 14 in "Online Algorithms: The State of the Art", LNCS # 1442, Fiat and Woeginger eds., 1998.

• A Polynomial-time Algorithm for Learning Noisy Linear Threshold Functions. With Alan Frieze, Ravi Kannan, and Santosh Vempala. Algorithmica, 22:35--52, 1998. An extended abstract appears in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS'96), pages 330--338.

• A Constant-factor Approximation Algorithm for the k-MST Problem. With R. Ravi and Santosh Vempala. JCSS, 58:101--108 (1999). An extended abstract appears in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC '96), pages 442--448.

• Randomized Robot Navigation Algorithms. With Piotr Berman, Amos Fiat, Howard Karloff, Adi Rosen, and Michael Saks. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 75--84, January 1996.

1995

• Fast Planning Through Planning Graph Analysis . With Merrick Furst. Artificial Intelligence 90:281--300, 1997. An extended abstract appears in Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), pages 1636--1642, August 1995. See also the Graphplan home page .

• Empirical support for Winnow and Weighted-Majority based algorithms: results on a calendar scheduling domain . Machine Learning 26:5--23, 1997. An earlier version is in Proceedings of the Twelfth International Conference on Machine Learning, pages 64--72, July 1995. Click here for more information and source code.

• Learning with Unreliable Boundary Queries . With Prasad Chalasani, Sally Goldman, and Donna Slonim. Journal of Computer and System Sciences,56(2):209-222, 1998. Originally appeared in Proceedings of the Eighth Annual Conference on Computational Learning Theory (COLT), pages 98---107, July 1995.

• New Approximation Guarantees for Minimum Weight k-Trees and Prize-Collecting Salesmen. With Baruch Awerbuch, Yossi Azar, and Santosh Vempala. SIAM J. Computing, 28(1):254--262, 1999. Originally published in Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 277--283, 1995. A tech report version appears as CMU-CS-94-173, August, 1994.

• A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane. With J.S.B. Mitchell, Prasad Chalasani, and Santosh Vempala. SIAM J. Computing 28(3): 771-781 (1998). This paper combines two conference papers: J.S.B. Mitchell, "Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem", SODA '96, pp. 402--408, and Blum, Chalasani, and Vempala, "A constant-factor approximation for the k-MST problem in the plane", STOC '95, pp. 294--302.

• Coloring Random and Semi-Random k-Colorable Graphs. With Joel Spencer. Journal of Algorithms 19:204--234, 1995. This paper extends the semi-random model results in "Some Tools for Approximate 3-Coloring", Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 554-562, October 1990.

1994

• Relevant Examples and Relevant Features: Thoughts from Computational Learning Theory . This is a survey paper presented at the 1994 AAAI Fall Symposium. Here is a longer article with a broader perspective, joint with Pat Langley, that appears in Artificial Intelligence, 97:245--272, 1997.

• On learning read-k-satisfy-j DNF. With Howard Aizenstein, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, and Dan Roth. SIAM J. Computing, 27(6):1515--1530, 1998. Originally published in Proceedings of the Seventh Annual Conference on Computational Learning Theory, pages 110--117, July 1994.

• The Minimum Latency Problem. With Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 163--171, 1994.

• Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis. With Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 253--262, 1994. [notes and clarifications]

• New Approximation Algorithms for Graph Coloring. JACM 41(3):470--516, May 1994. This paper combines the worst-case approximation results in "Some Tools for Approximate 3-Coloring", FOCS 1990 (pp 554-562), and those in "An O(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithms for k-Coloring)", STOC 1989 (pp 535-542). See 1995 paper with Joel Spencer for results on Semi-Random model.

1993

• Cryptographic Primitives Based on Hard Learning Problems. With Merrick Furst, Michael Kearns, and Richard Lipton. In Advances in Cryptology --- CRYPTO 93, Lecture Notes in Computer Science #773, pages 278-291, Springer-Verlag, 1994.

• Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution. With Ravi Kannan. Journal of Computer and System Sciences 54(2):371--380, 1997 (JCSS special issue for FOCS '93). Originally appeared in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 312--320, November 1993. Also published as Chapter 9 in Theoretical Advances in Neural Computation and Learning , Roychowdhury, Siu and Orlitsky, eds. Kluwer, 1994.

• An On-Line Algorithm for Improving Performance in Navigation. With Prasad Chalasani. SIAM J. Comput. 29(6): 1907-1938 (2000). Originally appeared in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 2--11, November 1993.

• On Learning Embedded Symmetric Concepts. With Prasad Chalasani and Jeffrey Jackson. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, pages 337--346, July 1993.

• Generalized Degree Sums and Hamiltonian Graphs. With Ronald Gould. ARS Combinatoria, 35:35--54, 1993.

1992

• A Decomposition Theorem and Bounds for Randomized Server Problems. With Howard Karloff, Yuval Rabani, and Michael Saks. SIAM J. Computing, 30(5): 1624--1661, 2000. Originally appeared un Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 197--207, October 1992.

• Learning Switching Concepts. With Prasad Chalasani. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 231--242, July 1992.

• Fast Learning of k-Term DNF Formulas with Queries. With Steven Rudich. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 382-389, May 1992.

• Rank-r Decision Trees are a Subclass of r-Decision Lists. Information Processing Letters, 42:183--185, 1992.

1991

• Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. With Lisa Hellerstein and Nick Littlestone. JCSS 50(1):32--40, February 1995. An earlier version appears in Proceedings of the Fourth Annual Workshop on Computational Learning Theory, pages 157-166, August 1991.

• Algorithms for Approximate Graph Coloring. Ph.D. thesis, MIT Laboratory for Computer Science MIT/LCS/TR-506, May 1991.

• Linear Approximation of Shortest Superstrings. [ps] With Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. JACM 41(4):630--647, 1994. An earlier version appears in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 328-336, May 1991.

• Navigating in Unfamiliar Geometric Terrain. [ps] With Prabhakar Raghavan and Baruch Schieber. Siam J. Comp 26(1):110-137, February 1997. An earlier version appears in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 494-504, May 1991.

1990

• Learning Boolean Functions in an Infinite Attribute Space. Machine Learning, 9(4):373--386, 1992. Also in Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 64-72, May 1990.

• Some Tools for Approximate 3-Coloring. Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 554-562, October 1990.

• Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain. [pdf] SIAM J. Computing, Vol 23, No. 5, 1994. Also in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 211-218, October 1990.

• Learning Functions of k Terms. With Mona Singh. In Proceedings of the Third Annual Workshop on Computational Learning Theory, pages 144-153, August 1990.

1989

• On the Computational Complexity of Training Simple Neural Networks. Master's thesis, MIT Laboratory for Computer Science, MIT/LCS/TR-445, May 1989.

• An O(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithms for k-Coloring). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 535-542, May 1989.

• Training a 3-Node Neural Network is NP-Complete. With Ron Rivest. Neural Networks, 5(1):117-127, 1992. Also in Advances in Neural Information Processing Systems 1 (proceedings of the 1988 NIPS conference), pp. 494-501, 1989.

Last updated: August 2010