Avrim Blum

According to our database1, Avrim Blum authored at least 182 papers between 1989 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2007, "For contributions to learning theory and algorithms.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Lifelong learning in costly feature spaces.
Theor. Comput. Sci., 2020

Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries.
Oper. Res., 2020

Learning Complexity of Simulated Annealing.
CoRR, 2020

Random Smoothing Might be Unable to Certify 𝓁 Robustness for High-Dimensional Images.
CoRR, 2020

Technical perspective: Algorithm selection as a learning problem.
Commun. ACM, 2020

Advancing Subgroup Fairness via Sleeping Experts.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Recovering from Biased Data: Can Fairness Constraints Improve Accuracy?
Proceedings of the 1st Symposium on Foundations of Responsible Computing, 2020

2019
Sparse Approximation via Generating Point Sets.
ACM Trans. Algorithms, 2019

Computing Stackelberg Equilibria of Large General-Sum Games.
Proceedings of the Algorithmic Game Theory - 12th International Symposium, 2019

Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Optimal Strategies of Blotto Games: Beyond Convexity.
Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

2018
Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions.
ACM Trans. Economics and Comput., 2018

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

On preserving non-discrimination when combining expert advice.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

On Price versus Quality.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Approximate Convex Hull of Data Streams.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Active Tolerant Testing.
Proceedings of the Conference On Learning Theory, 2018

Diversified Strategies for Mitigating Adversarial Attacks in Multiagent Systems.
Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Algorithms for Generalized Topic Modeling.
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017
Opting Into Optimal Matchings.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Collaborative PAC Learning.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Efficient Co-Training of Linear Separators under Weak Dependence.
Proceedings of the 30th Conference on Learning Theory, 2017

Efficient PAC Learning from the Crowd.
Proceedings of the 30th Conference on Learning Theory, 2017

2016
Semi-supervised Learning.
Encyclopedia of Algorithms, 2016

Generalized Topic Modeling.
CoRR, 2016

On the Computational Hardness of Manipulating Pairwise Voting Rules.
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2015
Special Issue on New Theoretical Challenges in Machine Learning.
Algorithmica, 2015

Online Allocation and Pricing with Economies of Scale.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Commitment Without Regrets: Online Learning in Stackelberg Security Games.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Variational Dropout and the Local Reparameterization Trick.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Privacy-Preserving Public Information for Sequential Games.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

The Ladder: A Reliable Leaderboard for Machine Learning Competitions.
Proceedings of the 32nd International Conference on Machine Learning, 2015

Efficient Representations for Lifelong Learning and Autoencoding.
Proceedings of The 28th Conference on Learning Theory, 2015

Learning Valuation Distributions from Partial Observation.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries.
CoRR, 2014

Efficient Representations for Life-Long Learning and Autoencoding.
CoRR, 2014

Estimating Accuracy from Unlabeled Data.
Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, 2014

Learning Optimal Commitment to Overcome Insecurity.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Active Learning and Best-Response Dynamics.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Learning Mixtures of Ranking Models.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Lazy Defenders Are Almost Optimal against Diligent Attackers.
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013
The Price of Uncertainty.
ACM Trans. Economics and Comput., 2013

Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.
SIAM J. Comput., 2013

A learning theory approach to noninteractive database privacy.
J. ACM, 2013

Clustering under approximation stability.
J. ACM, 2013

Harnessing the power of two crossmatches.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Learnability of DNF with representation-specific queries.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Differentially private data analysis of social networks via restricted sensitivity.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Exploiting Ontology Structures and Unlabeled Data for Learning.
Proceedings of the 30th International Conference on Machine Learning, 2013

Fast Private Data Release Algorithms for Sparse Queries.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
Distributed Learning, Communication Complexity and Privacy.
Proceedings of the COLT 2012, 2012

Center-based clustering under perturbation stability.
Inf. Process. Lett., 2012

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Active Property Testing.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Additive Approximation for Near-Perfect Phylogeny Construction.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Active Testing
CoRR, 2011

Welfare and Profit Maximization with Production Costs.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games.
Theory Comput., 2010

A discriminative model for semi-supervised learning.
J. ACM, 2010

On Nash-Equilibria of Approximation-Stable Games.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

Trading off Mistakes and Don't-Know Predictions.
Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

