 | 2012 |
|---|
| 161 |       | Jeremiah Blocki,
Avrim Blum,
Anupam Datta,
Or Sheffet:
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
CoRR abs/1204.2136: (2012) |
| 160 | | Maria-Florina Balcan,
Avrim Blum,
Shai Fine,
Yishay Mansour:
Distributed Learning, Communication Complexity and Privacy
CoRR abs/1204.3514: (2012) |
| 159 | | Pranjal Awasthi,
Avrim Blum,
Or Sheffet:
Center-based clustering under perturbation stability.
Inf. Process. Lett. 112(1-2): 49-54 (2012) |
| 2011 |
|---|
| 158 | | Avrim Blum,
Anupam Gupta,
Yishay Mansour,
Ankit Sharma:
Welfare and Profit Maximization with Production Costs.
FOCS 2011: 77-86 |
| 157 | | Avrim Blum,
Katrina Ligett,
Aaron Roth:
A Learning Theory Approach to Non-Interactive Database Privacy
CoRR abs/1109.2229: (2011) |
| 156 | | Avrim Blum,
Anupam Gupta,
Yishay Mansour,
Ankit Sharma:
Welfare and Profit Maximization with Production Costs
CoRR abs/1110.4992: (2011) |
| 155 | | Maria-Florina Balcan,
Eric Blais,
Avrim Blum,
Liu Yang:
Active Testing
CoRR abs/1111.0897: (2011) |
| 154 | | Avrim Blum,
Aaron Roth:
Fast Private Data Release Algorithms for Sparse Queries
CoRR abs/1111.6842: (2011) |
| 2010 |
|---|
| 153 | | Pranjal Awasthi,
Avrim Blum,
Or Sheffet:
Improved Guarantees for Agnostic Learning of Disjunctions.
COLT 2010: 359-367 |
| 152 | | Pranjal Awasthi,
Avrim Blum,
Or Sheffet:
Stability Yields a PTAS for k-Median and k-Means Clustering.
FOCS 2010: 309-318 |
| 151 | | Maria-Florina Balcan,
Avrim Blum,
Yishay Mansour:
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.
ICS 2010: 200-213 |
| 150 | | Amin Sayedi,
Morteza Zadimoghaddam,
Avrim Blum:
Trading off Mistakes and Don't-Know Predictions.
NIPS 2010: 2092-2100 |
| 149 | | Pranjal Awasthi,
Maria-Florina Balcan,
Avrim Blum,
Or Sheffet,
Santosh Vempala:
On Nash-Equilibria of Approximation-Stable Games.
SAGT 2010: 78-89 |
| 148 | | Pranjal Awasthi,
Avrim Blum,
Or Sheffet:
Center-based Clustering under Perturbation Stability
CoRR abs/1009.3594: (2010) |
| 147 | | Maria-Florina Balcan,
Avrim Blum:
A discriminative model for semi-supervised learning.
J. ACM 57(3): (2010) |
| 146 | | Avrim Blum,
Eyal Even-Dar,
Katrina Ligett:
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games.
Theory of Computing 6(1): 179-199 (2010) |
| 2009 |
|---|
| 145 | | Maria-Florina Balcan,
Avrim Blum,
Yishay Mansour:
The price of uncertainty.
ACM Conference on Electronic Commerce 2009: 285-294 |
| 144 | | Shobha Venkataraman,
Avrim Blum,
Dawn Song,
Subhabrata Sen,
Oliver Spatscheck:
Tracking Dynamic Sources of Malicious Activity at Internet Scale.
NIPS 2009: 1946-1954 |
| 143 | | Maria-Florina Balcan,
Avrim Blum,
Anupam Gupta:
Approximate clustering without the approximation.
SODA 2009: 1068-1077 |
| 142 | | Maria-Florina Balcan,
Avrim Blum,
Yishay Mansour:
Improved equilibria via public service advertising.
SODA 2009: 728-737 |
| 141 | | Sharath R. Cholleti,
Sally A. Goldman,
Avrim Blum,
David G. Politte,
Steven Don,
Kirk Smith,
Fred Prior:
Veritas: Combining Expert Opinions without Labeled Data.
International Journal on Artificial Intelligence Tools 18(5): 633-651 (2009) |
| 2008 |
|---|
| 140 | | Maria-Florina Balcan,
Avrim Blum,
Yishay Mansour:
Item pricing for revenue maximization.
ACM Conference on Electronic Commerce 2008: 50-59 |
| 139 | | Maria-Florina Balcan,
Avrim Blum:
Clustering with Interactive Feedback.
ALT 2008: 316-328 |
| 138 | | Maria-Florina Balcan,
Avrim Blum,
Nathan Srebro:
Improved Guarantees for Learning via Similarity Functions.
COLT 2008: 287-298 |
| 137 | | Sharath R. Cholleti,
Sally A. Goldman,
Avrim Blum,
David G. Politte,
Steven Don:
Veritas: Combining Expert Opinions without Labeled Data.
ICTAI (1) 2008: 45-52 |
| 136 | | Shobha Venkataraman,
Avrim Blum,
Dawn Song:
Limits of Learning-based Signature Generation with Adversaries.
NDSS 2008 |
| 135 | | Avrim Blum,
MohammadTaghi Hajiaghayi,
Katrina Ligett,
Aaron Roth:
Regret minimization and the price of total anarchy.
STOC 2008: 373-382 |
| 134 | | Avrim Blum,
Katrina Ligett,
Aaron Roth:
A learning theory approach to non-interactive database privacy.
STOC 2008: 609-618 |
| 133 | | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
A discriminative framework for clustering via similarity functions.
STOC 2008: 671-680 |
| 132 | | Maria-Florina Balcan,
Avrim Blum,
Jason D. Hartline,
Yishay Mansour:
Reducing mechanism design to algorithm design via machine learning.
J. Comput. Syst. Sci. 74(8): 1245-1270 (2008) |
| 131 | | Maria-Florina Balcan,
Avrim Blum,
Nathan Srebro:
A theory of learning with similarity functions.
Machine Learning 72(1-2): 89-112 (2008) |
| 130 | | Maria-Florina Balcan,
Avrim Blum,
Yishay Mansour:
Item pricing for revenue maximization.
SIGecom Exchanges 7(3): (2008) |
| 2007 |
|---|
| 129 | | David J. Abraham,
Avrim Blum,
Tuomas Sandholm:
Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.
ACM Conference on Electronic Commerce 2007: 295-304 |
| 128 | | Avrim Blum:
A Theory of Similarity Functions for Learning and Clustering.
ALT 2007: 9 |
| 127 | | Avrim Blum,
Maria-Florina Balcan:
Open Problems in Efficient Semi-supervised PAC Learning.
COLT 2007: 622-624 |
| 126 | | Avrim Blum:
A Theory of Similarity Functions for Learning and Clustering.
Discovery Science 2007: 39 |
| 125 | | Avrim Blum,
Amin Coja-Oghlan,
Alan M. Frieze,
Shuheng Zhou:
Separating Populations with Wide Data: A Spectral Analysis.
ISAAC 2007: 439-451 |
| 124 | | Maria-Florina Balcan,
Avrim Blum,
T.-H. Hubert Chan,
MohammadTaghi Hajiaghayi:
A Theory of Loss-Leaders: Making Money by Pricing Below Cost.
WINE 2007: 293-299 |
| 123 | | Avrim Blum,
Yishay Mansour:
From External to Internal Regret.
Journal of Machine Learning Research 8: 1307-1324 (2007) |
| 122 | | Avrim Blum,
Gábor Lugosi,
Hans-Ulrich Simon:
Introduction to the special issue on COLT 2006.
Machine Learning 69(2-3): 75-77 (2007) |
| 121 | | Avrim Blum,
Shuchi Chawla,
David R. Karger,
Terran Lane,
Adam Meyerson,
Maria Minkoff:
Approximation Algorithms for Orienteering and Discounted-Reward TSP.
SIAM J. Comput. 37(2): 653-670 (2007) |
| 120 | | Maria-Florina Balcan,
Avrim Blum:
Mechanism design, machine learning, and pricing problems.
SIGecom Exchanges 7(1): 34-36 (2007) |
| 119 | | Maria-Florina Balcan,
Avrim Blum:
Approximation Algorithms and Online Mechanisms for Item Pricing.
Theory of Computing 3(1): 179-195 (2007) |
| 2006 |
|---|
| 118 | | Maria-Florina Balcan,
Avrim Blum:
Approximation algorithms and online mechanisms for item pricing.
ACM Conference on Electronic Commerce 2006: 29-35 |
| 117 | | Maria-Florina Balcan,
Avrim Blum:
On a theory of learning with similarity functions.
ICML 2006: 73-80 |
| 116 | | Avrim Blum,
Eyal Even-Dar,
Katrina Ligett:
Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games.
PODC 2006: 45-52 |
| 115 | | Avrim Blum,
Tuomas Sandholm,
Martin Zinkevich:
Online algorithms for market clearing.
J. ACM 53(5): 845-879 (2006) |
| 114 | | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
Kernels as features: On kernels, margins, and low-dimensional mappings.
Machine Learning 65(1): 79-94 (2006) |
| 2005 |
|---|
| 113 | | Maria-Florina Balcan,
Avrim Blum:
A PAC-Style Model for Learning from Labeled and Unlabeled Data.
COLT 2005: 111-126 |
| 112 | | Avrim Blum,
Yishay Mansour:
From External to Internal Regret.
COLT 2005: 621-636 |
| 111 | | Maria-Florina Balcan,
Avrim Blum,
Jason D. Hartline,
Yishay Mansour:
Mechanism Design via Machine Learning.
FOCS 2005: 605-614 |
| 110 | | Shobha Venkataraman,
Dawn Xiaodong Song,
Phillip B. Gibbons,
Avrim Blum:
New Streaming Algorithms for Fast Detection of Superspreaders.
NDSS 2005 |
| 109 | | Avrim Blum,
Cynthia Dwork,
Frank McSherry,
Kobbi Nissim:
Practical privacy: the SuLQ framework.
PODS 2005: 128-138 |
| 108 | | Avrim Blum:
Random Projection, Margins, Kernels, and Feature-Selection.
SLSFS 2005: 52-68 |
| 107 | | Avrim Blum,
Jason D. Hartline:
Near-optimal online auctions.
SODA 2005: 1156-1163 |
| 106 | | Yossi Azar,
Avrim Blum,
David P. Bunde,
Yishay Mansour:
Combining Online Algorithms for Acceptance and Rejection.
Theory of Computing 1(1): 105-117 (2005) |
| 2004 |
|---|
| 105 | | Maria-Florina Balcan,
Avrim Blum,
Santosh Vempala:
On Kernels, Margins, and Low-Dimensional Mappings.
ALT 2004: 194-205 |
| 104 | | H. Brendan McMahan,
Avrim Blum:
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary.
COLT 2004: 109-123 |
| 103 | | Avrim Blum,
John D. Lafferty,
Mugizi Robert Rwebangira,
Rajashekar Reddy:
Semi-supervised learning using randomized mincuts.
ICML 2004 |
| 102 | | Maria-Florina Balcan,
Avrim Blum,
Ke Yang:
Co-Training and Expansion: Towards Bridging Theory and Practice.
NIPS 2004 |
| 101 | | Avrim Blum,
Dawn Xiaodong Song,
Shobha Venkataraman:
Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds.
RAID 2004: 258-277 |
| 100 | | Nikhil Bansal,
Avrim Blum,
Shuchi Chawla,
Adam Meyerson:
Approximation algorithms for deadline-TSP and vehicle routing with time-windows.
STOC 2004: 166-174 |
| 99 | | Avrim Blum,
Jeffrey C. Jackson,
Tuomas Sandholm,
Martin Zinkevich:
Preference Elicitation and Query Learning.
Journal of Machine Learning Research 5: 649-667 (2004) |
| 98 | | Nikhil Bansal,
Avrim Blum,
Shuchi Chawla:
Correlation Clustering.
Machine Learning 56(1-3): 89-113 (2004) |
| 97 | | Avrim Blum,
Vijay Kumar,
Atri Rudra,
Felix Wu:
Online learning in online auctions.
Theor. Comput. Sci. 324(2-3): 137-146 (2004) |
| 2003 |
|---|
| 96 | | Martin Zinkevich,
Avrim Blum,
Tuomas Sandholm:
On polynomial-time preference elicitation with value queries.
ACM Conference on Electronic Commerce 2003: 176-185 |
| 95 | | Avrim Blum,
Jeffrey C. Jackson,
Tuomas Sandholm,
Martin Zinkevich:
Preference Elicitation and Query Learning.
COLT 2003: 13-25 |
| 94 | | Avrim Blum,
John Langford:
PAC-MDL Bounds.
COLT 2003: 344-357 |
| 93 | | Avrim Blum:
Learning a Function of r Relevant Variables.
COLT 2003: 731-733 |
| 92 | | Nikhil Bansal,
Avrim Blum,
Shuchi Chawla,
Kedar Dhamdhere:
Scheduling for Flow-Time with Admission Control.
ESA 2003: 43-54 |
| 91 | | Avrim Blum:
Machine Learning: My Favorite Results, Directions, and Open Problems.
FOCS 2003: 2- |
| 90 | | Avrim Blum,
Shuchi Chawla,
David R. Karger,
Terran Lane,
Adam Meyerson,
Maria Minkoff:
Approximation Algorithms for Orienteering and Discounted-Reward TSP.
FOCS 2003: 46-55 |
| 89 |  | H. Brendan McMahan,
Geoffrey J. Gordon,
Avrim Blum:
Planning in the Presence of Cost Functions Controlled by an Adversary.
ICML 2003: 536-543 |
| 88 | | Ke Yang,
Avrim Blum:
On Statistical Query Sampling and NMR Quantum Computing.
IEEE Conference on Computational Complexity 2003: 194- |
| 87 | | Avrim Blum,
Vijay Kumar,
Atri Rudra,
Felix Wu:
Online learning in online auctions.
SODA 2003: 202-204 |
| 86 | | Yossi Azar,
Avrim Blum,
Yishay Mansour:
Combining online algorithms for rejection and acceptance.
SPAA 2003: 159-163 |
| 85 | | Nikhil Bansal,
Avrim Blum,
Shuchi Chawla,
Adam Meyerson:
Online oblivious routing.
SPAA 2003: 44-49 |
| 84 | | Avrim Blum,
Shuchi Chawla,
Adam Kalai:
Static Optimality and Dynamic Search-Optimality in Lists and Trees.
Algorithmica 36(3): 249-260 (2003) |
| 83 | | Avrim Blum,
Ke Yang:
On Statistical Query Sampling and NMR Quantum Computing
Electronic Colloquium on Computational Complexity (ECCC) 10(014): (2003) |
| 82 | | Avrim Blum,
Adam Tauman Kalai,
Jon M. Kleinberg:
Admission Control to Minimize Rejections.
Internet Mathematics 1(2): 165-176 (2003) |
| 81 | | Avrim Blum,
Adam Kalai,
Hal Wasserman:
Noise-tolerant learning, the parity problem, and the statistical query model.
J. ACM 50(4): 506-519 (2003) |
| 80 | | John Langford,
Avrim Blum:
Microchoice Bounds and Self Bounding Learning Algorithms.
Machine Learning 51(2): 165-179 (2003) |
| 2002 |
|---|
| 79 | | Nikhil Bansal,
Avrim Blum,
Shuchi Chawla:
Correlation Clustering.
FOCS 2002: 238- |
| 78 | | Avrim Blum,
Shuchi Chawla,
Adam Kalai:
Static optimality and dynamic search-optimality in lists and trees.
SODA 2002: 1-8 |
| 77 | | Avrim Blum,
John Dunagan:
Smoothed analysis of the perceptron algorithm for linear programming.
SODA 2002: 905-914 |
| 76 | | Avrim Blum,
Tuomas Sandholm,
Martin Zinkevich:
Online algorithms for market clearing.
SODA 2002: 971-980 |
| 2001 |
|---|
| 75 | | Avrim Blum,
Shuchi Chawla:
Learning from Labeled and Unlabeled Data using Graph Mincuts.
ICML 2001: 19-26 |
| 74 | | Avrim Blum,
Adam Kalai,
Jon M. Kleinberg:
Admission Control to Minimize Rejections.
WADS 2001: 155-164 |
| 2000 |
|---|
| 73 | | Joseph O'Sullivan,
John Langford,
Rich Caruana,
Avrim Blum:
FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness.
ICML 2000: 703-710 |
| 72 | | Avrim Blum,
Adam Kalai,
Hal Wasserman:
Noise-tolerant learning, the parity problem, and the statistical query model.
STOC 2000: 435-440 |
| 71 | | Avrim Blum,
Adam Kalai,
Hal Wasserman:
Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
CoRR cs.LG/0010022: (2000) |
| 70 | | Avrim Blum,
Carl Burch:
On-line Learning and the Metrical Task System Problem.
Machine Learning 39(1): 35-58 (2000) |
| 69 | | Avrim Blum,
Prasad Chalasani:
An Online Algorithm for Improving Performance in Navigation.
SIAM J. Comput. 29(6): 1907-1938 (2000) |
| 68 | | Avrim Blum,
Howard J. Karloff,
Yuval Rabani,
Michael E. Saks:
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.
SIAM J. Comput. 30(5): 1624-1661 (2000) |
| 67 | | Avrim Blum,
Goran Konjevod,
R. Ravi,
Santosh Vempala:
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.
Theor. Comput. Sci. 235(1): 25-42 (2000) |
| 1999 |
|---|
| 66 | | Avrim Blum,
Adam Kalai,
John Langford:
Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation.
COLT 1999: 203-208 |
| 65 | | John Langford,
Avrim Blum:
Microchoice Bounds and Self Bounding Learning Algorithms.
COLT 1999: 209-214 |
| 64 | | Avrim Blum,
John Langford:
Probabilistic Planning in the Graphplan Framework.
ECP 1999: 319-332 |
| 63 | | Avrim Blum,
Carl Burch,
Adam Kalai:
Finely-Competitive Paging.
FOCS 1999: 450-458 |
| 62 | | Avrim Blum,
R. Ravi,
Santosh Vempala:
A Constant-Factor Approximation Algorithm for the k-MST Problem.
J. Comput. Syst. Sci. 58(1): 101-108 (1999) |
| 61 | | Avrim Blum,
Adam Kalai:
Universal Portfolios With and Without Transaction Costs.
Machine Learning 35(3): 193-205 (1999) |
| 1998 |
|---|
| 60 | | Avrim Blum,
Tom M. Mitchell:
Combining Labeled and Unlabeled Sata with Co-Training.
COLT 1998: 92-100 |
| 59 | | Avrim Blum,
Carl Burch,
John Langford:
On Learning Monotone Boolean Functions.
FOCS 1998: 408-415 |
| 58 | | Avrim Blum,
Goran Konjevod,
R. Ravi,
Santosh Vempala:
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
STOC 1998: 100-105 |
| 57 | | Avrim Blum,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Algorithmica 22(1/2): 35-52 (1998) |
| 56 | | Avrim Blum,
Prasad Chalasani,
Sally A. Goldman,
Donna K. Slonim:
Learning with Unreliable Boundary Queries.
J. Comput. Syst. Sci. 56(2): 209-222 (1998) |
| 55 | | Avrim Blum,
Adam Kalai:
A Note on Learning from Multiple-Instance Examples.
Machine Learning 30(1): 23-29 (1998) |
| 54 | | Howard Aizenstein,
Avrim Blum,
Roni Khardon,
Eyal Kushilevitz,
Leonard Pitt,
Dan Roth:
On Learning Read-k-Satisfy-j DNF.
SIAM J. Comput. 27(6): 1515-1530 (1998) |
| 53 | | Baruch Awerbuch,
Yossi Azar,
Avrim Blum,
Santosh Vempala:
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
SIAM J. Comput. 28(1): 254-262 (1998) |
| 52 | | Joseph S. B. Mitchell,
Avrim Blum,
Prasad Chalasani,
Santosh Vempala:
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane.
SIAM J. Comput. 28(3): 771-781 (1998) |
| 51 | | Avrim Blum,
Prabhakar Raghavan:
On a theory of computing symposia.
SIGACT News 29(3): 104-111 (1998) |
| 1997 |
|---|
| 50 | | Avrim Blum,
Adam Kalai:
Universal Portfolios With and Without Transaction Costs.
COLT 1997: 309-313 |
| 49 | | Avrim Blum,
Carl Burch:
On-line Learning and the Metrical Task System Problem.
COLT 1997: 45-53 |
| 48 | | Yair Bartal,
Avrim Blum,
Carl Burch,
Andrew Tomkins:
A polylog(n)-Competitive Algorithm for Metrical Task Systems.
STOC 1997: 711-719 |
| 47 | | Avrim Blum,
Merrick L. Furst:
Fast Planning Through Planning Graph Analysis.
Artif. Intell. 90(1-2): 281-300 (1997) |
| 46 | | Avrim Blum,
Pat Langley:
Selection of Relevant Features and Examples in Machine Learning.
Artif. Intell. 97(1-2): 245-271 (1997) |
| 45 | | Avrim Blum,
David R. Karger:
An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs.
Inf. Process. Lett. 61(1): 49-53 (1997) |
| 44 | | Avrim Blum,
Ravindran Kannan:
Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution.
J. Comput. Syst. Sci. 54(2): 371-380 (1997) |
| 43 | | Avrim Blum:
Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain.
Machine Learning 26(1): 5-23 (1997) |
| 42 | | Avrim Blum,
Prabhakar Raghavan,
Baruch Schieber:
Navigating in Unfamiliar Geometric Terrain.
SIAM J. Comput. 26(1): 110-137 (1997) |
| 1996 |
|---|
| 41 | | Avrim Blum,
Michael Kearns:
Proceedings of the Ninth Annual Conference on Computational Learning Theory, COLT 1996, Desenzano del Garda, Italy, June 28-July 1, 1996.
ACM 1996 |
| 40 | | Avrim Blum,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
FOCS 1996: 330-338 |
| 39 | | Avrim Blum:
On-line Algorithms in Machine Learning.
Online Algorithms 1996: 306-325 |
| 38 | | Piotr Berman,
Avrim Blum,
Amos Fiat,
Howard J. Karloff,
Adi Rosén,
Michael E. Saks:
Randomized Robot Navigation Algorithms.
SODA 1996: 75-84 |
| 37 | | Avrim Blum,
R. Ravi,
Santosh Vempala:
A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract).
STOC 1996: 442-448 |
| 1995 |
|---|
| 36 | | Avrim Blum,
Prasad Chalasani,
Sally A. Goldman,
Donna K. Slonim:
Learning with Unreliable Boundary Queries.
COLT 1995: 98-107 |
| 35 | | Avrim Blum:
Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain.
ICML 1995: 64-72 |
| 34 | | Avrim Blum,
Merrick L. Furst:
Fast Planning Through Planning Graph Analysis.
IJCAI 1995: 1636-1642 |
| 33 | | Baruch Awerbuch,
Yossi Azar,
Avrim Blum,
Santosh Vempala:
Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen.
STOC 1995: 277-283 |
| 32 | | Avrim Blum,
Prasad Chalasani,
Santosh Vempala:
A constant-factor approximation for the k-MST problem in the plane.
STOC 1995: 294-302 |
| 31 | | Avrim Blum,
Joel Spencer:
Coloring Random and Semi-Random k-Colorable Graphs.
J. Algorithms 19(2): 204-234 (1995) |
| 30 | | Avrim Blum,
Lisa Hellerstein,
Nick Littlestone:
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
J. Comput. Syst. Sci. 50(1): 32-40 (1995) |
| 29 | | Avrim Blum,
Steven Rudich:
Fast Learning of k-Term DNF Formulas with Queries.
J. Comput. Syst. Sci. 51(3): 367-373 (1995) |
| 1994 |
|---|
| 28 | | Avrim Blum,
Roni Khardon,
Eyal Kushilevitz,
Leonard Pitt,
Dan Roth:
On Learning Read-k-Satisfy-j DNF.
COLT 1994: 110-117 |
| 27 | | Avrim Blum,
Prasad Chalasani,
Don Coppersmith,
William R. Pulleyblank,
Prabhakar Raghavan,
Madhu Sudan:
The minimum latency problem.
STOC 1994: 163-171 |
| 26 | | Avrim Blum,
Merrick L. Furst,
Jeffrey C. Jackson,
Michael J. Kearns,
Yishay Mansour,
Steven Rudich:
Weakly learning DNF and characterizing statistical query learning using Fourier analysis.
STOC 1994: 253-262 |
| 25 | | Avrim Blum:
New Approximation Algorithms for Graph Coloring.
J. ACM 41(3): 470-516 (1994) |
| 24 | | Avrim Blum,
Tao Jiang,
Ming Li,
John Tromp,
Mihalis Yannakakis:
Linear Approximation of Shortest Superstrings.
J. ACM 41(4): 630-647 (1994) |
| 23 | | Avrim Blum:
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain.
SIAM J. Comput. 23(5): 990-1000 (1994) |
| 1993 |
|---|
| 22 | | Avrim Blum,
Prasad Chalasani,
Jeffrey C. Jackson:
On Learning Embedded Symmetric Concepts.
COLT 1993: 337-346 |
| 21 | | Avrim Blum,
Merrick L. Furst,
Michael J. Kearns,
Richard J. Lipton:
Cryptographic Primitives Based on Hard Learning Problems.
CRYPTO 1993: 278-291 |
| 20 | | Avrim Blum,
Prasad Chalasani:
An On-Line Algorithm for Improving Performance in Navigation
FOCS 1993: 2-11 |
| 19 | | Avrim Blum,
Ravi Kannan:
Learning an Intersection of k Halfspaces over a Uniform Distribution
FOCS 1993: 312-320 |
| 18 | | Avrim Blum,
Ronald L. Rivest:
Training a 3-Node Neural Network is NP-Complete.
Machine Learning: From Theory to Applications 1993: 9-28 |
| 1992 |
|---|
| 17 | | Avrim Blum,
Prasad Chalasani:
Learning Switching Concepts.
COLT 1992: 231-242 |
| 16 | | Avrim Blum,
Howard J. Karloff,
Yuval Rabani,
Michael E. Saks:
A Decomposition Theorem and Bounds for Randomized Server Problems
FOCS 1992: 197-207 |
| 15 | | Avrim Blum,
Steven Rudich:
Fast Learning of k-Term DNF Formulas with Queries
STOC 1992: 382-389 |
| 14 | | Avrim Blum:
Rank-r Decision Trees are a Subclass of r-Decision Lists.
Inf. Process. Lett. 42(4): 183-185 (1992) |
| 13 | | Avrim Blum:
Learning Boolean Functions in an Infinite Attribute Space.
Machine Learning 9: 373-386 (1992) |
| 12 | | Avrim Blum,
Ronald L. Rivest:
Training a 3-node neural network is NP-complete.
Neural Networks 5(1): 117-127 (1992) |
| 1991 |
|---|
| 11 | | Avrim Blum,
Lisa Hellerstein,
Nick Littlestone:
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
COLT 1991: 157-166 |
| 10 | | Avrim Blum,
Tao Jiang,
Ming Li,
John Tromp,
Mihalis Yannakakis:
Linear Approximation of Shortest Superstrings
STOC 1991: 328-336 |
| 9 | | Avrim Blum,
Prabhakar Raghavan,
Baruch Schieber:
Navigating in Unfamiliar Geometric Terrain (Preliminary Version)
STOC 1991: 494-504 |
| 1990 |
|---|
| 8 | | Avrim Blum,
Mona Singh:
Learning Functions of k Terms.
COLT 1990: 144-153 |
| 7 | | Avrim Blum:
Separating PAC and Mistake-Bound Learning Models Over the Boolean Domain (Abstract).
COLT 1990: 393 |
| 6 | | Avrim Blum:
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain
FOCS 1990: 211-218 |
| 5 | | Avrim Blum:
Some Tools for Approximate 3-Coloring (Extended Abstract)
FOCS 1990: 554-562 |
| 4 | | Avrim Blum:
Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract)
STOC 1990: 64-72 |
| 1989 |
|---|
| 3 | | Avrim Blum:
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring)
STOC 1989: 535-542 |
| 1988 |
|---|
| 2 | | Avrim Blum,
Ronald L. Rivest:
Training a 3-Node Neural Network is NP-Complete.
COLT 1988: 9-18 |
| 1 | | Avrim Blum,
Ronald L. Rivest:
Training a 3-Node Neural Network is NP-Complete.
NIPS 1988: 494-501 |
Data released under the ODC-BY 1.0 license — See also our legal information page