| 2026 | AAAI | A Theoretical Model for Grit in Pursuing Ambitious Ends. | Avrim Blum, Emily Diana, Kavya Ravichandran, Alexander Williams Tolbert |
| 2025 | AISTATS | Distributional Adversarial Loss. | Saba Ahmadi, Siddharth Bhandari, Avrim Blum, Chen Dan, Prabhav Jain |
| 2025 | ALT | Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem. | Avrim Blum, Kavya Ravichandran |
| 2025 | ALT | A Model for Combinatorial Dictionary Learning and Inference. | Avrim Blum, Kavya Ravichandran |
| 2025 | COLT | Proofs as Explanations: Short Certificates for Reliable Predictions. | Avrim Blum, Steve Hanneke, Chirag Pabbaraju, Donya Saless |
| 2025 | ICML | PAC Learning with Improvements. | Idan Attias, Avrim Blum, Keziah Naggita, Donya Saless, Dravyansh Sharma, Matthew R. Walter |
| 2025 | SODA | Competitive strategies to use "warm start" algorithms with predictions. | Avrim Blum, Vaidehi Srinivas |
| 2024 | AISTATS | Agnostic Multi-Robust Learning using ERM. | Saba Ahmadi, Avrim Blum, Omar Montasser, Kevin M. Stangl |
| 2024 | AISTATS | On the Vulnerability of Fairness Constrained Learning to Malicious Noise. | Avrim Blum, Princewill Okoroafor, Aadirupa Saha, Kevin M. Stangl |
| 2024 | ALT | Dueling Optimization with a Monotone Adversary. | Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, Yuanyuan Yang |
| 2022 | COLT | Robustly-reliable learners under poisoning attacks. | Maria-Florina Balcan, Avrim Blum, Steve Hanneke, Dravyansh Sharma |
| 2022 | SODA | Stochastic Vertex Cover with Few Queries. | Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan |
| 2021 | AAAI | Communication-Aware Collaborative Learning. | Avrim Blum, Shelby Heinecke, Lev Reyzin |
| 2021 | AISTATS | Learning Complexity of Simulated Annealing. | Avrim Blum, Chen Dan, Saeed Seddighin |
| 2021 | COLT | Robust learning under clean-label attack. | Avrim Blum, Steve Hanneke, Jian Qian, Han Shao |
| 2021 | ICML | One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning. | Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, Han Shao |
| 2020 | COLT | Active Local Learning. | Arturs Backurs, Avrim Blum, Neha Gupta |
| 2019 | EC | Optimal Strategies of Blotto Games: Beyond Convexity. | Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin |
| 2019 | ESA | Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem. | Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan |
| 2019 | SAGT | Computing Stackelberg Equilibria of Large General-Sum Games. | Avrim Blum, Nika Haghtalab, MohammadTaghi Hajiaghayi, Saeed Seddighin |
| 2018 | AAAI | Algorithms for Generalized Topic Modeling. | Avrim Blum, Nika Haghtalab |
| 2018 | COLT | Active Tolerant Testing. | Avrim Blum, Lunjia Hu |
| 2018 | ICALP | Approximate Convex Hull of Data Streams. | Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, Lin F. Yang |
| 2018 | SODA | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. | Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark |
| 2017 | ALT | Lifelong Learning in Costly Feature Spaces. | Maria-Florina Balcan, Avrim Blum, Vaishnavh Nagarajan |
| 2017 | COLT | Efficient PAC Learning from the Crowd. | Pranjal Awasthi, Avrim Blum, Nika Haghtalab, Yishay Mansour |
| 2017 | COLT | Efficient Co-Training of Linear Separators under Weak Dependence. | Avrim Blum, Yishay Mansour |
| 2017 | SODA | Opting Into Optimal Matchings. | Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel D. Procaccia, Eviatar B. Procaccia, Rohit Vaish |
| 2016 | SODA | Sparse Approximation via Generating Point Sets. | Avrim Blum, Sariel Har-Peled, Benjamin Raichel |
| 2015 | AAAI | Learning Valuation Distributions from Partial Observation. | Avrim Blum, Yishay Mansour, Jamie Morgenstern |
| 2015 | COLT | Efficient Representations for Lifelong Learning and Autoencoding. | Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |
| 2015 | ICML | The Ladder: A Reliable Leaderboard for Machine Learning Competitions. | Avrim Blum, Moritz Hardt |
| 2014 | AAAI | Lazy Defenders Are Almost Optimal against Diligent Attackers. | Avrim Blum, Nika Haghtalab, Ariel D. Procaccia |
| 2014 | UAI | Estimating Accuracy from Unlabeled Data. | Emmanouil Antonios Platanios, Avrim Blum, Tom M. Mitchell |
| 2013 | ICML | Exploiting Ontology Structures and Unlabeled Data for Learning. | Nina Balcan, Avrim Blum, Yishay Mansour |
| 2012 | FOCS | Active Property Testing. | Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang |
| 2012 | FOCS | The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy. | Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet |
| 2011 | FOCS | Welfare and Profit Maximization with Production Costs. | Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma |
| 2010 | COLT | Improved Guarantees for Agnostic Learning of Disjunctions. | Pranjal Awasthi, Avrim Blum, Or Sheffet |
| 2010 | FOCS | Stability Yields a PTAS for k-Median and k-Means Clustering. | Pranjal Awasthi, Avrim Blum, Or Sheffet |
| 2010 | SAGT | On Nash-Equilibria of Approximation-Stable Games. | Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, Santosh S. Vempala |
| 2009 | SODA | Approximate clustering without the approximation. | Maria-Florina Balcan, Avrim Blum, Anupam Gupta |
| 2009 | SODA | Improved equilibria via public service advertising. | Maria-Florina Balcan, Avrim Blum, Yishay Mansour |
| 2008 | ALT | Clustering with Interactive Feedback. | Maria-Florina Balcan, Avrim Blum |
| 2008 | COLT | Improved Guarantees for Learning via Similarity Functions. | Maria-Florina Balcan, Avrim Blum, Nathan Srebro |
| 2008 | ICTAI | Veritas: Combining Expert Opinions without Labeled Data. | Sharath R. Cholleti, Sally A. Goldman, Avrim Blum, David G. Politte, Steven Don |
| 2008 | NDSS | Limits of Learning-based Signature Generation with Adversaries. | Shobha Venkataraman, Avrim Blum, Dawn Song |
| 2008 | STOC | A discriminative framework for clustering via similarity functions. | Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |
| 2008 | STOC | Regret minimization and the price of total anarchy. | Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, Aaron Roth |
| 2008 | STOC | A learning theory approach to non-interactive database privacy. | Avrim Blum, Katrina Ligett, Aaron Roth |
| 2007 | ALT | A Theory of Similarity Functions for Learning and Clustering. | Avrim Blum |
| 2007 | COLT | Open Problems in Efficient Semi-supervised PAC Learning. | Avrim Blum, Maria-Florina Balcan |
| 2007 | DIS | A Theory of Similarity Functions for Learning and Clustering. | Avrim Blum |
| 2007 | ISAAC | Separating Populations with Wide Data: A Spectral Analysis. | Avrim Blum, Amin Coja-Oghlan, Alan M. Frieze, Shuheng Zhou |
| 2006 | HOTNETS | Black Box Anomaly Detection: Is It Utopian?. | Shobha Venkataraman, Juan Caballero, Dawn Song, Avrim Blum, Jennifer Yates |
| 2006 | ICML | On a theory of learning with similarity functions. | Maria-Florina Balcan, Avrim Blum |
| 2006 | PODC | Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games. | Avrim Blum, Eyal Even-Dar, Katrina Ligett |
| 2005 | COLT | A PAC-Style Model for Learning from Labeled and Unlabeled Data. | Maria-Florina Balcan, Avrim Blum |
| 2005 | COLT | From External to Internal Regret. | Avrim Blum, Yishay Mansour |
| 2005 | FOCS | Mechanism Design via Machine Learning. | Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour |
| 2005 | NDSS | New Streaming Algorithms for Fast Detection of Superspreaders. | Shobha Venkataraman, Dawn Xiaodong Song, Phillip B. Gibbons, Avrim Blum |
| 2005 | PODS | Practical privacy: the SuLQ framework. | Avrim Blum, Cynthia Dwork, Frank McSherry, Kobbi Nissim |
| 2005 | SODA | Near-optimal online auctions. | Avrim Blum, Jason D. Hartline |
| 2004 | ALT | On Kernels, Margins, and Low-Dimensional Mappings. | Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |
| 2004 | COLT | Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. | H. Brendan McMahan, Avrim Blum |
| 2004 | ICML | Semi-supervised learning using randomized mincuts. | Avrim Blum, John D. Lafferty, Mugizi Robert Rwebangira, Rajashekar Reddy |
| 2004 | RAID | Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds. | Avrim Blum, Dawn Xiaodong Song, Shobha Venkataraman |
| 2004 | STOC | Approximation algorithms for deadline-TSP and vehicle routing with time-windows. | Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson |
| 2003 | COLT | Learning a Function of r Relevant Variables. | Avrim Blum |
| 2003 | COLT | Preference Elicitation and Query Learning. | Avrim Blum, Jeffrey C. Jackson, Tuomas Sandholm, Martin Zinkevich |
| 2003 | COLT | PAC-MDL Bounds. | Avrim Blum, John Langford |
| 2003 | ESA | Scheduling for Flow-Time with Admission Control. | Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere |
| 2003 | FOCS | Machine Learning: My Favorite Results, Directions, and Open Problems. | Avrim Blum |
| 2003 | FOCS | Approximation Algorithms for Orienteering and Discounted-Reward TSP. | Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff |
| 2003 | ICML | Planning in the Presence of Cost Functions Controlled by an Adversary. | H. Brendan McMahan, Geoffrey J. Gordon, Avrim Blum |
| 2003 | SODA | Online learning in online auctions. | Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu |
| 2003 | SPAA | Combining online algorithms for rejection and acceptance. | Yossi Azar, Avrim Blum, Yishay Mansour |
| 2003 | SPAA | Online oblivious routing. | Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson |
| 2002 | FOCS | Correlation Clustering. | Nikhil Bansal, Avrim Blum, Shuchi Chawla |
| 2002 | SODA | Static optimality and dynamic search-optimality in lists and trees. | Avrim Blum, Shuchi Chawla, Adam Kalai |
| 2002 | SODA | Smoothed analysis of the perceptron algorithm for linear programming. | Avrim Blum, John Dunagan |
| 2002 | SODA | Online algorithms for market clearing. | Avrim Blum, Tuomas Sandholm, Martin Zinkevich |
| 2001 | ICML | Learning from Labeled and Unlabeled Data using Graph Mincuts. | Avrim Blum, Shuchi Chawla |
| 2001 | WADS | Admission Control to Minimize Rejections. | Avrim Blum, Adam Kalai, Jon M. Kleinberg |
| 2000 | ICML | FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness. | Joseph O'Sullivan, John Langford, Rich Caruana, Avrim Blum |
| 2000 | STOC | Noise-tolerant learning, the parity problem, and the statistical query model. | Avrim Blum, Adam Kalai, Hal Wasserman |
| 1999 | COLT | Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation. | Avrim Blum, Adam Kalai, John Langford |
| 1999 | COLT | Microchoice Bounds and Self Bounding Learning Algorithms. | John Langford, Avrim Blum |
| 1999 | FOCS | Finely-Competitive Paging. | Avrim Blum, Carl Burch, Adam Kalai |
| 1999 | ICASSP | On-line algorithms for combining language models. | Adam Kalai, Stanley F. Chen, Avrim Blum, Ronald Rosenfeld |
| 1998 | COLT | Combining Labeled and Unlabeled Data with Co-Training. | Avrim Blum, Tom M. Mitchell |
| 1998 | FOCS | On Learning Monotone Boolean Functions. | Avrim Blum, Carl Burch, John Langford |
| 1998 | STOC | Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. | Avrim Blum, Goran Konjevod, R. Ravi, Santosh S. Vempala |
| 1997 | COLT | On-line Learning and the Metrical Task System Problem. | Avrim Blum, Carl Burch |
| 1997 | COLT | Universal Portfolios With and Without Transaction Costs. | Avrim Blum, Adam Kalai |
| 1997 | STOC | A polylog( | Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins |
| 1996 | FOCS | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. | Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala |
| 1996 | SODA | Randomized Robot Navigation Algorithms. | Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosn, Michael E. Saks |
| 1996 | STOC | A Constant-factor Approximation Algorithm for the | Avrim Blum, R. Ravi, Santosh S. Vempala |
| 1995 | COLT | Learning with Unreliable Boundary Queries. | Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim |
| 1995 | ICML | Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain. | Avrim Blum |
| 1995 | IJCAI | Fast Planning Through Planning Graph Analysis. | Avrim Blum, Merrick L. Furst |
| 1995 | STOC | Improved approximation guarantees for minimum-weight | Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala |
| 1995 | STOC | A constant-factor approximation for the | Avrim Blum, Prasad Chalasani, Santosh S. Vempala |
| 1994 | COLT | On Learning Read- | Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth |
| 1994 | STOC | The minimum latency problem. | Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan |
| 1994 | STOC | Weakly learning DNF and characterizing statistical query learning using Fourier analysis. | Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich |
| 1993 | COLT | On Learning Embedded Symmetric Concepts. | Avrim Blum, Prasad Chalasani, Jeffrey C. Jackson |
| 1993 | CRYPTO | Cryptographic Primitives Based on Hard Learning Problems. | Avrim Blum, Merrick L. Furst, Michael J. Kearns, Richard J. Lipton |
| 1993 | FOCS | An On-Line Algorithm for Improving Performance in Navigation | Avrim Blum, Prasad Chalasani |
| 1993 | FOCS | Learning an Intersection of k Halfspaces over a Uniform Distribution | Avrim Blum, Ravi Kannan |
| 1992 | COLT | Learning Switching Concepts. | Avrim Blum, Prasad Chalasani |
| 1992 | FOCS | A Decomposition Theorem and Bounds for Randomized Server Problems | Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks |
| 1992 | STOC | Fast Learning of k-Term DNF Formulas with Queries | Avrim Blum, Steven Rudich |
| 1991 | COLT | Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. | Avrim Blum, Lisa Hellerstein, Nick Littlestone |
| 1991 | STOC | Linear Approximation of Shortest Superstrings | Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis |
| 1991 | STOC | Navigating in Unfamiliar Geometric Terrain (Preliminary Version) | Avrim Blum, Prabhakar Raghavan, Baruch Schieber |
| 1990 | COLT | Separating PAC and Mistake-Bound Learning Models Over the Boolean Domain (Abstract). | Avrim Blum |
| 1990 | COLT | Learning Functions of | Avrim Blum, Mona Singh |
| 1990 | FOCS | Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain | Avrim Blum |
| 1990 | FOCS | Some Tools for Approximate 3-Coloring (Extended Abstract) | Avrim Blum |
| 1990 | STOC | Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract) | Avrim Blum |
| 1989 | STOC | An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring) | Avrim Blum |
| 1988 | COLT | Training a 3-Node Neural Network is NP-Complete. | Avrim Blum, Ronald L. Rivest |