Avrim Blum

Or Sheffet

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Improved Guarantees for Agnostic Learning of Disjunctions.

[BibT_eX]

[DOI]

Pranjal Awasthi

Or Sheffet

Proceedings of the COLT 2010, 2010

2009

Veritas: Combining Expert Opinions without Labeled Data.

[BibT_eX]

[DOI]

Int. J. Artif. Intell. Tools, 2009

Improved equilibria via public service advertising.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximate clustering without the approximation.

[BibT_eX]

[DOI]

Anupam Gupta

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Tracking Dynamic Sources of Malicious Activity at Internet Scale.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

2008

Item pricing for revenue maximization.

[BibT_eX]

[DOI]

SIGecom Exch., 2008

A theory of learning with similarity functions.

[BibT_eX]

[DOI]

Nathan Srebro

Mach. Learn., 2008

Reducing mechanism design to algorithm design via machine learning.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

A learning theory approach to non-interactive database privacy.

[BibT_eX]

[DOI]

Katrina Ligett

Aaron Roth

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Regret minimization and the price of total anarchy.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Katrina Ligett

Aaron Roth

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

A discriminative framework for clustering via similarity functions.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Limits of Learning-based Signature Generation with Adversaries.

[BibT_eX]

[DOI]

Shobha Venkataraman

Dawn Song

Proceedings of the Network and Distributed System Security Symposium, 2008

Veritas: Combining Expert Opinions without Labeled Data.

[BibT_eX]

[DOI]

Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2008), 2008

Improved Guarantees for Learning via Similarity Functions.

[BibT_eX]

[DOI]

Nathan Srebro

Proceedings of the 21st Annual Conference on Learning Theory, 2008

Clustering with Interactive Feedback.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

2007

Approximation Algorithms and Online Mechanisms for Item Pricing.

[BibT_eX]

[DOI]

Theory Comput., 2007

Mechanism design, machine learning, and pricing problems.

[BibT_eX]

[DOI]

SIGecom Exch., 2007

Approximation Algorithms for Orienteering and Discounted-Reward TSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Introduction to the special issue on COLT 2006.

[BibT_eX]

[DOI]

Gábor Lugosi

Hans Ulrich Simon

Mach. Learn., 2007

From External to Internal Regret.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2007

A Theory of Loss-Leaders: Making Money by Pricing Below Cost.

[BibT_eX]

[DOI]

T.-H. Hubert Chan

MohammadTaghi Hajiaghayi

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.

[BibT_eX]

[DOI]

David J. Abraham

Tuomas Sandholm

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Separating Populations with Wide Data: A Spectral Analysis.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

A Theory of Similarity Functions for Learning and Clustering.

[BibT_eX]

[DOI]

Proceedings of the Discovery Science, 10th International Conference, 2007

Open Problems in Efficient Semi-supervised PAC Learning.

[BibT_eX]

[DOI]

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

Kernels as features: On kernels, margins, and low-dimensional mappings.

[BibT_eX]

[DOI]

Mach. Learn., 2006

Online algorithms for market clearing.

[BibT_eX]

[DOI]

Tuomas Sandholm

Martin Zinkevich

J. ACM, 2006

On a theory of learning with similarity functions.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning, 2006

Black Box Anomaly Detection: Is It Utopian?.

[BibT_eX]

[DOI]

Proceedings of the 5th ACM Workshop on Hot Topics in Networks, 2006

A Random-Surfer Web-Graph Model.

[BibT_eX]

[DOI]

T.-H. Hubert Chan

Mugizi Robert Rwebangira

Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

An Augmented PAC Model for Semi-Supervised Learning.

[BibT_eX]

[DOI]

Proceedings of the Semi-Supervised Learning, 2006

2005

Combining Online Algorithms for Acceptance and Rejection.

[BibT_eX]

[DOI]

Theory Comput., 2005

Near-optimal online auctions.

[BibT_eX]

[DOI]

Jason D. Hartline

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Random Projection, Margins, Kernels, and Feature-Selection.

[BibT_eX]

[DOI]

Proceedings of the Subspace, 2005

Practical privacy: the SuLQ framework.

[BibT_eX]

[DOI]

Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