Stability Yields a PTAS for k-Median and k-Means Clustering.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Improved Guarantees for Agnostic Learning of Disjunctions.
Proceedings of the COLT 2010, 2010

2009
Veritas: Combining Expert Opinions without Labeled Data.
Int. J. Artif. Intell. Tools, 2009

Improved equilibria via public service advertising.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximate clustering without the approximation.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Tracking Dynamic Sources of Malicious Activity at Internet Scale.
Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

2008
Item pricing for revenue maximization.
SIGecom Exch., 2008

A theory of learning with similarity functions.
Mach. Learn., 2008

Reducing mechanism design to algorithm design via machine learning.
J. Comput. Syst. Sci., 2008

A learning theory approach to non-interactive database privacy.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Regret minimization and the price of total anarchy.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

A discriminative framework for clustering via similarity functions.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Limits of Learning-based Signature Generation with Adversaries.
Proceedings of the Network and Distributed System Security Symposium, 2008

Veritas: Combining Expert Opinions without Labeled Data.
Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2008), 2008

Improved Guarantees for Learning via Similarity Functions.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

Clustering with Interactive Feedback.
Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

2007
Approximation Algorithms and Online Mechanisms for Item Pricing.
Theory Comput., 2007

Mechanism design, machine learning, and pricing problems.
SIGecom Exch., 2007

Approximation Algorithms for Orienteering and Discounted-Reward TSP.
SIAM J. Comput., 2007

Introduction to the special issue on COLT 2006.
Mach. Learn., 2007

From External to Internal Regret.
J. Mach. Learn. Res., 2007

A Theory of Loss-Leaders: Making Money by Pricing Below Cost.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Separating Populations with Wide Data: A Spectral Analysis.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

A Theory of Similarity Functions for Learning and Clustering.
Proceedings of the Discovery Science, 10th International Conference, 2007

Open Problems in Efficient Semi-supervised PAC Learning.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006
Kernels as features: On kernels, margins, and low-dimensional mappings.
Mach. Learn., 2006

Online algorithms for market clearing.
J. ACM, 2006

On a theory of learning with similarity functions.
Proceedings of the Machine Learning, 2006

Black Box Anomaly Detection: Is It Utopian?.
Proceedings of the 5th ACM Workshop on Hot Topics in Networks, 2006

A Random-Surfer Web-Graph Model.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

An Augmented PAC Model for Semi-Supervised Learning.
Proceedings of the Semi-Supervised Learning, 2006

2005
Combining Online Algorithms for Acceptance and Rejection.
Theory Comput., 2005

Near-optimal online auctions.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Random Projection, Margins, Kernels, and Feature-Selection.
Proceedings of the Subspace, 2005

Practical privacy: the SuLQ framework.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

New Streaming Algorithms for Fast Detection of Superspreaders.
Proceedings of the Network and Distributed System Security Symposium, 2005

Mechanism Design via Machine Learning.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

A PAC-Style Model for Learning from Labeled and Unlabeled Data.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004
Online learning in online auctions.
Theor. Comput. Sci., 2004

Correlation Clustering.
Mach. Learn., 2004

Preference Elicitation and Query Learning.
J. Mach. Learn. Res., 2004

Approximation algorithms for deadline-TSP and vehicle routing with time-windows.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds.
Proceedings of the Recent Advances in Intrusion Detection: 7th International Symposium, 2004

Co-Training and Expansion: Towards Bridging Theory and Practice.
Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004

Semi-supervised learning using randomized mincuts.
Proceedings of the Machine Learning, 2004

Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

On Kernels, Margins, and Low-Dimensional Mappings.
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003
Microchoice Bounds and Self Bounding Learning Algorithms.
Mach. Learn., 2003

Noise-tolerant learning, the parity problem, and the statistical query model.
J. ACM, 2003

Admission Control to Minimize Rejections.
Internet Math., 2003

On Statistical Query Sampling and NMR Quantum Computing
Electronic Colloquium on Computational Complexity (ECCC), 2003

Static Optimality and Dynamic Search-Optimality in Lists and Trees.
Algorithmica, 2003

Online oblivious routing.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Combining online algorithms for rejection and acceptance.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

On polynomial-time preference elicitation with value queries.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Planning in the Presence of Cost Functions Controlled by an Adversary.
Proceedings of the Machine Learning, 2003

