Avrim Blum
According to our database^{1},
Avrim Blum
authored at least 176 papers
between 1988 and 2018.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2007, "For contributions to learning theory and algorithms.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at dl.acm.org
On csauthors.net:
Bibliography
2018
From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
On preserving nondiscrimination 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 ThirtySecond AAAI Conference on Artificial Intelligence, 2018
2017
Opting Into Optimal Matchings.
Proceedings of the TwentyEighth Annual ACMSIAM 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 CoTraining 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
Lifelong Learning in Costly Feature Spaces.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017
2016
Semisupervised Learning.
Encyclopedia of Algorithms, 2016
Sparse Approximation via Generating Point Sets.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 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
Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015
Ignorance is Almost Bliss: NearOptimal Stochastic Matching With Few Queries.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 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
PrivacyPreserving 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 TwentyNinth AAAI Conference on Artificial Intelligence, 2015
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 BestResponse 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 TwentyEighth AAAI Conference on Artificial Intelligence, 2014
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 representationspecific 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
Centerbased clustering under perturbation stability.
Inf. Process. Lett., 2012
The JohnsonLindenstrauss 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 NearPerfect Phylogeny Construction.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012
2011
Welfare and Profit Maximization with Production Costs.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
2010
A discriminative model for semisupervised learning.
J. ACM, 2010
On NashEquilibria of ApproximationStable Games.
Proceedings of the Algorithmic Game Theory  Third International Symposium, 2010
Trading off Mistakes and Don'tKnow 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 69 December 2010, 2010
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.
Proceedings of the Innovations in Computer Science, 2010
Stability Yields a PTAS for kMedian and kMeans 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.
International Journal on Artificial Intelligence Tools, 2009
Improved equilibria via public service advertising.
Proceedings of the Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, 2009
Approximate clustering without the approximation.
Proceedings of the Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, 2009
The price of uncertainty.
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC2009), 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 710 December 2009, 2009
2008
A theory of learning with similarity functions.
Machine Learning, 2008
Reducing mechanism design to algorithm design via machine learning.
J. Comput. Syst. Sci., 2008
A learning theory approach to noninteractive 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
Item pricing for revenue maximization.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC2008), 2008
Limits of Learningbased 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
Mechanism design, machine learning, and pricing problems.
SIGecom Exchanges, 2007
Introduction to the special issue on COLT 2006.
Machine Learning, 2007
A Theory of LossLeaders: 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 (EC2007), 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 Semisupervised PAC Learning.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007
A Theory of Similarity Functions for Learning and Clustering.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007
2006
Kernels as features: On kernels, margins, and lowdimensional mappings.
Machine Learning, 2006
Approximation algorithms and online mechanisms for item pricing.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC2006), 2006
Routing without regret: on convergence to nash equilibria of regretminimizing algorithms in routing games.
Proceedings of the TwentyFifth Annual ACM Symposium on Principles of Distributed Computing, 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 RandomSurfer WebGraph Model.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006
2005
Combining Online Algorithms for Acceptance and Rejection.
Theory of Computing, 2005
Nearoptimal online auctions.
Proceedings of the Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2005
Random Projection, Margins, Kernels, and FeatureSelection.
Proceedings of the Subspace, 2005
Practical privacy: the SuLQ framework.
Proceedings of the Twentyfourth ACM SIGACTSIGMODSIGART 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
From External to Internal Regret.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005
A PACStyle Model for Learning from Labeled and Unlabeled Data.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005
2004
Approximation algorithms for deadlineTSP and vehicle routing with timewindows.
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
CoTraining and Expansion: Towards Bridging Theory and Practice.
Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004
Semisupervised 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 LowDimensional Mappings.
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004
2003
On Statistical Query Sampling and NMR Quantum Computing
Electronic Colloquium on Computational Complexity (ECCC), 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
Online learning in online auctions.
Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2003
On polynomialtime preference elicitation with value queries.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC2003), 2003
Planning in the Presence of Cost Functions Controlled by an Adversary.
Proceedings of the Machine Learning, 2003
Approximation Algorithms for Orienteering and DiscountedReward TSP.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 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 FlowTime with Admission Control.
Proceedings of the Algorithms, 2003
PACMDL Bounds.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003
Preference Elicitation and Query Learning.
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
On Statistical Query Sampling and NMR Quantum Computing.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
2002
Online algorithms for market clearing.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Smoothed analysis of the perceptron algorithm for linear programming.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Static optimality and dynamic searchoptimality in lists and trees.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Correlation Clustering.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Admission Control to Minimize Rejections.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 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
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
Noisetolerant learning, the parity problem, and the statistical query model.
Proceedings of the ThirtySecond Annual ACM Symposium on Theory of Computing, 2000
FeatureBoost: A MetaLearning 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
A ConstantFactor Approximation Algorithm for the kMST Problem.
J. Comput. Syst. Sci., 1999
Online algorithms for combining language models.
Proceedings of the 1999 IEEE International Conference on Acoustics, 1999
FinelyCompetitive 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
Microchoice Bounds and Self Bounding Learning Algorithms.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999
Beating the HoldOut: Bounds for Kfold and Progressive CrossValidation.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999
1998
On a theory of computing symposia.
SIGACT News, 1998
A ConstantFactor Approximation Algorithm for the Geometric kMST Problem in the Plane.
SIAM J. Comput., 1998
New Approximation Guarantees for MinimumWeight kTrees and PrizeCollecting Salesmen.
SIAM J. Comput., 1998
On Learning ReadkSatisfyj DNF.
SIAM J. Comput., 1998
A Note on Learning from MultipleInstance Examples.
Machine Learning, 1998
SemiDefinite Relaxations for Minimum Bandwidth and other VertexOrdering Problems.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
On Learning Monotone Boolean Functions.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
Combining Labeled and Unlabeled Data with CoTraining.
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 WeightedMajority Algorithms: Results on a Calendar Scheduling Domain.
Machine Learning, 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 3Colorable Graphs.
Inf. Process. Lett., 1997
Selection of Relevant Features and Examples in Machine Learning.
Artif. Intell., 1997
A polylog(n)Competitive Algorithm for Metrical Task Systems.
Proceedings of the TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Universal Portfolios With and Without Transaction Costs.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997
Online Learning and the Metrical Task System Problem.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997
1996
A Constantfactor Approximation Algorithm for the k MST Problem (Extended Abstract).
Proceedings of the TwentyEighth Annual ACM Symposium on the Theory of Computing, 1996
Randomized Robot Navigation Algorithms.
Proceedings of the Seventh Annual ACMSIAM Symposium on Discrete Algorithms, 1996
A PolynomialTime Algorithm for Learning Noisy Linear Threshold Functions.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
Online Algorithms in Machine Learning.
Proceedings of the Online Algorithms, 1996
1995
Fast Learning of kTerm DNF Formulas with Queries.
J. Comput. Syst. Sci., 1995
Coloring Random and SemiRandom kColorable Graphs.
J. Algorithms, 1995
A constantfactor approximation for the kMST problem in the plane.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
Improved approximation guarantees for minimumweight ktrees and prizecollecting salesmen.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
Fast Planning Through Planning Graph Analysis.
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995
Empirical Support for Winnow and WeightedMajority Based Algorithms: Results on a Calendar Scheduling Domain.
Proceedings of the Machine Learning, 1995
Learning with Unreliable Boundary Queries.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995
1994
Separating DistributionFree and MistakeBound 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 TwentySixth Annual ACM Symposium on Theory of Computing, 1994
The minimum latency problem.
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
On Learning ReadkSatisfyj DNF.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994
1993
Training a 3Node Neural Network is NPComplete.
Proceedings of the Machine Learning: From Theory to Applications, 1993
Learning an Intersection of k Halfspaces over a Uniform Distribution
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993
An OnLine 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
Learning Boolean Functions in an Infinite Attribute Space.
Machine Learning, 1992
Rankr Decision Trees are a Subclass of rDecision Lists.
Inf. Process. Lett., 1992
Fast Learning of kTerm DNF Formulas with Queries
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 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
Linear Approximation of Shortest Superstrings
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
Navigating in Unfamiliar Geometric Terrain (Extended Summary).
Proceedings of the OnLine Algorithms, 1991
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
Proceedings of the Fourth Annual Workshop on Computational Learning Theory, 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 3Coloring (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
Separating DistributionFree and MistakeBound Learning Models over the Boolean Domain
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 MistakeBound 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 3Coloring (and Improved Approximation Algorithm for kColoring)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
1988
Training a 3Node Neural Network is NPComplete.
Proceedings of the Advances in Neural Information Processing Systems 1, 1988
Training a 3Node Neural Network is NPComplete.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988