Avrim Blum | Academic Influence

Avrim Blum's AcademicInfluence.com Rankings

Avrim Blum

Computer Science

#324

World Rank

#337

Historical Rank

#184

USA Rank

Machine Learning

#69

World Rank

#69

Historical Rank

#26

USA Rank

Database

#436

World Rank

#458

Historical Rank

#183

USA Rank

computer-science Degrees

Download Badge

Computer Science

Avrim Blum's Degrees

PhD Computer Science University of California, Berkeley

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Avrim Blum Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Avrim Blum is a computer scientist. In 2007, he was made a Fellow of the Association for Computing Machinery "for contributions to learning theory and algorithms." Blum attended MIT, where he received his Ph.D. in 1991 under professor Ron Rivest. He was a professor of computer science at Carnegie Mellon University from 1991 to 2017.

(See a Problem?)

Avrim Blum's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Combining labeled and unlabeled data with co-training (1998) (5784)
Selection of Relevant Features and Examples in Machine Learning (1997) (3428)
Fast Planning Through Planning Graph Analysis (1995) (2303)
Learning from Labeled and Unlabeled Data using Graph Mincuts (2001) (1095)
Training a 3-node neural network is NP-complete (1988) (951)
Practical privacy: the SuLQ framework (2005) (880)
Noise-tolerant learning, the parity problem, and the statistical query model (2000) (651)
A learning theory approach to non-interactive database privacy (2008) (537)
Correlation Clustering (2002) (400)
The minimum latency problem (1994) (340)
Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges (2007) (334)
A learning theory approach to noninteractive database privacy (2011) (322)
Cryptographic Primitives Based on Hard Learning Problems (1993) (315)
Beating the hold-out: bounds for K-fold and progressive cross-validation (1999) (314)
From External to Internal Regret (2005) (312)
Co-Training and Expansion: Towards Bridging Theory and Practice (2004) (311)
Planning in the Presence of Cost Functions Controlled by an Adversary (2003) (290)
Semi-supervised learning using randomized mincuts (2004) (282)
Approximation algorithms for orienteering and discounted-reward TSP (2003) (280)
Weakly learning DNF and characterizing statistical query learning using Fourier analysis (1994) (279)
On-line Algorithms in Machine Learning (1996) (249)
Foundations of Data Science (2020) (237)
Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds (2004) (231)
New Streaming Algorithms for Fast Detection of Superspreaders (2005) (221)
Approximation algorithms for deadline-TSP and vehicle routing with time-windows (2004) (219)
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions (1996) (213)
Navigating in unfamiliar geometric terrain (1991) (207)
Universal Portfolios With and Without Transaction Costs (1997) (205)
Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain (2004) (202)
Online learning in online auctions (2003) (201)
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary (2004) (199)
Distributed Learning, Communication Complexity and Privacy (2012) (191)
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012) (180)
A discriminative framework for clustering via similarity functions (2008) (176)
Differentially private data analysis of social networks via restricted sensitivity (2012) (174)
Regret minimization and the price of total anarchy (2008) (169)
Coloring Random and Semi-Random k-Colorable Graphs (1995) (166)
Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games (2006) (163)
Probabilistic Planning in the Graphplan Framework (1999) (155)
Linear approximation of shortest superstrings (1991) (155)
On a theory of learning with similarity functions (2006) (154)
Kernels as features: On kernels, margins, and low-dimensional mappings (2006) (145)
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1999) (144)
Approximate clustering without the approximation (2009) (144)
Near-optimal online auctions (2005) (134)
Approximation algorithms and online mechanisms for item pricing (2006) (134)
Random Projection, Margins, Kernels, and Feature-Selection (2005) (131)
A discriminative model for semi-supervised learning (2010) (129)
An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs (1997) (128)
Center-based clustering under perturbation stability (2010) (125)
Mechanism design via machine learning (2005) (125)
Algorithmic Game Theory: Learning, Regret Minimization, and Equilibria (2007) (122)
The Ladder: A Reliable Leaderboard for Machine Learning Competitions (2015) (120)
Online algorithms for market clearing (2002) (120)
A PAC-Style Model for Learning from Labeled and Unlabeled Data (2005) (117)
New approximation algorithms for graph coloring (1994) (113)
On-line Learning and the Metrical Task System Problem (1997) (112)
Item pricing for revenue maximization (2008) (110)
Preference Elicitation and Query Learning (2004) (109)
A Note on Learning from Multiple-Instance Examples (2004) (106)
Learning in the presence of finitely or infinitely many irrelevant attributes (1991) (101)
Person Identification in Webcam Images: An Application of Semi-Supervised Learning (2005) (100)
A polylog(n)-competitive algorithm for metrical task systems (1997) (99)
Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain (1995) (97)
Commitment Without Regrets: Online Learning in Stackelberg Security Games (2015) (96)
Learning Optimal Commitment to Overcome Insecurity (2014) (93)
Clustering with Interactive Feedback (2008) (92)
Stability Yields a PTAS for k-Median and k-Means Clustering (2010) (91)
Linear approximation of shortest superstrings (1994) (89)
Reducing mechanism design to algorithm design via machine learning (2007) (88)
A theory of learning with similarity functions (2008) (87)
Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen (1995) (87)
A Constant-Factor Approximation Algorithm for the k-MST Problem (1999) (83)
Learning boolean functions in an infinite attribute space (1990) (82)
Fast learning of k-term DNF formulas with queries (1992) (79)
Clustering under approximation stability (2013) (77)
Smoothed analysis of the perceptron algorithm for linear programming (2002) (75)
Separating distribution-free and mistake-bound learning models over the Boolean domain (1990) (75)
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems (1998) (70)
Efficient Representations for Lifelong Learning and Autoencoding (2014) (67)
Improved Guarantees for Learning via Similarity Functions (2008) (66)
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries (2014) (65)
A Random-Surfer Web-Graph Model (2006) (65)
PAC-MDL Bounds (2003) (65)
Rank-r Decision Trees are a Subclass of r-Decision Lists (1992) (64)
Estimating Accuracy from Unlabeled Data (2014) (62)
Static Optimality and Dynamic Search-Optimality in Lists and Trees (2002) (61)
Active Property Testing (2011) (61)
Limits of Learning-based Signature Generation with Adversaries (2008) (61)
On polynomial-time preference elicitation with value queries (2003) (59)
Recovering from Biased Data: Can Fairness Constraints Improve Accuracy? (2019) (59)
Learning Mixtures of Ranking Models (2014) (58)
Finely-competitive paging (1999) (57)
Relevant Examples and Relevant Features: Thoughts from Computational Learning Theory (1994) (56)
Randomized robot navigation algorithms (1996) (55)
A constant-factor approximation for the k-MST problem in the plane (1995) (54)
Random Smoothing Might be Unable to Certify 𝓁∞ Robustness for High-Dimensional Images (2020) (53)
On learning monotone Boolean functions (1998) (53)
Improved equilibria via public service advertising (2009) (53)
FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness (2000) (53)
Welfare and Profit Maximization with Production Costs (2011) (52)
Some tools for approximate 3-coloring (1990) (46)
Learning a Function of r Relevant Variables (2003) (45)
On learning Read-k-Satisfy-j DNF (1994) (39)
Item pricing for revenue maximization (2008) (39)
A decomposition theorem and bounds for randomized server problems (1992) (39)
Learning with unreliable boundary queries (1995) (38)
Online oblivious routing (2003) (38)
Quantitatively tight sample complexity bounds (2002) (38)
Learning functions of k terms (1990) (38)
The Price of Uncertainty (2009) (37)
Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution (1997) (37)
Learning an intersection of k halfspaces over a uniform distribution (1993) (36)
Harnessing the power of two crossmatches (2013) (36)
Noise-tolerant learning, the parity problem, and the statistical query model (2000) (36)
A constant-factor approximation algorithm for the k MST problem (extended abstract) (1996) (35)
ALGORITHMS FOR APPROXIMATE GRAPH COLORING (1991) (35)
An on-line algorithm for improving performance in navigation (1993) (34)
Collaborative PAC Learning (2017) (34)
Exploiting Ontology Structures and Unlabeled Data for Learning (2013) (33)
4 Learning , Regret minimization , and Equilibria (2006) (33)
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior (2013) (33)
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems (2000) (31)
Microchoice Bounds and Self Bounding Learning Algorithms (1999) (31)
Sparse Approximation via Generating Point Sets (2015) (29)
On Kernels, Margins, and Low-Dimensional Mappings (2004) (29)
On preserving non-discrimination when combining expert advice (2018) (28)
Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract) (1990) (28)
Veritas: Combining Expert Opinions without Labeled Data (2008) (27)
Advancing subgroup fairness via sleeping experts (2019) (26)
Trading off Mistakes and Don't-Know Predictions (2010) (25)
Learning switching concepts (1992) (25)
An O(n0.4)-approximation algorithm for 3-coloring (1989) (23)
On-line algorithms for combining language models (1999) (23)
Algorithms for flow time scheduling (2003) (22)
Scheduling for Flow-Time with Admission Control (2003) (22)
Lazy Defenders Are Almost Optimal against Diligent Attackers (2014) (22)
The Strategic Perceptron (2020) (21)
On learning embedded symmetric concepts (1993) (20)
Admission Control to Minimize Rejections (2001) (20)
Theoretical guarantees for algorithms in multi-agent settings (2004) (19)
A Theory of Loss-Leaders: Making Money by Pricing Below Cost (2007) (19)
Improved Guarantees for Agnostic Learning of Disjunctions (2010) (17)
Opting Into Optimal Matchings (2016) (17)
Efficient PAC Learning from the Crowd (2017) (17)
Single Price Mechanisms for Revenue Maximization in Unlimited Supply Combinatorial Auctions (2006) (17)
An Augmented PAC Model for Semi-Supervised Learning (2006) (17)
From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games (2018) (17)
Fast Private Data Release Algorithms for Sparse Queries (2011) (17)
Optimal Strategies of Blotto Games: Beyond Convexity (2019) (16)
One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning (2021) (16)
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane (1999) (15)
Random Smoothing Might be Unable to Certify $\ell_\infty$ Robustness for High-Dimensional Images (2020) (15)
Learning Boolean Functions in an Infinite Attribute Space (1992) (15)
Learning Valuation Distributions from Partial Observation (2014) (15)
Machine learning: my favorite results, directions, and open problems (2003) (13)
Learning valuation distributions from partial observations (2015) (13)
Active Tolerant Testing (2017) (13)
Black Box Anomaly Detection: Is It Utopian? (2006) (13)
Tracking Dynamic Sources of Malicious Activity at Internet Scale (2009) (13)
On Nash-Equilibria of Approximation-Stable Games (2010) (12)
Excess Capacity and Backdoor Poisoning (2021) (12)
Privacy-Preserving Public Information for Sequential Games (2014) (12)
Learning Complexity of Simulated Annealing (2020) (12)
Robust planning in domains with stochastic outcomes, adversaries, and partial observability (2006) (11)
New theoretical frameworks for machine learning (2008) (11)
Clustering via Similarity Functions : Theoretical Foundations and Algorithms ∗ (2008) (9)
Separating PAC and mistake-bound learning models over the Boolean domain (abstract) (1990) (9)
On the Power of Abstention and Data-Driven Decision Making for Adversarial Robustness (2020) (9)
Computing Stackelberg Equilibria of Large General-Sum Games (2019) (8)
Graph algorithms for planning and partitioning (2005) (7)
Combining online algorithms for rejection and acceptance (2003) (7)
Robust learning under clean-label attack (2021) (7)
Bilu-Linial stability, certified algorithms and the Independent Set problem (2018) (7)
Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions (2014) (7)
Thoughts on clustering ∗ (2009) (7)
Machine Learning Theory (2007) (6)
Probabilistic and on-line methods in machine learning (2001) (6)
Approximate Convex Hull of Data Streams (2017) (6)
The On-Line Search (1985) (6)
Separating Populations with Wide Data: A Spectral Analysis (2007) (6)
Learnability of DNF with representation-specific queries (2013) (6)
Active Learning and Best-Response Dynamics (2014) (5)
Open Problems in Efficient Semi-supervised PAC Learning (2007) (5)
Learning to Play Stackelberg Security Games (2015) (5)
The price of uncertainty (2009) (5)
Diversified Strategies for Mitigating Adversarial Attacks in Multiagent Systems (2018) (5)
Efficient Co-Training of Linear Separators under Weak Dependence (2017) (5)
Incentive-Compatible Kidney Exchange in a Slightly Semi-Random Model (2021) (5)
Machine learning in metrical task systems and other on-line problems (2000) (5)
On classification of strategic agents who can both game and improve (2022) (5)
On the Computational Hardness of Manipulating Pairwise Voting Rules (2016) (4)
Regret Minimization , and Equilibria (4)
Combining Online Algorithms for Acceptance and Rejection (2005) (4)
21 An Augmented PAC Model for Semi-Supervised Learning (2005) (4)
The Computational Worldview and the Sciences : a Report on Two Workshops (2007) (4)
Clustering Under Natural Stability Assumptions (2010) (4)
Approximation Algorithms for Item Pricing (2005) (4)
Robustly-reliable learners under poisoning attacks (2022) (4)
A Theory of Similarity Functions for Clustering (2007) (4)
Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline (2022) (3)
Active Testing (2011) (3)
Technical perspective: Algorithm selection as a learning problem (2020) (3)
Mechanism design, machine learning, and pricing problems (2007) (3)
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring) (1989) (3)
Additive Approximation for Near-Perfect Phylogeny Construction (2012) (3)
On statistical query sampling and NMR quantum computing (2003) (3)
Stochastic Vertex Cover with Few Queries (2021) (3)
Sponsored Search Auction Design via Machine Learning (2008) (3)
Techniques for exploiting unlabeled data (2008) (3)
An algorithm for 3-colorable graphs (1997) (2)
Preference Elicitation and Allocation with Read-Once Preferences (2002) (2)
Active Local Learning (2020) (2)
Kidney exchange and endless paths: On the optimal use of an altruistic donor (2020) (2)
A Theory of PAC Learnability under Transformation Invariances (2022) (2)
Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness (2022) (2)
TTIC 31250 : An Introduction to the Theory of Machine Learning (2018) (1)
Generalized Topic Modeling (2016) (1)
On Price versus Quality (2018) (1)
A Theory of Similarity Functions for Learning and Clustering (2007) (1)
A Learning Theoretic Framework for Clustering with Similarity Functions (2007) (1)
Semi-supervised Learning (2016) (1)
Map Learning and Coverage Planning for Robots in Large Unknown Environments (2014) (1)
Random Walks and Markov Chains (2020) (1)
Communication-Aware Collaborative Learning (2020) (1)
10-806 Foundations of Machine Learning and Data Science (2015) (1)
Mathematical Foundations for Understanding and Designing Conceptualizing Strategizing Control ( CONSCS ) Systems (2004) (1)
Lifelong Learning in Costly Feature Spaces (2017) (1)
Best-Fit Subspaces and Singular Value Decomposition (SVD) (2020) (1)
Some Tools for Approximate 3-Coloring (Extended Abstract) (1990) (1)
Online Allocation and Pricing with Economies of Scale (2015) (1)
Navigating in Unfamiliar Geometric Terrain (Preliminary Version) (1991) (1)
Online Learning with Primary and Secondary Losses (2020) (0)
1 0 Ju l 2 01 4 Learning Valuation Distributions from Partial Observation (2015) (0)
A Note on Learning from Multiple Instance (2010) (0)
Introduction to the special issue on COLT 2006 (2007) (0)
Algorithms for Massive Data Problems: Streaming, Sketching, and Sampling (2020) (0)
Algorithms for Generalized Topic Modeling (2018) (0)
Special Issue on New Theoretical Challenges in Machine Learning (2014) (0)
Fundamental Bounds on Online Strategic Classification (2023) (0)
Efficient PAC Learning from the Crowd Pranjal Awasthi (2017) (0)
Why Do We Want a Good Ratio Anyway? Approximation Stability and Proxy Objectives (2011) (0)
An Analysis of Robustness of Non-Lipschitz Networks (2020) (0)
Proceedings of the Ninth Annual Conference on Computational Learning Theory, COLT 1996, Desenzano del Garda, Italy, June 28-July 1, 1996 (1996) (0)
Navigating in Unfamiliar Geometric Terrain (Extended Summary) (1991) (0)
Certifiable (Multi)Robustness Against Patch Attacks Using ERM (2023) (0)
Setting Fair Incentives to Maximize Improvement (2022) (0)
Approximation Stability and Proxy Objectives (2020) (0)
Aleksandr Kazachkov 1 Readings for today ’ s lecture (2013) (0)
Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback (2023) (0)
Why Do We Want a Good Ratio Anyway ? Approximation Stability and Proxy Objectives Scribe : Avrim (2011) (0)
Special Issue on New Theoretical Challenges in Machine Learning (2015) (0)
Learning What’s Going on (2018) (0)
A learning perspective on selfish behavior in games (2009) (0)
On a theory of computing symposia (1998) (0)
Session details: Session 10A (2011) (0)
Algorithms : From Theory to Application (0)
The J ohnson-Lindenstrauss Transform Itself Preserves Diffe rential Privacy (2012) (0)
A small extension of Chernoff-Hoeffding bounds (2021) (0)
{13 () Universal Portfolios with and without Transaction Costs (1997) (0)
Finding Relevant Subspaces in Neural Network Learning (1994) (0)
Session details: Session 4B (2003) (0)
Dynamics of Real-world Networks (2007) (0)
Building Consensus with Balanced Splits ⋆ (2014) (0)
Machine Learning , Game Theory , and Mechanism Design for a Networked World (2006) (0)
Session details: Session 9B (2003) (0)

This paper list is powered by the following services:

Other Resources About Avrim Blum

What Schools Are Affiliated With Avrim Blum?

Avrim Blum is affiliated with the following schools:

Image Attributions

Image Source for Avrim Blum