| 2006 | Efficient Algorithms for General Active Learning. | Claire Monteleoni |
| 2006 | Mercer's Theorem, Feature Maps, and Smoothing. | Ha Quang Minh, Partha Niyogi, Yuan Yao |
| 2006 | The Rademacher Complexity of Linear Transformation Classes. | Andreas Maurer |
| 2006 | Online Learning with Constraints. | Shie Mannor, John N. Tsitsiklis |
| 2006 | Online Learning with Variable Stage Duration. | Shie Mannor, Nahum Shimkin |
| 2006 | Discriminative Learning Can Succeed Where Generative Learning Fails. | Philip M. Long, Rocco A. Servedio |
| 2006 | Improving Random Projections Using Marginal Information. | Ping Li, Trevor Hastie, Kenneth Ward Church |
| 2006 | DNF Are Teachable in the Average Case. | Homin K. Lee, Rocco A. Servedio, Andrew Wan |
| 2006 | Optimal Oracle Inequality for Aggregation of Classifiers Under Low Noise Condition. | Guillaume Lecu |
| 2006 | Parent Assignment Is Hard for the MDL, AIC, and NML Costs. | Mikko Koivisto |
| 2006 | Improved Lower Bounds for Learning Intersections of Halfspaces. | Adam R. Klivans, Alexander A. Sherstov |
| 2006 | On Learning Languages from Positive Data and a Limited Number of Short Counterexamples. | Sanjay Jain, Efim B. Kinber |
| 2006 | Uniform-Distribution Learnability of Noisy Linear Threshold Functions with Restricted Focus of Attention. | Jeffrey C. Jackson |
| 2006 | Uniform Convergence of Adaptive Graph-Based Regularization. | Matthias Hein |
| 2006 | Logarithmic Regret Algorithms for Online Convex Optimization. | Elad Hazan, Adam Kalai, Satyen Kale, Amit Agarwal |
| 2006 | The Shortest Path Problem Under Partial Monitoring. | Andrs Gyrgy, Tams Linder, Gyrgy Ottucsk |
| 2006 | Functional Classification with Margin Conditions. | Magalie Fromont, Christine Tuleau |
| 2006 | Efficient Learning Algorithms Yield Circuit Lower Bounds. | Lance Fortnow, Adam R. Klivans |
| 2006 | Active Sampling for Multiple Output Identification. | Shai Fine, Yishay Mansour |
| 2006 | PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption. | Jon Feldman, Rocco A. Servedio, Ryan O'Donnell |
| 2006 | Stable Transductive Learning. | Ran El-Yaniv, Dmitry Pechyony |
| 2006 | Maximum Entropy Distribution Estimation with Generalized Regularization. | Miroslav Dudk, Robert E. Schapire |
| 2006 | Random Multivariate Search Trees. | Luc Devroye |
| 2006 | Learning Rational Stochastic Languages. | Franois Denis, Yann Esposito, Amaury Habrard |
| 2006 | Online Multitask Learning. | Ofer Dekel, Philip M. Long, Yoram Singer |