New Streaming Algorithms for Fast Detection of Superspreaders.

[BibT_eX]

[DOI]

Proceedings of the Network and Distributed System Security Symposium, 2005

Mechanism Design via Machine Learning.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

A PAC-Style Model for Learning from Labeled and Unlabeled Data.

[BibT_eX]

[DOI]

Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004

Online learning in online auctions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Correlation Clustering.

[BibT_eX]

[DOI]

Nikhil Bansal

Shuchi Chawla

Mach. Learn., 2004

Preference Elicitation and Query Learning.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2004

Approximation algorithms for deadline-TSP and vehicle routing with time-windows.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds.

[BibT_eX]

[DOI]

Dawn Xiaodong Song

Shobha Venkataraman

Proceedings of the Recent Advances in Intrusion Detection: 7th International Symposium, 2004

Co-Training and Expansion: Towards Bridging Theory and Practice.

[BibT_eX]

[DOI]

Ke Yang

Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004

Semi-supervised learning using randomized mincuts.

[BibT_eX]

[DOI]

John D. Lafferty

Mugizi Robert Rwebangira

Rajashekar Reddy

Proceedings of the Machine Learning, 2004

Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary.

[BibT_eX]

[DOI]

H. Brendan McMahan

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

On Kernels, Margins, and Low-Dimensional Mappings.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003

Microchoice Bounds and Self Bounding Learning Algorithms.

[BibT_eX]

[DOI]

Mach. Learn., 2003

Noise-tolerant learning, the parity problem, and the statistical query model.

[BibT_eX]

[DOI]

Hal Wasserman

J. ACM, 2003

Admission Control to Minimize Rejections.

[BibT_eX]

[DOI]

Adam Tauman Kalai

Jon M. Kleinberg

Internet Math., 2003

On Statistical Query Sampling and NMR Quantum Computing

[BibT_eX]

[DOI]

Ke Yang

Electron. Colloquium Comput. Complex., 2003

Static Optimality and Dynamic Search-Optimality in Lists and Trees.

[BibT_eX]

[DOI]

Shuchi Chawla

Algorithmica, 2003

Online oblivious routing.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Combining online algorithms for rejection and acceptance.

[BibT_eX]

[DOI]

Yossi Azar

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

On polynomial-time preference elicitation with value queries.

[BibT_eX]

[DOI]

Martin Zinkevich

Tuomas Sandholm

Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Planning in the Presence of Cost Functions Controlled by an Adversary.

[BibT_eX]

[DOI]

H. Brendan McMahan

Geoffrey J. Gordon

Proceedings of the Machine Learning, 2003

Machine Learning: My Favorite Results, Directions, and Open Problems.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Scheduling for Flow-Time with Admission Control.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2003

PAC-MDL Bounds.

[BibT_eX]

[DOI]

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

Learning a Function of r Relevant Variables.

[BibT_eX]

[DOI]

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Smoothed analysis of the perceptron algorithm for linear programming.

[BibT_eX]

[DOI]

John Dunagan

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

Learning from Labeled and Unlabeled Data using Graph Mincuts.

[BibT_eX]

Shuchi Chawla

Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28, 2001

2000

Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

An Online Algorithm for Improving Performance in Navigation.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

On-line Learning and the Metrical Task System Problem.

[BibT_eX]

[DOI]

Carl Burch

Mach. Learn., 2000

FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness.

[BibT_eX]

Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29, 2000

1999

Universal Portfolios With and Without Transaction Costs.

[BibT_eX]

[DOI]

Mach. Learn., 1999

A Constant-Factor Approximation Algorithm for the k-MST Problem.

[BibT_eX]

[DOI]

R. Ravi

J. Comput. Syst. Sci., 1999

On-line algorithms for combining language models.

[BibT_eX]

[DOI]

Proceedings of the 1999 IEEE International Conference on Acoustics, 1999

Finely-Competitive Paging.

[BibT_eX]

[DOI]

Carl Burch

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Probabilistic Planning in the Graphplan Framework.

[BibT_eX]

[DOI]

Proceedings of the Recent Advances in AI Planning, 5th European Conference on Planning, 1999

Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998

On a theory of computing symposia.

[BibT_eX]

