All accepted papers are available online here. Accepted Papers Exact = PExact (Pexact = Exact Learning) Dmitry Gavinsky, Avi Owshanko A new PAC-bound for intersection-closed concept classes Peter Auer, Ronald Ortner Toward Attribute Efficient Learning of Decision Lists and Parities Adam Klivans, Rocco Servedio Polynomial time Prediction Strategy with almost Optimal Mistake Probability Nader Bshouty Minimizing Regret with Label Efficient Prediction Nicolo Cesa-Bianchi, Gabor Lugosi, Gilles Stoltz An Improved VC Dimension Bound for Sparse Polynomials Michael Schmitt Model selection by bootstrap penalization for classification Magalie FROMONT Consistency in Models for Communication Constrained Distributed Learning Joel Predd, Sanjeev Kulkarni, H. Vincent Poor Concentration Bounds for Unigrams Language Model Evgeny Drukh, Yishay Mansour Towards a Characterization of Polynomial Preference Elicitation with Value Queries in Combinatorial Auctions Paolo Santi, Vincent Conitzer, Tuomas Sandholm Learning a Hidden Graph Using O(log n) Queries per Edge Dana Angluin, Jiang Chen Convergence of Discrete MDL for Sequential Prediction Jan Poland, Marcus Hutter Regularization and Semisupervised Learning on Large Graphs Mikhail Belkin, Irina Matveeva, Partha Niyogi Learning Intersections of Halfspaces with a Margin Adam Klivans, Rocco Servedio Replacing limit learners with equally powerful one-shot query learners Steffen Lange, Sandra Zilles Bayes and Tukey Meet at the Center Point Ran Gilad-Bachrach, Amir Navot, Naftali Tishby On the learnability of E-pattern languages over small alphabets Daniel Reidenbach A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra Magnus Rattray Boosting Based on a Smooth Margin Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies On the Convergence of MDL Density Estimation Tong Zhang Learning over Compact Metric Spaces Minh Ha Quang Inferring Mixtures of Markov Chains Tugkan Batu, Sudipto Guha, Sampath Kannan Reinforcement Learning for Average Reward Zero-Sum Games Shie Mannor A function representation for learning in Banach spaces Massimiliano Pontil, Charles Micchelli Data Dependent Risk Bounds For Hierarchical Mixture of Experts Classifiers Arik Azran, Ron Meir Oracle bounds and exact algorithm for dyadic classification trees Gilles Blanchard, Christin Schafer, Yves Rozenholc A General Convergence Theorem for the Decomposition Method Hans Simon, Niko List Graphical Economics Sham Kakade, Michael Kearns, Luis Ortiz Towards convergence of spectral clustering on random samples Ulrike von Luxburg, Olivier Bousquet, Mikhail Belkin Learning classes of Probabilistic Automata Francois DENIS, Yann ESPOSITO Bayesian Networks and Inner Product Spaces Hans Simon, Atsuyoshi Nakamura, Michael Schmitt, Niels Schmitt Statistical Properties of Kernel Principal Component Analysis Laurent Zwald, Olivier Bousquet, Gilles Blanchard Regret Bounds for Hierarchical Classification with Linear-Threshold Functions Nicolo Cesa-Bianchi, Alex Conconi, claudio gentile An Inequality for Nearly Log-concave Distributions with Applications to Learning Constantine Caramanis, Shie Mannor Kernelizing Sorting: Permutation and Alignment for Kernel PCA Tony Jebara Suboptimal Behavior of Bayes and MDL in Classification under Misspecification Peter Grunwald, John Langford Local Complexities for Empirical Risk Minimization Peter Bartlett, Shahar Mendelson, Petra Philips Sparseness vs Estimating Conditional Probabilities: Some Asymptotic Results Peter Bartlett, Ambuj Tewari On the Power of Learning Decision Graphs Adam Kalai Deterministic Calibration and Nash Equilibrium Sham Kakade, Dean Foster Performance Guarantees for Regularized Maximum Entropy Density Estimation Miroslav Dudik, Steven J. Phillips, Robert E. Schapire Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary H. Brendan McMahan, Avrim Blum A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering Shai Ben-david