Item Pricing for Revenue Maximization (2009)
Maria-florina Balcan, Avrim Blum, Yishay Mansour
We consider the problem of pricing n items to maximize revenue when faced with a series of unknown buyers with complex preferences, and show that a simple pricing scheme achieves surprisingly strong...
A Discriminative Framework for Clustering via Similarity Functions (2009)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Problems of clustering data from pairwise similarity information are ubiquitous in Computer Science. Theoretical treatments typically view the similarity information as ground-truth and then design...
Improved Equilibria via Public Service Advertising (2009)
Maria-florina Balcan, Avrim Blum, Yishay Mansour
Many natural games have both high and low cost Nash equilibria: their Price of Anarchy is high and yet their Price of Stability is low. In such cases, one could hope to move behavior from a high cost...
Improved Guarantees for Learning via Similarity Functions (2009)
Maria-florina Balcan, Avrim Blum, Nathan Srebro
We continue the investigation of natural conditions for a similarity function to allow learning, without requiring the similarity function to be a valid kernel, or referring to an implicit...
Clustering with Interactive Feedback (2009)
Maria-florina Balcan, Avrim Blum
Abstract. In this paper, 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...
Separating Populations with Wide Data: a Spectral Analysis (2009)
Avrim Blum, Amin Coja-oghlan, Alan Frieze, Shuheng Zhou
Abstract. In this paper, 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...
A Discriminative Model for Semi-Supervised Learning ∗ (2009)
Maria-florina Balcan, Avrim Blum
Supervised learning — that is, learning from labeled examples — is an area of Machine Learning that has reached substantial maturity. It has generated general-purpose and practically-successful...
Veritas: Combining Expert Opinions without Labeled Data (2009)
Sharath R. Cholleti, Sally A. Goldman, David G. Politte, Steven Don, Avrim Blum
We consider a variation of the problem of combining expert opinions for the situation in which there is no ground truth to use for training. Even though we don’t have labeled data, the goal of this...
Limits of Learning-based Signature Generation with Adversaries (2009)
Shobha Venkataraman, Avrim Blum, Dawn Song
Automatic signature generation is necessary because there may often be little time between the discovery of a vulnerability, and exploits developed to target the vulnerability. Much research effort...
Approximate Clustering without the Approximation (2009)
Maria-florina Balcan, Avrim Blum, Anupam Gupta
Approximation algorithms for clustering points in metric spaces is a flourishing area of research, with much research effort spent on getting a better understanding of the approximation guarantees...
of positive semi-definite kernels (Scholkopf & Smola, (2009)
Maria-florina Balcan, Avrim Blum
We continue to investigate natural conditions for a similarity function to allow learning, without thinking of the similarity function as a kernel, requiring it to be p.s.d, or referring to an...
Avrim Blum, Tom Mitchell, Saif Mohammad, Lecturer Rich Maclin, Human Annotation
� Learn classifier from annotated training data � Apply classifier on unseen test data � Larger the training set � More accurate is the classifier � Consider Word Sense Disambiguation �...
Improved equilibria via public service advertising (2009)
Balcan, Maria-Florina, Mansour, Yishay, Blum, Avrim
Many natural games have both high and low cost Nash equilibria: their Price of Anarchy is high and yet their Price of Stability is low. In such cases, one could hope to move behavior from a high cost...
Maria-florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing...
ABSTRACT Black box anomaly detection: is it utopian? (2008)
Shobha Venkataraman, Juan Caballero, Dawn Song, Avrim Blum, Jennifer Yates
Automatic identification of anomalies on network data is a problem of fundamental interest to ISPs to diagnose incipient problems in their networks. ISPs gather diverse data sources from the network...
Algorithms, Security, Theory (2008)
We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class...
Shobha Venkataraman, Avrim Blum
Automatic signature generation is necessary because there may often be little time between the discovery of a vulnerability, and exploits developed to target the vulnerability. Much research effort...
Separating Populations with Wide Data: a Spectral Analysis (2008)
Avrim Blum, Amin Coja-oghlan, Alan Frieze, Shuheng Zhou
Abstract. In this paper, 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...
Separating Populations with Wide Data: a Spectral Analysis (2008)
Avrim Blum, Amin Coja-oghlan, Alan Frieze, Shuheng Zhou
Abstract. In this paper, 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...
(who-eats-whom) Web & citations Internet Sexual network Yeast protein (2008)
Jure Leskovec, Christos Faloutsos, Avrim Blum, Jon Kleinberg, John Lafferty
interactions
Maria-florina Balcan, Avrim Blum
Consider a seller with multiple digital goods or services for sale, such as movies, software, or network services, over which buyers may have complicated preferences. In order to sell these items...
Avrim Blum, Atri Rudra, Felix Wu
We consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this paper, we demonstrate that results from online...
Maria-florina Balcan, Avrim Blum, Ke Yang
Co-training is a method for combining labeled and unlabeled data when examples can be thought of as containing two distinct sets of features. It has had a number of practical successes, yet previous...
Dissertation: New Theoretical Frameworks for Machine Learning. (2008)
Maiden Name Popa, Maria-florina Balcan, Avrim Blum, Manuel Blum, Yishay Mansour, Tom Mitchell, ...
Dependable Computing and Fault Tolerance (TSF) Team, CNRS, Toulouse, France.
ABSTRACT Black box anomaly detection: is it utopian? (2008)
Shobha Venkataraman, Juan Caballero, Dawn Song, Avrim Blum, Jennifer Yates
Automatic identification of anomalies on network data is a problem of fundamental interest to ISPs to diagnose incipient problems in their networks. ISPs gather diverse data sources from the network...
Combining online algorithms for acceptance and rejection (2008)
Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour, C Yossi Azar, Avrim Blum, ...
Abstract: Resource allocation and admission control are critical tasks in a communication network that often must be performed online. Algorithms for these types of problems have been considered both...
Ravinda K. Ahuja, James B. Orlin, Stefano Pallottino, Maria G, Nikhil Bansal, Avrim Blum, ...
Scutella. Dynamic shortest paths minimizing travel times and costs. Networks,
Maria-florina Balcan, Avrim Blum, Ke Yang
Co-training is a method for combining labeled and unlabeled data when examples can be thought of as containing two distinct sets of features. It has had a number of practical successes, yet previous...
Dissertation: New Theoretical Frameworks for Machine Learning. (2008)
Maiden Name Popa, Maria-florina Balcan, Avrim Blum, Manuel Blum, Yishay Mansour, Tom Mitchell, ...
Dependable Computing and Fault Tolerance (TSF) Team, CNRS, Toulouse, France.
Combining online algorithms for acceptance and rejection (2008)
Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour, C Yossi Azar, Avrim Blum, ...
Abstract: Resource allocation and admission control are critical tasks in a communication network that often must be performed online. Algorithms for these types of problems have been considered both...
Abstract Cryptographic Primitives Based on Hard Learning Problems (2008)
Modern cryptography has had considerable impact on the development of computational learning theory. Tools from cryptography have been used in proving nearly all of the strong negative results for...
Maria-florina Balcan, Avrim Blum
Consider a seller with multiple digital goods or services for sale, such as movies, software, or network services, over which buyers may have complicated preferences. In order to sell these items...
We present new results, both positive and negative, on the well-studied problem of learning disjunctive normal form (DNF) expressions. We rst prove that an algorithm due to Kushilevitz and Mansour...
Combining online algorithms for acceptance and rejection (2008)
Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour, C Yossi Azar, Avrim Blum, ...
Abstract: Resource allocation and admission control are critical tasks in a communication network that often must be performed online. Algorithms for these types of problems have been considered both...
Open Problems in Efficient Semi-Supervised PAC Learning (2008)
Avrim Blum, Maria-florina Balcan
The standard PAC model focuses on learning a class of functions from labeled examples, where the two critical resources are the number of examples needed
21 An Augmented PAC Model for SemiSupervised Learning (2008)
Maria-florina Balcan, Avrim Blum
The standard PAC-learning model has proven to be a useful theoretical framework for thinking about the problem of supervised learning. However, it does not tend to capture the assumptions underlying...
Maria-florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing...
Mechanism Design, Machine Learning, and Pricing Problems (2008)
Maria-florina Balcan, Avrim Blum
Consider a seller with multiple digital goods or services for sale, such as movies, software, or network services, over which buyers may have complicated preferences. In order to sell these items...
On Statistical Query Sampling and NMR Quantum Computing Abstract (2008)
which the goal of an algorithm is to produce an element in a hidden set ¡£¢¥¤§¦©¨����� � with reasonable probability. The algorithm gains information about ¡ through oracle...
Avrim Blum, Mohammadtaghi Hajiaghayi, Aaron Roth, Katrina Ligett
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that selfinterested players will play according to a Nash equilibrium (which may even be...
On a Theory of Computing Symposia (2007)
Avrim Blum, Prabhakar Raghavan
We consider the problem of scheduling a conference to achieve the benefits in timecompression of parallel sessions, but without the associated high degree of conflict between talks. We describe a...
Learning an Intersection of Halfspaces over a Uniform Distribution (2007)
We present a polynomial-time algorithm to learn an intersection of a constant number of halfspaces in n dimensions, over the uniform distribution on an n- dimensional ball. The algorithm we present...
Robust Learning with FeatureBoost (2007)
Joseph O'Sullivan, John Langford, Rich Caruana, Avrim Blum
PAC learning typically assumes that the training and test sets are drawn from the same distributions. This assumption often is violated in practice. How can machine learning algorithms be biased to...
Improved Approximation Guarantees for Minimum-Weight (2007)
Trees And, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, ...
We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by...
Abstract. We point out that a number of standard sample complexity bounds (VC-dimension, PAC-Bayes, and others) are all related to the number of bits required to communicate the labels given the...
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Abstract. Kernel functions are typically viewed as providing an implicit mapping of points into a high-dimensional space, with the ability to gain much of the power of that space without incurring a...
† Strategic Planning and Optimization Team, Amazon.com, (2007)
Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu
We consider here the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this note, we demonstrate that results from online...
Avrim Blum, Shuchi Chawla, David R. Karger, Adam Meyerson, Maria Minkoff
In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot...
On Statistical Query Sampling and NMR Quantum Computing (2007)
We introduce a "Statistical Query Sampling " model, in which the goal of an algorithm is to produce an element in a hidden set S ` f0; 1g n with reasonable probability. The...
n), improving on the previous best bound of (2007)
Avrim Blum, Carl Burch, John Langford
We consider the problem of learning monotone Boolean functions over f0; 1g n under the uniform distribution. Specifically, given a polynomial number of uniform random samples for an unknown monotone...
Preference Elicitation and Allocation with Read-Once Preferences (2007)
Martin Zinkevich, Avrim Blum, Tuomas Sandholm
Elicitation of real-valued preferences is a key capability in many allocation problems, especially in electronic commerce. When multiple items are to be allocated, preference elicitation is difficult...
We consider the following scenario. A point robot is placed at some start location ¡ in a 2dimensional scene containing oriented rectangular obstacles. The robot must repeatedly travel back and...
Avrim Blum, Ravi Kannan, Santosh Vempala
In this paper we consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a \perceptron"). Methods for solving this problem generally fall into...
Please send all correspondence to: (2007)
Joel Spencer, Avrim Blum, Avrim Blum
The problem of coloring a graph with the minimum number of colors is well known to be NPhard, even restricted to k-colorable graphs for constant k 3. On the other hand, it is known that random...
Avrim Blum, Adam Kalai, Jon Kleinberg
Abstract. Admission control (call control) is a well-studied online problem. We are given a fixed graph with edge capacities, and must process a sequence of calls that arrive over time, accepting...
On Statistical Query Sampling and NMR Quantum Computing (2007)
We introduce a "Statistical Query Sampling" model, in which the goal of an algorithm is to produce an element in a hidden set S f0; 1g with reasonable probability.
H. Brendan Mcmahan, Avrim Blum
Abstract. We give an algorithm for the bandit version of a very general online optimization problem considered by Kalai and Vempala [1], for the case of an adaptive adversary. In this problem we are...
Avrim Blum, Jeffrey Jackson, Tuomas Sandholm, Martin Zinkevich
Abstract. In this paper we initiate an exploration of relationships between "preference elicitation", a learning-style problem that arises in combinatorial auctions, and the problem...
1. You (probabilistically) select an expert. 2. Each expert experiences a \loss " between 0 and `max. (You can see what they all are) 3. You experience the loss of your expert. Repeat.!...
Avrim Blum, Howard Karloff, Michael Saks
We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...
Separating populations with wide data: A spectral analysis (2007)
Blum, Avrim, Coja-Oghlan, Amin, Frieze, Alan, Zhou, Shuheng
In this paper, 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...
Approximation Algorithms for Bounded Dimensional Metric Spaces (2007)
The study of finite metrics is an important area of research, because of its wide applications to many different problems. The input of many problems (for instance clustering, near-neighbor queries...
A Learning Theoretic Framework for Clustering with Similarity Functions (2007)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Problems of clustering data from pairwise similarity information are ubiquitous in Computer Science. Theoretical treatments typically view the similarity information as ground-truth and then design...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Katrina Ligett, Aaron Roth
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Katrina Ligett, Aaron Roth
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be...
A Learning Theoretic Framework for Clustering with Similarity Functions (2007)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Problems of clustering data from pairwise similarity information are ubiquitous in Computer Science. Theoretical treatments typically view the similarity information as ground-truth and then design...
Item Pricing for Revenue Maximization (2007)
Maria-florina Balcan, Avrim Blum, Yishay Mansour
We consider the problem of pricing items to maximize revenue when faced with buyers with complex preferences, and show that a simple and natural pricing scheme achieves surprisingly strong...
HAJIAGHAYI: A theory of loss-leaders: Making money by pricing below cost (2007)
Maria-florina Balcan, Avrim Blum, Mohammadtaghi Hajiaghayi
Abstract. We consider the problem of assigning prices to goods of fixed marginal cost in order to maximize revenue in the presence of singleminded customers. We focus in particular on the question of...
Single price mechanisms for revenue maximization in unlimited supply combinatorial auctions (2007)
Maria-florina Balcan, Avrim Blum, Yishay Mansour
In this paper we generalize a result of Guruswami et. al [7], showing that in unlimited-supply combinatorial auctions, a surprisingly simple mechanism that offers the same price for each item...
HAJIAGHAYI: A theory of loss-leaders: Making money by pricing below cost (2007)
Maria-florina Balcan, Avrim Blum, T-h. Hubert, Chan Mohammadtaghi Hajiaghayi
We consider the problem of assigning prices to goods of fixed marginal cost in order to maximize revenue in the presence of single-minded customers. We focus in particular on the question of how...
Using Online Algorithms to Solve NP-Hard Problems More Efficiently in Practice (2007)
Matthew Streeter, Avrim Blum, Carla P. Gomes
as representing the official policies of the U.S. Government.
A theory of similarity functions for clustering (2007)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Problems of clustering data from pairwise similarity information are ubiquitous in Computer Science. Theoretical treatments typically view the similarity information as ground-truth and then design...
FiG: Automatic Fingerprint Generation (2007)
Juan Caballero, Min Gyung Kang, Shobha Venkataraman, Dawn Song, Pongsin Poosankam, Avrim Blum
Fingerprinting is a widely used technique among the networking and security communities for identifying different implementations of the same piece of networking software running on a remote host. A...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Aaron Roth, Katrina Ligett
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that selfinterested players will play according to a Nash equilibrium (which may even be...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize- Collecting Salesmen (2006)
Awerbuch, Baruch, Azar, Yossi, Blum, Avrim
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
On a theory of learning with similarity functions (2006)
Maria-florina Balcan, Avrim Blum, Nathan Srebro
Abstract. Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly...
Computational Aspects of Preference Aggregation (2006)
Vincent Conitzer, Avrim Blum, Tom Mitchell
IIS-0427858, IIS-0234695, and IIS-0121678, as well as a Sloan Fellowship awarded to Tuomas Sandholm, and an IBM Ph.D. Fellowship. The views and conclusions contained in this document are those of the...
Avrim Blum, Eyal Even-dar, Katrina Ligett
Abstract There has been substantial work developing simple, efficient no-regret algorithms for a wideclass of repeated decision-making problems including online routing. These are adaptive strategies...
Routing Without Regret: On Convergence To Nash . . . (2006)
Avrim Blum, Eyal Even-Dar, Katrina Ligett
There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an...
Approximation Algorithms and Online Mechanisms for (2006)
Maria-florina Balcan, Avrim Blum
We present approximation and online algorithms for a number of problems of pricing items for sale so as to maximize seller's revenue in an unlimited supply setting. Our first result is an...
On a theory of learning with similarity functions (2006)
Maria-florina Balcan, Avrim Blum
Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly very high...
On a theory of learning with similarity functions (2006)
Maria-florina Balcan, Avrim Blum
Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly very high...
Approximation Algorithms and Online Mechanisms for Item Pricing (2006)
Maria-florina Balcan, Avrim Blum
We present approximation and online algorithms for a number of problems of pricing items for sale so as to maximize seller’s revenue in an unlimited supply setting. Our first result is an...
Avrim Blum, Eyal Even-dar, Katrina Ligett
Abstract. There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive...
Approximation Algorithms and Online Mechanisms for Item Pricing (2006)
Maria-florina Balcan, Avrim Blum
Abstract: We present approximation and online algorithms for problems of pricing a collection of items for sale so as to maximize the seller’s revenue in an unlimited supply setting. Our first...
A random-surfer web-graph model (2006)
Avrim Blum, T-h. Hubert, Chan Mugizi, Robert Rwebangira
In this paper we provide 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...
On a theory of learning with similarity functions (2006)
Maria-florina Balcan, Avrim Blum
Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly very high...
On a theory of learning with similarity functions (2006)
Maria-florina Balcan, Avrim Blum
Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly very high...
Approximation Algorithms and Online Mechanisms for Item Pricing (2006)
Maria-florina Balcan, Avrim Blum
We present approximation and online algorithms for a number of problems of pricing items for sale so as to maximize seller’s revenue in an unlimited supply setting. Our first result is an...
Computational Aspects of Preference Aggregation (2006)
Vincent Conitzer, Avrim Blum, Tom Mitchell
IIS-0427858, IIS-0234695, and IIS-0121678, as well as a Sloan Fellowship awarded to Tuomas Sandholm, and an IBM Ph.D. Fellowship. The views and conclusions contained in this document are those of the...
An augmented pac model for semi-supervised learning (2006)
Maria-florina Balcan, Avrim Blum
The standard PAC-learning model has proven to be a useful theoretical framework for thinking about the problem of supervised learning. However, it does not tend to capture the assumptions underlying...
Avrim Blum, Eyal Even-dar, Katrina Ligett
There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an...
Approximation Algorithms and Online Mechanisms for Item Pricing (2006)
Maria-florina Balcan, Avrim Blum
Abstract: We present approximation and online algorithms for problems of pricing a collection of items for sale so as to maximize the seller’s revenue in an unlimited supply setting. Our first...
On a theory of learning with similarity functions (2006)
Maria-florina Balcan, Avrim Blum, Nathan Srebro
Abstract. Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly...
Mechanism Design via Machine Learning (2005)
Balcan, Maria-Florina, Blum, Avrim, Hartline, Jason, Mansour, Yishay
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide variety of revenue-maximizing...
From External to Internal Regret (2005)
External regret compares the performance of an online algorithm, selecting among $N$ actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an...
Near-Optimal Online Auctions (2005)
Abstract We consider the online auction problem proposed byBar-Yossef, Hildrum, and Wu [4] in which an auctioneer is selling identical items to bidders arriving one at atime. We give an auction that...
New Streaming Algorithms for Fast Detection of Superspreaders (2005)
Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum
High-speed monitoring of Internet traffic is an important and challenging problem, with applications to realtime attack detection and mitigation, traffic engineering, etc. However, packet-level...
Mechanism Design via Machine Learning (2005)
Avrim Blum, Jason D. Hartline, Yishay Mansour
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing...
Approximation Algorithms for Item Pricing (2005)
We present approximation algorithms for a number of problems of pricing items for sale so as to maximize seller's revenue in an unlimited supply setting. Our main result is an O(k)-...
Approximation Algorithms and Online Mechanisms for (2005)
Maria-florina Balcan, Avrim Blum
We present approximation and online algorithms for a number of problems of pricing items for sale so as to maximize seller's revenue in an unlimited supply setting. Our first result is an...
Person Identification in Webcam Images: (2005)
An Application Of, Maria-florina Balcan, Avrim Blum, Patrick Pakyan Choi, John Lafferty, Brian Pantano, ...
An application of semi-supervised learning is made to the problem of person identification in low quality webcam images. Using a set of images of ten people collected over a period of four months,...
A PAC-style Model for Learning from Labeled and Unlabeled Data (2005)
Maria-florina Balcan, Avrim Blum
There has been growing interest in practice in using unlabeled data together with labeled data in machine learning, and a number of di#erent approaches have been developed. However, the assumptions...
An Augmented PAC Model for SemiSupervised Learning (2005)
Maria-florina Balcan, Avrim Blum
that these numbers depend on. We provide examples of sample-complexity bounds both for uniform convergence and #-cover based algorithms, as well as several algorithmic results. 21.1 Introduction As...
Random Projection, Margins, Kernels, and (2005)
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...
Random projection, margins, kernels, and feature-selection (2005)
Abstract. 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...
From external to internal regret (2005)
Avrim Blum, Yishay Mansour, Ron Meir
External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an...
A PAC-style model for learning from labeled and unlabeled data (2005)
Maria-florina Balcan, Avrim Blum
There has recently been substantial interest in practice in using unlabeled data together with labeled data in machine learning, and a number of di erent approaches have been developed. However, the...
Random projection, margins, kernels, and feature-selection (2005)
Abstract. 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...
From external to internal regret (2005)
Avrim Blum, Yishay Mansour, Ron Meir
External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an...
Mechanism design via machine learning (2005)
Maria-florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour
Science Foundation, by a grant from BSF and an IBM faculty award. This publication reflects only the authors ’ views.
New Streaming Algorithms for Fast Detection of Superspreaders (2005)
Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum
High-speed monitoring of Internet traffic is an important and challenging problem, with applications to realtime attack detection and mitigation, traffic engineering, etc. However, packet-level...
Practical privacy: The SuLQ framework (2005)
Avrim Blum, Cynthia Dwork, Frank Mcsherry, Kobbi Nissim
Abstract. We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a...
A PAC-style model for learning from labeled and unlabeled data (2005)
Maria-florina Balcan, Avrim Blum
Abstract. There has been growing interest in practice in using unlabeled data together with labeled data in machine learning, and a number of different approaches have been developed. However, the...
Semi-supervised learning using randomized mincuts (2004)
Avrim Blum, John Lafferty, Mugizi Robert Rwebangira, Rajashekar Reddy
In many application domains there is a large amount of unlabeled data but only a very limited amount of labeled training data. One general approach that has been explored for utilizing this unlabeled...
Semi-Supervised Training of Models for Appearance-Based Statistical Object Detection Methods (2004)
Charles Joseph Rosenberg, Henry Schneiderman, Avrim Blum
policies, either expressed or implied of Carnegie Mellon University or the Eastman Kodak Company.
Preference elicitation and query learning (2004)
Avrim Blum, Jeffrey Jackson, Tuomas Sandholm, Martin Zinkevich, Kristin Bennett, Nicolò Cesa-bianchi
In this paper we explore the relationship between “preference elicitation”, a learning-style problem that arises in combinatorial auctions, and the problem of learning via queries studied in...
New Streaming Algorithms for Fast Detection (2004)
Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum, Of Superspreaders, Shobha Venkataraman, ...
OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in
On kernels, margins and low-dimensional mappings (2004)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Kernel functions are typically viewed as providing an implicit mapping of points into a high-dimensional space, with the ability to gain much of the power of that space without incurring a high cost...
Detection of interactive stepping stones: Algorithms and confidence bounds (2004)
Avrim Blum, Dawn Song, Shobha Venkataraman
Abstract. Intruders on the Internet often prefer to launch network intrusions indirectly, i.e., using a chain of hosts on the Internet as relay machines using protocols such as Telnet or SSH. This...
Preference elicitation and query learning (2004)
Avrim Blum, Jeffrey Jackson, Tuomas S, Martin Zinkevich
Abstract. In this paper we initiate an exploration of relationships between “preference elicitation”, a learning-style problem that arises in combinatorial auctions, and the problem of learning...
Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows (2004)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible...
Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds (2004)
Avrim Blum, Dawn Song, Shobha Venkataraman
Intruders on the Internet often prefer to launch network intrusions indirectly, i.e., using a chain of hosts on the Internet as relay machines using protocols such as Telnet or SSH. This type of...
From External to Internal Regret (2004)
External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an...
Kernels as Features: On Kernels, Margins, and Low-dimensional Mappings (2004)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Kernel functions are typically viewed as providing an implicit mapping of points into a high-dimensional space, with the ability to gain much of the power of that space without incurring a high cost...
Co-Training and Expansion: Towards Bridging Theory and Practice (2004)
Maria-florina Balcan, Avrim Blum, Ke Yang
Co-training is a method for combining labeled and unlabeled data when examples can be thought of as containing two distinct sets of features. It has had a number of practical successes, yet previous...
Approximation Algorithms for Deadline-TSP and Vehicle (2004)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible...
Semi-supervised learning using randomized mincuts (2004)
Avrim Blum, John Lafferty, Mugizi Robert Rwebangira, Rajashekar Reddy
In many application domains there is a large amount of unlabeled data but only a very limited amount of labeled training data. One general approach that has been explored for utilizing this unlabeled...
Semi-Supervised Training of Models for Appearance-Based Statistical Object Detection Methods (2004)
Charles Joseph Rosenberg, Henry Schneiderman, Avrim Blum
policies, either expressed or implied of Carnegie Mellon University or the Eastman Kodak Company.
Semi-supervised learning using randomized mincuts (2004)
Avrim Blum, John Lafferty, Mugizi Robert Rwebangira, Rajashekar Reddy
In many application domains there is a large amount of unlabeled data but only a very limited amount of labeled training data. One general approach that has been explored for utilizing this unlabeled...
Kernels as features: On kernels, margins, and low-dimensional mappings (2004)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Abstract. Kernel functions are typically viewed as providing an implicit mapping of points into a high-dimensional space, with the ability to gain much of the power of that space without incurring a...
Approximation algorithms for deadline-tsp and vehicle routing with time-windows (2004)
Nikhil Bansal, Shuchi Chawla, Avrim Blum, Adam Meyerson
Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible...
Kernels as features: On kernels, margins, and low-dimensional mappings (2004)
Maria-florina Balcan, Avrim Blum, Santosh Vempala
Abstract. Kernel functions are typically viewed as providing an implicit mapping of points into a high-dimensional space, with the ability to gain much of the power of that space without incurring a...
New Streaming Algorithms for Fast Detection of (2004)
Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum
conclusions contained here are those of the authors and should not be interpreted as necessarily representing the
A PAC-style Model for Learning from Labeled and Unlabeled Data (2004)
Maria-florina Balcan, Avrim Blum
There has recently been substantial interest in practice in using unlabeled data together with labeled data in machine learning, and a number of different approaches have been developed. However, the...
Detection of interactive stepping stones: Algorithms and confidence bounds (2004)
Avrim Blum, Dawn Song, Shobha Venkataraman
Abstract. Intruders on the Internet often prefer to launch network intrusions indirectly, i.e., using a chain of hosts on the Internet as relay machines using protocols such as Telnet or SSH. This...
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary (2004)
H. Brendan Mcmahan, Avrim Blum
Abstract. We give an algorithm for the bandit version of a very general online optimization problem considered by Kalai and Vempala [1], for the case of an adaptive adversary. In this problem we are...
Approximation algorithms for deadline-TSP and vehicle routing with time-windows (2004)
Nikhil Bansal, Shuchi Chawla, Avrim Blum, Adam Meyerson
Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible...
On Statistical Query Sampling and NMR Quantum Computing (2003)
We introduce a ``Statistical Query Sampling'' model, in which the goal of an algorithm is to produce an element in a hidden set $Ssubseteqbit^n$ with reasonable probability. The algorithm gains...
Admission Control to Minimize Rejections (2003)
Blum, Avrim, Kalai, Adam, Kleinberg, Jon
Admission control (call control) is a well-studied online problem. We are given a fixed graph with edge capacities, and must process a sequence of calls that arrive over time, accepting some and...
Online oblivious routing (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of ows), without knowledge of the tra c or...
Online oblivious routing (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic...
Online learning in online auctions (2003)
Avrim Blum, Atri Rudra, Felix Wu
We consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this paper, we demonstrate that results from online...
Planning in the presence of cost functions controlled by an adversary (2003)
H. Brendan Mcmahan, Geoffrey J Gordon, Avrim Blum
We investigate methods for planning in a Markov Decision Process where the cost function is chosen by an adversary after we fix our policy. As a running example, we consider a robot path planning...
Online oblivious routing (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic...
Scheduling for flow-time with admission control (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere
Abstract. We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total flow...
Approximation algorithms for orienteering and discounted-reward tsp (2003)
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff
Abstract In this paper, we give the first constant-factor approx-imation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by...
Approximation algorithms for orienteering and discounted-reward tsp (2003)
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff
In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot...
On polynomial-time preference elicitation with value queries (2003)
Martin A. Zinkevich, Avrim Blum, Tuomas Sandholm
Preference elicitation--- the process of asking queries to determine parties ' preferences--- is a key part of many problems in electronic commerce. For example, a shopping agent needs to know a...
Noise-tolerant learning, the parity problem, and the Statistical Query model (2003)
Avrim Blum Carnegie, Avrim Blum, Adam Kalai
We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise. This results in a polynomial-time algorithm for the case of parity...
Noise-tolerant learning, the parity problem, and the Statistical Query model (2003)
Avrim Blum, Adam Kalai, Hal Wasserman, Carnegie Mellon Univeristy
We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise. By applying this algorithm to the restricted case of parity...
Online Learning in Online Auctions (2003)
Avrim Blum, Vijay Kuma, Atri Rudra, Felix Wu
We consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this paper, we demonstrate that results from online...
Scheduling for Flow-Time with Admission Control (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere
We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total ow time and...
Approximation Algorithms for Orienteering and Discounted-Reward TSP (2003)
Avrim Blum Shuchi, Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, ...
In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the DiscountedReward TSP, motivated by robot...
Scheduling for flow-time with admission control (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere
Abstract. We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total flow...
Approximation algorithms for orienteering and discounted-reward tsp (2003)
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff
In this paper, we give the first constant-factor approximation algorithm for the rooted ORIENTEER-ING problem, as well as a new problem that we call the DISCOUNTED-REWARD-TSP, motivated by robot...
Online Learning in Online Auctions (2003)
Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu
We consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this note, we demonstrate that results from online...
Combining Online Algorithms for Rejection and Acceptance (2003)
Yossi Azar, Avrim Blum, Yishay Mansour
Resource allocation and admission control are critical tasks in a communication network, that often must be performed online. Algorithms for these types of problems have been considered both under...
Planning in the Presence of Cost Functions (2003)
Controlled By An, H. Brendan Mcmahan, Geo#rey J Gordon, Avrim Blum
We investigate methods for planning in a Markov Decision Process where the cost function is chosen by an adversary after we fix our policy. As a running example, we consider a robot path planning...
Avrim Blum And, Avrim Blum, John Langford
We point out that a number of standard sample complexity bounds (VC-dimension, PAC-Bayes, and others) are all related to the number of bits required to communicate the labels given the unlabeled data...
Approximation Algorithms for Orienteering and Discounted-Reward TSP (2003)
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff
In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot...
Online oblivious routing (2003)
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic...
Nikhil Bansal, Avrim Blum, Shuchi Chawla
We consider the following clustering problem: we have a complete graph on Ò vertices (items), where each edge Ù � Ú is labeled either or depending on whether Ù and Ú have been deemed to be...
Nikhil Bansal, Avrim Blum, Shuchi Chawla
Abstract. We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge u�v is labeled either or depending on whether u and v have been deemed to be...
Nikhil Bansal, Avrim Blum, Shuchi Chawla
We consider the following clustering problem: we have a complete graph onÒvertices (items), where each edge Ù�Úis labeled either or depending on whetherÙand Úhave been deemed to be similar or...
Smoothed analysis of the perceptron algorithm for linear programming (2002)
The smoothed complexity [1] of an algorithm is the expected running time of the algorithm on an arbitrary instance under a random perturbation. It was shown recently that the simplex algorithm has...
Online Algorithms for Market Clearing (2002)
Avrim Blum, Tuomas Sandholm, Martin Zinkevich
In this paper we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at dierent...
Nikhil Bansal, Avrim Blum, Shuchi Chawla
We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u; v) is labeled either + or depending on whether u and v have been deemed to be similar...
Smoothed analysis of the perceptron algorithm for linear programming (2002)
The smoothed complexity [1] of an algorithm is the expected running time of the algorithm on an arbitrary instance under a random perturbation. It was shown recently that the simplex algorithm has...
Static Optimality and Dynamic Search-Optimality in Lists and Trees (2002)
Avrim Blum, Shuchi Chawla, Adam Kalai
Adaptive data structures form a central topic of online algorithms research, beginning with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and...
Online Algorithms for Market Clearing (2002)
Avrim Blum, Tuomas Sandholm, Martin Zinkevich
In this paper we study the problem of online market clearing where there is one commodity in the market, being bought and sold by multiple buyers and sellers who submit buy and sell bids that arrive...
Approximation Algorithms for Orienteering and Discounted-Reward TSP (2002)
Avrim Blum, Shuchi Chawla, Adam Meyerson, Terran Lane, David R. Karger, Maria Minkoff
In this paper, wegive the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot...
Static Optimality and Dynamic Search-Optimality in Lists and Trees (2002)
Avrim Blum, Shuchi Chawla, Adam Kalai
Adaptive data structures form a central topic of online algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve static...
Online Algorithms for Market Clearing (2002)
Avrim Blum, Tuomas Sandholm, Martin Zinkevich
Abstract. In this article, we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire...
Static Optimality and Dynamic Search-Optimality in Lists and Trees (2002)
Avrim Blum, Shuchi Chawla, Adam Kalai
Abstract. Adaptive data structures form a central topic of on-line algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve...
Nikhil Bansal, Avrim Blum, Shuchi Chawla
Abstract. We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge ¡ u ¢ v £ is labeled either ¤ or ¥ depending on whether u and v have been...
Admission control to minimize rejections (2001)
Avrim Blum, Adam Kalai, Jon Kleinberg
Abstract. Admission control (call control) is a well-studied online problem. We are given a xed graph with edge capacities, and must process a sequence of calls that arrive over time, accepting some...
Learning from labeled and unlabeled data using graph mincuts (2001)
Many application domains suer from not having enough labeled training data for learning. However, large amounts of unlabeled examples can often be gathered cheaply. As a result, there has been a...
Admission Control to Minimize Rejections (2001)
Avrim Blum, Adam Kalai, Jon Kleinberg
Admission control (call control) is a well-studied online problem.
Microchoice Bounds and Self Bounding Learning Algorithms (2001)
A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we...
Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model (2000)
Blum, Avrim, Kalai, Adam, Wasserman, Hal
We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise. This results in a polynomial-time algorithm for the case of parity...
Featureboost: A meta-learning algorithm that improves model robustness (2000)
John Langford, Rich Caruana, Avrim Blum
Most machine learning algorithms are lazy: they extract from the training set the minimum information needed to predict its labels. Unfortunately, this often leads to models that are not robust when...
FeatureBoost: A Meta Learning Algorithm that Improves Model Robustness (2000)
Joseph O'Sullivan, John Langford, Rich Caruana, Avrim Blum
Most machine learning algorithms are lazy: they extract from the training set the minimum information needed to predict its labels. Unfortunately, this often leads to models that are not robust when...
FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness (2000)
Joseph Sullivan Josullvn, John Langford, Rich Caruana, Avrim Blum
Most machine learning algorithms are lazy: they extract from the training set the minimum information needed to predict its labels. Unfortunately, this often leads to models that are not robust when...
Featureboost: A meta-learning algorithm that improves model robustness (2000)
John Langford, Rich Caruana, Avrim Blum
Most machine learning algorithms are lazy: they extract from the training set the minimum information needed to predict its labels. Unfortunately, this often leads to models that are not robust when...
Noise-tolerant learning, the parity problem, and the statistical query model (2000)
Avrim Blum, Adam Kalai, Hal Wasserman
Abstract. We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and...
Microchoice bounds and self bounding learning algorithms (1999)
A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we...
Finely-competitive paging (1999)
Avrim Blum, Carl Burch, Adam Kalai
We construct an online algorithm for paging that achieves an O(r + log k) competitive ratio when compared to an offline strategy that is allowed the additional ability to "rent "...
Microchoice bounds and self bounding learning algorithms (1999)
A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we...
Iterative Macro-Operators Revisited: Applying Program Synthesis to Learning in Planning (1999)
Ute Schmid, Jana Koehler, Avrim Blum
supported by a DFG research scholarship. The idea of combining planning and program synthesis was suggested by Fritz Wysotzki. Part of the work reported here was already done or prepared during the...
Microchoice bounds and self bounding learning algorithms (1999)
Our goal is proving tighter upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. We prove bounds for learning algorithms that operate by...
Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation (1999)
Avrim Blum, Adam Kalai, John Langford
The empirical error on a test set, the hold-out estimate, often is a more reliable estimate of generalization error than the observed error on the training set, the training estimate. K-fold cross...
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1999)
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
Microchoice Bounds and Self Bounding Learning Algorithms (1999)
We prove adaptive bounds for learning algorithms that operate by making a sequence of choices. These adaptive bounds, which we call Microchoice bounds, can be used to make these algorithms...
Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation (1999)
Avrim Blum, Adam Kalai, John Langford
The empirical error on a test set, the hold-out estimate, often is a more reliable estimate of generalization error than the observed error on the training set, the training estimate. K-fold cross...
Avrim Blum, Progressive Cross-validation
The empirical error on a test set, the hold-out estimate, often is a more reliable estimate of generalization error than the observed error on the training set, the training estimate. K-fold cross...
On-line algorithms for combining language models (1999)
Adam Kalai, Stanley Chen, Avrim Blum, Ronald Rosenfeld
Multiple language models are combined for many tasks in language modeling, such as domain and topic adaptation. In this work, we compare on-line algorithms from machine learning to existing...
On-line algorithms for combining language models (1999)
Adam Kalai, Stanley Chen, Avrim Blum, Ronald Rosenfeld
Multiple language models are combined for many tasks in language modeling, such as domain and topic adaptation. In this work, we compare on-line algorithms from machine learning to existing...
Combining labeled and unlabeled data with co-training (1998)
We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a setting in...
Combining labeled and unlabeled data with co-training (1998)
avrim+Qcs.cmu.edu We consider the problem of using a large unla-beled sample to boost performance of a learn-ing algorit,hrn when only a small set of labeled examples is available. In particular, we...
Combining labeled and unlabeled data with co-training (1998)
We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a problem...
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems (1998)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
Combining Labeled and Unlabeled Data with Co-Training (1998)
We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a problem...
On-Line Algorithms for Combining Language Models (1998)
Adam Kalai, Stanley Chen, Avrim Blum, Ronald Rosenfeld
Multiple language models are combined for many tasks in language modeling, such as domain and topic adaptation. In this work, we compare on-line algorithms from machine learning to existing...
Combining Labeled and Unlabeled Data with Co-Training (1998)
We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a setting in...
A Note on Learning from Multiple-Instance Examples (1998)
. We describe a simple reduction from the problem of PAC-learning from multiple-instance examples to that of PAC-learning with one-sided random classification noise. Thus, all concept classes...
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane (1998)
Avrim Blum, Prasad Chalasani, Santosh Vempala
. We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original subdivision....
On-Line Algorithms for Combining Language Models (1998)
Adam Kalai, Stanley Chen, Avrim Blum, Ronald Rosenfeld
Multiple language models are combined for many tasks in language modeling, such as domain and topic adaptation. In this work, we compare on-line algorithms from machine learning to existing...
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane (1998)
Avrim Blum, Prasad Chalasani, Santosh Vempala
.<F3.826e+05> We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original...
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems (1998)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane (1998)
Avrim Blum, Prasad Chalasani, Santosh Vempala
We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original subdivision....
On Learning Read-k-Satisfy-j DNF (1998)
Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth, ...
.<F3.824e+05> We study the learnability of<F3.347e+05><F3.824e+05><F3.347e+05> read-k-satisfy-j<F3.824e+05> (RkSj) DNF formulas. These are boolean formulas in...
On-Line Algorithms For Combining Language Models (1998)
Adam Kalai Stanley, Stanley Chen, Avrim Blum, Ronald Rosenfeld
Multiple language models are combined for many tasks in language modeling, such as domain and topic adaptation. In this work, we compare on-line algorithms from machine learning to existing...
Combining labeled and unlabeled data with co-training (1998)
We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a problem...
Edge Coloring, Polyhedra and Probability (1998)
Ljubomir Perkovic, Alan Frieze, Avrim Blum, Jeong Han Kim
Submitted inpartial ful llment of the requirements
A note on learning from multiple-instance examples (1998)
We describe a simple reduction from the problem of PAC-learning from multiple-instance examples to that of PAC-learning with one-sided random classi cation noise. Thus, all concept classes learnable...
On-line learning and the metrical task system problem (1997)
We relate two problems that have been explored in two distinct communities. The first is the problem of combining expert advice, studied extensively in the computational learning theory literature,...
On-line learning and the metrical task system problem (1997)
AbsLracL. The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of...
This paper describes experimental results on using Winnow and Weighted-Majority based algorithms on a real-world calendar scheduling domain. These two algorithms have been highly studied in the...
A polylog(n)-competitive algorithm for metrical task systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) against an oblivious adversary, on any metric space. This is the first...
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems (1997)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
. This paper describes experimental results on using Winnow and Weighted-Majority based algorithms on a real-world calendar scheduling domain. These two algorithms have been highly studied in the...
Selection of Relevant Features and Examples in Machine Learning (1997)
In this survey, we review work in machine learning on methods for handling data sets containing large amounts of irrelevant information. We focus on two key issues: the problem of selecting relevant...
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems (1997)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
Learning With Unreliable Boundary Queries (1997)
Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim
We introduce a model for learning from examples and membership queries in situations where the boundary between positive and negative examples is somewhat ill-defined. In our model, queries near the...
Polylog(n)-Competitive Algorithm for Metrical Task Systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) against an oblivious adversary, on any metric space. This is the first...
Polylog(n)-Competitive Algorithm For Metrical Task Systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) for arbitrary metric spaces, against an oblivious adversary. This is the...
On-line Learning and the Metrical Task System Problem (1997)
. The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line...
Universal Portfolios With and Without Transaction Costs (1997)
A constant rebalanced portfolio is an investment strategy which keeps the same distribution of wealth among a set of stocks from period to period. Recently there has been work on on-line investment...
On-line Learning and the Metrical Task System Problem (1997)
In this paper, we relate the problem of combining expert advice, studied extensively in the Computational Learning Theory literature, to the Metrical Task System (MTS) problem, studied extensively in...
On-line Learning and the Metrical Task System Problem (1997)
. The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line...
Universal portfolios with and without transaction costs (1997)
Abstract. A constant rebalanced portfolio is an investment strategy which keeps the same distribution of wealth among a set of stocks from period to period. Recently there has been work on on-line...
A Constant-factor Approximation Algorithm for the k-MST Problem (Extended Abstract) (1996)
Avrim Blum, R. Ravi, Santosh Vempala
) Avrim Blum R. Ravi y Santosh Vempala z Abstract Given an undirected graph with non-negative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes. This...
A Polynomial-time Algorithm for Learning Noisy Linear Threshold Functions (1996)
Avrim Blum, Alan Frieze, Ravi Kannan, Santosh Vempala
In this paper we consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into...
An Õ(n^3/14)-Coloring Algorithm for 3-Colorable Graphs (1996)
We show how the results of Karger, Motwani, and Sudan [6] and Blum [3] can be combined in a natural manner to yield a polynomial-time algorithm for ~ O(n 3=14 )-coloring any n-node 3-colorable graph....
A Polynomial-time Algorithm for Learning Noisy Linear Threshold Functions (1996)
Avrim Blum, Alan Frieze, Ravi Kannan, Santosh Vempala
In this paper we consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a \perceptron"). Methods for solving this problem generally fall into two...
Randomized Robot Navigation Algorithms (1996)
Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosén, Michael Saks
We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...
A Constant-factor Approximation Algorithm for the k-MST Problem (1996)
Avrim Blum, R. Ravi, Santosh Vempala
Given an undirected graph with non-negative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes. This problem is known to be NP-hard. We present a...
Avrim Blum, Merrick L. Furst, Andrew Tomkins
We consider an extension of the standard on-line model to settings in which an on-line algorithm has free time between successive requests in an input sequence. During this free time, the algorithm...
On-Line Algorithms in Machine Learning (1996)
. The areas of On-Line Algorithms and Machine Learning are both concerned with problems of making decisions about the present based only on knowledge of the past. Although these areas differ in terms...
A Polynomial-time Algorithm for Learning Noisy Linear Threshold Functions (1996)
Avrim Blum, Alan Frieze, Ravi Kannan, Santosh Vempala
In this paper we consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into...
On-Line Algorithms in Machine Learning (1996)
The areas of On-Line Algorithms and Machine Learning are both concerned with problems of making decisions about the present based only on knowledge of the past. Although these areas differ in terms...
On Learning Read-k-Satisfy-j DNF (1996)
Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth
We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by...
Learning With Unreliable Boundary Queries (1995)
Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim
We introduce a model for learning from examples and membership queries in situations where the boundary between positive and negative examples is somewhat ill-defined. In our model, queries near the...
Improved Approximation Guarantees for Minimum-Weight (1995)
Trees And, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Learning With Unreliable Boundary Queries (1995)
Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim
We introduce a new model for learning with membership queries in which queries near the boundary of a target concept may receive incorrect or "don't care" responses. In partial...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1995)
Baruch Awerbuch, Yossi Azar, Avrim Blum, And Santosh Vempala, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1995)
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes (1995)
Avrim Blum, Lisa Hellerstein, Nick Littlestone
This paper addresses the problem of learning boolean functions in query and mistake-bound models in the presence of irrelevant attributes. In learning a concept, a learner may observe a great many...
On the minimum latency problem (1994)
Blum, Avrim, Chalasani, Prasad, Coppersmith, Don, Pulleyblank, Bill, Raghavan, Prabhakar, Sudan, Madhu
We are given a set of points $p_1,\ldots , p_n$ and a symmetric distance matrix $(d_{ij})$ giving the distance between $p_i$ and $p_j$. We wish to construct a tour that minimizes $\sum_{i=1}^n...
An on-line algorithm for improving performance in navigation (1994)
Blum, Avrim, Chalasani, Prasad
Recent papers have shown optimally-competitive on-line strategies for a robot traveling from a point $s$ to a point $t$ in certain unknown geometric environments. We consider the question: Having...
Combining online algorithms for rejection and acceptance (1994)
Yossi Azar, Avrim Blum, Yishay Mansour
Resource allocation and admission control are critical tasks in a communication network, that often must be performed online. Algorithms for these types of problems have been considered both under...
On learning read-k-satisfy-j dnf (1994)
Avrim Blum, Roni Khardont, Eyal Kushilevitzi, Leonard Pitt, Dan Rothf
We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF for-mulae in which the maximal number of occur-rences of a variable is bounded by k, and the number of terms satisfied...
On learning read-k-satisfy-j dnf (1994)
Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth
We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by...
Weakly learning DNF and characterizing statistical query learning using Fourier analysis (1994)
Avrim Blum, Merrick Furst, Michael Kearns, Yishay Mansour, Tel-aviv U, Steven Rudich, ...
We present new results on the well-studied problem of learning DNF expressions. We prove that an algorithm due to Kushilevitz and Mansour [13] can be used to weakly learn DNF formulas with membership...
New Approximation Algorithms for Graph Coloring (1994)
The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k 3. This paper explores the approximation problem of...
The Minimum Latency Problem (1994)
Avrim Blum, Prasad Chalasani, Bill Pulleyblank, Prabhakar Raghavan
We are given a set of points p 1 ; . . . ; p n and a symmetric distance matrix (d ij ) giving the distance between p i and p j . We wish to construct a tour that minimizes P n i=1 `(i), where `(i) is...
Cryptographic Primitives Based on Hard Learning Problems (1994)
Avrim Blum, Merrick Furst, Michael Kearns, Richard J. Lipton
this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. In doing so, we develop...
Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis (1994)
Avrim Blum, Jeffrey Jackson, Michael Kearns, Yishay Mansour, Steven Rudich
We present new results, both positive and negative, on the well-studied problem of learning disjunctive normal form (DNF) expressions. We first prove that an algorithm due to Kushilevitz and Mansour...
Improved Approximation Guarantees for Minimum-Weight (1994)
Trees And Prize-Collecting, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, ...
We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by...
The Minimum Latency Problem (1994)
Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, Madhu Sudan
We are given a set of points p 1 ; : : : ; p n and a symmetric distance matrix (d ij ) giving the distance between p i and p j . We wish to construct a tour that minimizes P n i=1 `(i), where `(i) is...
An On-Line Algorithm for Improving Performance in Navigation (1993)
We consider the following scenario. A point robot is placed at some start location s in a 2dimensional scene containing oriented rectangular obstacles. The robot must repeatedly travel back and forth...
Avrim Blum, Carnegie Mellon U, Michael Kearns, Merrick Furst, Carnegie Mellon U, Yishay Mansour, ...
We present new results on the well-studied problem of learning DNF expressions. We prove that an algorithm due to Kushilevitz and Mansour [13] can be used to weakly learn DNF formulas with membership...
Learning boolean functions in an infinite attribute space (1992)
This paper presents a theoretical model for learning Boolean functions in domains having a large, potentially infinite number of attributes. The model allows an algorithm to employ a rich vocabulary...
Fast Learning of k-Term DNF Formulas with Queries (1992)
This paper presents an algorithm that uses equivalence and membership queries to learn the class of k-term DNF formulas in time O(n \Delta k O(k) ), where n is the number of input variables. This...
Learning Switching Concepts (1992)
We consider learning in situations where the function used to classify examples may switch back and forth between a small number of different concepts during the course of learning. We examine...
Algorithms for approximate graph coloring /--by Avrim Louis Blum. (1991)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1991.
Algorithms for approximate graph coloring (1991)
A coloring of a graph is an assignment of colors to the vertices so that no two adjacent vertices are given the same color. The problem of coloring a graph with the minimum number of colors is well...
Navigating in Unfamiliar Geometric Terrain (1991)
Avrim Blum, Prabhakar Raghavan, Baruch Schieber, Pii S
Abstract. Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way. The robot always knows its current absolute position...
Navigating In Unfamiliar Geometric Terrain (1991)
. Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way. The robot always knows its current absolute position and that...
Linear Approximation of Shortest Superstrings (1991)
Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis
We consider the following problem: given a collection of strings s 1 ; . . . ; s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s. Although this...
Linear Approximation of Shortest Superstrings (1991)
Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis
We consider the following problem: given a collection of strings s 1 ; : : : ; s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s. Although this...
On the computational complexity of training simple neural networks /--by Avrim Blum. (1989)
Supervised by Ronald L. Rivest.
New Streaming Algorithms for Fast Detection of Superspreaders
Shobha Venkataraman Dawn, Dawn Song, Phillip B. Gibbons, Avrim Blum
High-speed monitoring of Internet traffic is an important and challenging problem, with applications to realtime attack detection and mitigation, traffic engineering, etc. However, packet-level...