[DOI]

SIGACT News, 1998

A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane.

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

SIAM J. Comput., 1998

New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

On Learning Read-k-Satisfy-j DNF.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

A Note on Learning from Multiple-Instance Examples.

[BibT_eX]

[DOI]

Mach. Learn., 1998

Learning with Unreliable Boundary Queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.

[BibT_eX]

[DOI]

Algorithmica, 1998

On Learning Monotone Boolean Functions.

[BibT_eX]

[DOI]

Carl Burch

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Combining Labeled and Unlabeled Data with Co-Training.

[BibT_eX]

[DOI]

Tom M. Mitchell

Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997

Navigating in Unfamiliar Geometric Terrain.

[BibT_eX]

[DOI]

Baruch Schieber

SIAM J. Comput., 1997

Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain.

[BibT_eX]

[DOI]

Mach. Learn., 1997

Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution.

[BibT_eX]

[DOI]

Ravindran Kannan

J. Comput. Syst. Sci., 1997

An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs.

[BibT_eX]

[DOI]

David R. Karger

Inf. Process. Lett., 1997

Selection of Relevant Features and Examples in Machine Learning.

[BibT_eX]

[DOI]

Pat Langley

Artif. Intell., 1997

Fast Planning Through Planning Graph Analysis.

[BibT_eX]

[DOI]

Merrick L. Furst

Artif. Intell., 1997

A polylog(n)-Competitive Algorithm for Metrical Task Systems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract).

[BibT_eX]

[DOI]

R. Ravi

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Randomized Robot Navigation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On-line Algorithms in Machine Learning.

[BibT_eX]

[DOI]

Proceedings of the Online Algorithms, 1996

1995

Fast Learning of k-Term DNF Formulas with Queries.

[BibT_eX]

[DOI]

Steven Rudich

J. Comput. Syst. Sci., 1995

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.

[BibT_eX]

[DOI]

Lisa Hellerstein

Nick Littlestone

J. Comput. Syst. Sci., 1995

Coloring Random and Semi-Random k-Colorable Graphs.

[BibT_eX]

[DOI]

Joel Spencer

J. Algorithms, 1995

A constant-factor approximation for the k-MST problem in the plane.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning, 1995

1994

Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Linear Approximation of Shortest Superstrings.

[BibT_eX]

[DOI]

J. ACM, 1994

New Approximation Algorithms for Graph Coloring.

[BibT_eX]

[DOI]

J. ACM, 1994

Weakly learning DNF and characterizing statistical query learning using Fourier analysis.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

The minimum latency problem.

[BibT_eX]

[DOI]

Don Coppersmith

William R. Pulleyblank

Madhu Sudan

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On Learning Read-k-Satisfy-j DNF.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

Learning an Intersection of k Halfspaces over a Uniform Distribution

[BibT_eX]

[DOI]

Ravi Kannan

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

An On-Line Algorithm for Improving Performance in Navigation

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Cryptographic Primitives Based on Hard Learning Problems.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1993

On Learning Embedded Symmetric Concepts.

[BibT_eX]

[DOI]

Jeffrey C. Jackson

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992

Training a 3-node neural network is NP-complete.

[BibT_eX]

[DOI]

Ronald L. Rivest

Neural Networks, 1992

Learning Boolean Functions in an Infinite Attribute Space.

[BibT_eX]

[DOI]

Mach. Learn., 1992

Rank-r Decision Trees are a Subclass of r-Decision Lists.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

A Decomposition Theorem and Bounds for Randomized Server Problems

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Learning Switching Concepts.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991

Navigating in Unfamiliar Geometric Terrain (Preliminary Version)

[BibT_eX]

[DOI]

Baruch Schieber

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Navigating in Unfamiliar Geometric Terrain (Extended Summary).

[BibT_eX]

[DOI]

Baruch Schieber

Proceedings of the On-Line Algorithms, 1991

1990

Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Some Tools for Approximate 3-Coloring (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Learning Functions of k Terms.

[BibT_eX]

[DOI]

Mona Singh

Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

Separating PAC and Mistake-Bound Learning Models Over the Boolean Domain (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989

An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring)

[BibT_eX]

[DOI]