Smoothed Analysis of the
Perceptron Algorithm. With John Dunagan. SODA
'02, pages 905--914.
= Machine Learning, 
= Online algorithms, = Optimization and
Approximation algorithms, 
= Planning and
heuristics, 
= Algorithms on
random/semirandom inputs.
Smoothed Analysis of the
Perceptron Algorithm. With John Dunagan. SODA
'02, pages 905--914.
Online Algorithms for Market
Clearing. With Tuomas Sandholm and Martin
Zinkevich. SODA '02, pages 971-980.
Static Optimality and Dynamic
Search-Optimality in Lists and Trees. With
Shuchi Chawla and Adam Kalai. SODA '02, pages 1-8.
Admission Control to Minimize
Rejections. With Adam Kalai and Jon
Kleinberg. WADS '01 (in LNCS 2125, pp.155-164, 2001).
Learning from Labeled and Unlabeled Data
using Graph Mincuts.
With Shuchi Chawla. ICML '01, pp. 19-26.
FeatureBoost: A Meta Learning Algorithm
that Improves Model Robustness.
With Joseph O'Sullivan, John Langford, and Rich Caruana. ICML '00,
pp. 703--710.
Noise-tolerant Learning, the Parity
problem, and the Statistical Query model.
With Adam Kalai and Hal Wasserman. STOC'00, pp. 435--440.
Finely-competitive Paging.
With Carl Burch and Adam Kalai. FOCS'99, pp. 450--458.
Probabilistic Planning in the
Graphplan Framework. With John Langford. 5th
European Conference on Planning (ECP'99). See the PGP web page.
Beating the Hold-Out: Bounds for K-fold
and Progressive Cross-Validation. With Adam Kalai and John
Langford. Proceedings of the 12th Annual Conference on
Computational Learning Theory (COLT '99), pp. 203--208.
Microchoice Bounds and Self
Bounding Learning Algorithms. With John
Langford. Proceedings of the 12th Annual Conference on
Computational Learning Theory (COLT '99), pp. 209--214. To
appear in Machine Learning.
On-line Algorithms for Combining Language Models.
With Stan Chen, Adam Kalai, and Roni Rosenfeld. In Proceedings of
the International Conference on Accoustics, Speech, and Signal
Processing (ICASSP '99). [postscript]
[gzipped postscript]
On Learning Monotone Boolean
Functions. With Carl Burch and John Langford.
Proceedings of the 39th Annual Symposium on Foundations of
Computer Science (FOCS '98).
Combining Labeled and Unlabeled Data
with Co-Training. With Tom Mitchell.
Proceedings of the 11th Annual Conference on Computational
Learning Theory, pages 92--100, 1998. (The document linked to
here is newer than the COLT version).
On a Theory of Computing Symposia. With
Prabhakar Raghavan. International Conference on Fun with
Algorithms (FUN '98).
Also appeared in SIGACT News, September 1998.
Semi-Definite Relaxations for Minimum Bandwidth and other
Vertex-Ordering problems. With Goran Konjevod,
R. Ravi, and Santosh Vempala. Theoretical Computer
Science, 235(1):25--42, 2000. (Special issue in honor of
Manuel Blum's 60th Birthday!)
Extended abstract in
Proceedings of the 30th Annual Symposium on the Theory of
Computing (STOC '98).
A Note on Learning from Multiple-Instance Examples.
With Adam Kalai. Machine Learning, 30:23--29, 1998.
Universal Portfolios With and Without Transaction Costs.
With Adam Kalai.
Machine Learning, 35: 193--205, 1999 (special
issue for COLT '97). Originally appeared in Proceedings
of the 10th Annual Conference on Computational Learning Theory,
pages 309--313, July 1997.
On-line Learning and the Metrical Task System Problem.
With Carl Burch. Machine Learning, 39: 35--58,
2000. Originally appeared in Proceedings of the 10th Annual
Conference on Computational Learning Theory (COLT '97), pages 45--53.
A polylog(n)-competitive algorithm for metrical task
systems. With Yair Bartal, Carl Burch, and Andrew
Tomkins. Proceedings of the 29th Annual Symposium on the Theory of
Computing (STOC '97), pages 711--719.
An O~(n^{3/14})-Coloring
Algorithm for 3-Colorable Graphs. With David Karger.
Information Processing Letters, 61(1):49--53, January 1997.
On-Line Algorithms in Machine
Learning (a survey). This is a survey paper for a talk
given at the Dagstuhl workshop on On-Line algorithms (June '96).
A Polynomial-time Algorithm for
Learning Noisy Linear Threshold Functions. With Alan
Frieze, Ravi Kannan, and Santosh Vempala. Algorithmica, 22:35--52,
1998. An extended abstract appears in Proceedings of the
37th Annual Symposium on Foundations of Computer Science (FOCS'96),
pages 330--338.
A Constant-factor
Approximation Algorithm for the k-MST Problem.
With R. Ravi and Santosh Vempala. JCSS, 58:101--108 (1999).
An extended abstract appears in Proceedings of the 28th Annual
ACM Symposium on the Theory of Computing (STOC '96), pages 442--448.
Randomized Robot Navigation
Algorithms. With Piotr Berman, Amos Fiat, Howard Karloff,
Adi Rosen, and Michael Saks. In Proceedings of the Seventh Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 75--84, January 1996.
Fast Planning Through Planning
Graph Analysis . With Merrick Furst.
Artificial Intelligence 90:281--300, 1997. An extended
abstract appears in Proceedings of
the 14th International Joint Conference on Artificial Intelligence
(IJCAI), pages 1636--1642, August 1995.
See also the Graphplan home page .
Empirical support for Winnow and
Weighted-Majority based algorithms: results on a calendar scheduling
domain . Machine Learning 26:5--23, 1997. An
earlier version is in Proceedings of the Twelfth International
Conference on Machine Learning, pages 64--72, July 1995. Click here for
more information and source code.
Learning with Unreliable Boundary
Queries . With Prasad Chalasani, Sally Goldman, and
Donna Slonim. Journal of Computer and System
Sciences,56(2):209-222, 1998. Originally appeared in
Proceedings of the Eighth Annual Conference on Computational
Learning Theory (COLT), pages 98---107, July 1995.
New Approximation Guarantees
for Minimum Weight k-Trees and Prize-Collecting Salesmen.
With Baruch Awerbuch, Yossi Azar, and Santosh Vempala. SIAM
J. Computing, 28(1):254--262, 1999. Originally published
in Proceedings of the 27th Annual
ACM Symposium on Theory of Computing, pages 277--283, 1995. A
tech report version appears as CMU-CS-94-173, August, 1994.
A Constant-Factor
Approximation Algorithm for the Geometric k-MST Problem in the
Plane. With J.S.B. Mitchell, Prasad
Chalasani, and
Santosh Vempala. SIAM J. Computing
28(3): 771-781 (1998). This paper
combines two conference papers: J.S.B. Mitchell, "Guillotine
subdivisions approximate polygonal subdivisions: A simple new
method for the geometric k-MST problem", SODA '96,
pp. 402--408, and Blum, Chalasani, and Vempala, "A
constant-factor approximation for the k-MST problem in the
plane", STOC '95, pp. 294--302.
Coloring Random and Semi-Random k-Colorable
Graphs. With Joel Spencer. Journal of Algorithms
19:204--234, 1995.
Relevant Examples and Relevant
Features: Thoughts from Computational Learning Theory .
This is a survey paper presented at the 1994 AAAI Fall Symposium.
Here is a longer article with a broader
perspective, joint with Pat Langley, that appears in
Artificial Intelligence, 97:245--272, 1997.
On learning read-k-satisfy-j DNF.
With Roni Khardon, Eyal Kushilevitz, Leonard Pitt, and Dan Roth.
SIAM J. Computing, 27(6):1515--1530, 1998. Originally
published in Proceedings of the Seventh Annual Conference
on Computational Learning Theory, pages 110--117, July 1994.
The Minimum Latency Problem.
With Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar
Raghavan, and Madhu Sudan. In Proceedings of the 26th Annual ACM
Symposium on Theory of Computing, pages 163--171, 1994.
Weakly Learning DNF and
Characterizing Statistical Query Learning Using Fourier Analysis.
With Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay
Mansour, and Steven Rudich. In Proceedings of the 26th Annual ACM
Symposium on Theory of Computing, pages 253--262, 1994.
Cryptographic Primitives Based on
Hard Learning Problems.
With Merrick Furst, Michael Kearns, and Richard Lipton.
In Advances in Cryptology --- CRYPTO 93, Lecture Notes in
Computer Science #773, pages 278-291, Springer-Verlag, 1994.
Learning an Intersection
of a Constant Number of Halfspaces over a Uniform Distribution.
With Ravi Kannan. Journal of Computer and System Sciences
54(2):371--380, 1997 (JCSS special issue for FOCS '93).
Originally appeared in Proceedings of the 34th Annual IEEE Symposium
on Foundations of Computer Science, pages 312--320,
November 1993. Also published as Chapter 9 in Theoretical
Advances in Neural Computation and Learning ,
Roychowdhury, Siu and Orlitsky, eds. Kluwer, 1994.
An On-Line Algorithm for Improving
Performance in Navigation.
With Prasad Chalasani.
SIAM J. Comput. 29(6): 1907-1938 (2000). Originally
appeared in Proceedings of the
34th Annual IEEE Symposium on Foundations of Computer Science,
pages 2--11, November 1993.
On Learning Embedded Symmetric Concepts.
With Prasad Chalasani and Jeffrey Jackson. In Proceedings of
the Sixth Annual Conference on Computational Learning Theory,
pages 337--346, July 1993.
Generalized Degree Sums and Hamiltonian Graphs. With Ronald Gould. ARS Combinatoria, 35:35--54, 1993.
A Decomposition Theorem and Bounds for Randomized Server
Problems.
With Howard Karloff, Yuval Rabani, and Michael Saks. SIAM J.
Computing, 30(5): 1624--1661, 2000. Originally appeared un
Proceedings of the 33rd Annual IEEE Symposium on Foundations of
Computer Science, pages 197--207, October 1992.
Learning Switching Concepts.
With Prasad Chalasani. In Proceedings of the Fifth Annual
Workshop on Computational Learning Theory, pages 231--242, July 1992.
Fast Learning of k-Term DNF Formulas with Queries.
With Steven Rudich. In Proceedings of the 24th Annual ACM
Symposium on Theory of Computing, pages 382-389, May 1992.
Rank-r Decision Trees are a Subclass of r-Decision Lists.
Information Processing Letters, 42:183--185, 1992.
Learning in the Presence of Finitely or
Infinitely Many Irrelevant Attributes.
With Lisa Hellerstein and Nick Littlestone. JCSS
50(1):32--40, February 1995. An earlier version appears in
Proceedings of the Fourth Annual Workshop on Computational
Learning Theory, pages 157-166, August 1991.
Algorithms for Approximate Graph Coloring.
Ph.D. thesis, MIT Laboratory for Computer Science MIT/LCS/TR-506,
May 1991.
Linear Approximation of Shortest
Superstrings.
With Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis.
JACM 31(4):630--647, 1994.
An earlier version appears in Proceedings of the 23rd Annual
ACM Symposium on Theory of Computing, pages 328-336, May 1991.
Navigating in Unfamiliar Geometric
Terrain.
With Prabhakar Raghavan and Baruch Schieber. Siam J.
Comp 26(1):110-137, February 1997. An earlier version
appears in Proceedings
of the 23rd Annual ACM Symposium on Theory of Computing, pages
494-504, May 1991.
Learning Boolean Functions in an
Infinite Attribute Space.
Machine Learning, 9(4):373--386, 1992. Also in
Proceedings of the 22nd ACM Symposium on Theory of Computing,
pages 64-72, May 1990.
New Approximation
Algorithms for Graph Coloring.
JACM 41(3):470--516, May 1994. An earlier version
appears as "Some Tools for Approximate 3-Coloring", in Proceedings of
the 31st Annual IEEE Symposium on Foundations of Computer
Science, pages 554-562, October 1990.
Separating Distribution-Free and Mistake-Bound Learning Models
over the Boolean Domain.
SIAM J. Computing, Vol 23, No. 5, 1994.
Also in Proceedings of the 31st Annual IEEE Symposium on Foundations of
Computer Science, pages 211-218, October 1990.
Learning Functions of k Terms.
With Mona Singh. In Proceedings of the Third Annual Workshop on
Computational Learning Theory, pages 144-153, August 1990.
On the Computational Complexity of Training Simple Neural
Networks.
Master's thesis, MIT Laboratory for Computer
Science, MIT/LCS/TR-445, May 1989.
An O(n^0.4)-Approximation Algorithm for 3-Coloring (and
Improved Approximation Algorithms for k-Coloring).
In Proceedings of the 21st ACM Symposium on Theory of
Computing, pages 535-542, May 1989.
Training a 3-Node Neural Network is NP-Complete.
With Ron Rivest. Neural Networks, 5(1):117-127, 1992. Also in
Advances in Neural Information Processing Systems 1 (proceedings of
the 1988 NIPS conference), pp. 494-501, 1989.
Last updated: October 2001