Machine Learning: My Favorite Results, Directions, and Open Problems.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Scheduling for Flow-Time with Admission Control.
Proceedings of the Algorithms, 2003

PAC-MDL Bounds.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

Learning a Function of r Relevant Variables.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002
Smoothed analysis of the perceptron algorithm for linear programming.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001
Learning from Labeled and Unlabeled Data using Graph Mincuts.
Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28, 2001

2000
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.
Theor. Comput. Sci., 2000

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.
SIAM J. Comput., 2000

An Online Algorithm for Improving Performance in Navigation.
SIAM J. Comput., 2000

On-line Learning and the Metrical Task System Problem.
Mach. Learn., 2000

FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness.
Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29, 2000

1999
Universal Portfolios With and Without Transaction Costs.
Mach. Learn., 1999

A Constant-Factor Approximation Algorithm for the k-MST Problem.
J. Comput. Syst. Sci., 1999

On-line algorithms for combining language models.
Proceedings of the 1999 IEEE International Conference on Acoustics, 1999

Finely-Competitive Paging.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Probabilistic Planning in the Graphplan Framework.
Proceedings of the Recent Advances in AI Planning, 5th European Conference on Planning, 1999

Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998
On a theory of computing symposia.
SIGACT News, 1998

A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane.
SIAM J. Comput., 1998

New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
SIAM J. Comput., 1998

On Learning Read-k-Satisfy-j DNF.
SIAM J. Comput., 1998

A Note on Learning from Multiple-Instance Examples.
Mach. Learn., 1998

Learning with Unreliable Boundary Queries.
J. Comput. Syst. Sci., 1998

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Algorithmica, 1998

On Learning Monotone Boolean Functions.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Combining Labeled and Unlabeled Data with Co-Training.
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997
Navigating in Unfamiliar Geometric Terrain.
SIAM J. Comput., 1997

Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain.
Mach. Learn., 1997

Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution.
J. Comput. Syst. Sci., 1997

An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs.
Inf. Process. Lett., 1997

Selection of Relevant Features and Examples in Machine Learning.
Artif. Intell., 1997

Fast Planning Through Planning Graph Analysis.
Artif. Intell., 1997

A polylog(n)-Competitive Algorithm for Metrical Task Systems.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996
A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Randomized Robot Navigation Algorithms.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On-line Algorithms in Machine Learning.
Proceedings of the Online Algorithms, 1996

1995
Fast Learning of k-Term DNF Formulas with Queries.
J. Comput. Syst. Sci., 1995

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
J. Comput. Syst. Sci., 1995

Coloring Random and Semi-Random k-Colorable Graphs.
J. Algorithms, 1995

A constant-factor approximation for the k-MST problem in the plane.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain.
Proceedings of the Machine Learning, 1995

1994
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain.
SIAM J. Comput., 1994

Linear Approximation of Shortest Superstrings.
J. ACM, 1994

New Approximation Algorithms for Graph Coloring.
J. ACM, 1994

Weakly learning DNF and characterizing statistical query learning using Fourier analysis.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

The minimum latency problem.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On Learning Read-k-Satisfy-j DNF.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993
Learning an Intersection of k Halfspaces over a Uniform Distribution
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

An On-Line Algorithm for Improving Performance in Navigation
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Cryptographic Primitives Based on Hard Learning Problems.
Proceedings of the Advances in Cryptology, 1993

On Learning Embedded Symmetric Concepts.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992
Training a 3-node neural network is NP-complete.
Neural Networks, 1992

Learning Boolean Functions in an Infinite Attribute Space.
Mach. Learn., 1992

Rank-r Decision Trees are a Subclass of r-Decision Lists.
Inf. Process. Lett., 1992

A Decomposition Theorem and Bounds for Randomized Server Problems
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Learning Switching Concepts.
Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991
Navigating in Unfamiliar Geometric Terrain (Preliminary Version)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Navigating in Unfamiliar Geometric Terrain (Extended Summary).
Proceedings of the On-Line Algorithms, 1991

1990
Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Some Tools for Approximate 3-Coloring (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Learning Functions of k Terms.
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

Separating PAC and Mistake-Bound Learning Models Over the Boolean Domain (Abstract).
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989


  Loading...