☰

Avrim Blum - Publications

Affiliations: 
Carnegie Mellon University, Pittsburgh, PA 
Area:
Computer Science, Mathematics
Tree Info Similar researchers PubMed Report error

47 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Blum A, Dickerson JP, Haghtalab N, Procaccia AD, Sandholm T, Sharma A. Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries Operations Research. 68: 16-34. DOI: 10.1287/Opre.2019.1856  0.363
2020 Blum A. Technical perspective: Algorithm selection as a learning problem Communications of the Acm. 63: 86-86. DOI: 10.1145/3394623  0.45
2020 Balcan M, Blum A, Nagarajan V. Lifelong learning in costly feature spaces Theoretical Computer Science. 808: 14-37. DOI: 10.1016/J.Tcs.2019.11.010  0.632
2015 Blum A, Long PM. Special Issue on New Theoretical Challenges in Machine Learning Algorithmica. 72: 191-192. DOI: 10.1007/S00453-014-9941-1  0.311
2013 Blum A, Ligett K, Roth A. A learning theory approach to noninteractive database privacy Journal of the Acm. 60. DOI: 10.1145/2450142.2450148  0.698
2013 Balcan MF, Blum A, Gupta A. Clustering under approximation stability Journal of the Acm. 60. DOI: 10.1145/2450142.2450144  0.588
2013 Balcan MF, Blum A, Mansour Y. Circumventing the price of anarchy: Leading dynamics to good behavior Siam Journal On Computing. 42: 230-264. DOI: 10.1137/110821317  0.585
2012 Awasthi P, Blum A, Sheffet O. Center-based clustering under perturbation stability Information Processing Letters. 112: 49-54. DOI: 10.1016/J.Ipl.2011.10.006  0.728
2010 Blum A, Even-Dar E, Ligett K. Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games Theory of Computing. 6: 179-199. DOI: 10.4086/Toc.2010.V006A008  0.702
2010 Balcan MF, Blum A. A discriminative model for semi-supervised learning Journal of the Acm. 57. DOI: 10.1145/1706591.1706599  0.657
2009 Blum A, Coja-Oghlan A, Frieze A, Zhou S. Separating populations with wide data: A spectral analysis Electronic Journal of Statistics. 3: 76-113. DOI: 10.1214/08-Ejs289  0.327
2009 Cholleti SR, Goldman SA, Blum A, Politte DG, Don S, Smith K, Prior F. Veritas: Combining expert opinions without labeled data International Journal On Artificial Intelligence Tools. 18: 633-651. DOI: 10.1142/S0218213009000330  0.355
2008 Balcan M, Blum A, Mansour Y. Item pricing for revenue maximization Sigecom Exchanges. 7: 6. DOI: 10.1145/1486877.1486883  0.568
2008 Balcan MF, Blum A, Hartline JD, Mansour Y. Reducing mechanism design to algorithm design via machine learning Journal of Computer and System Sciences. 74: 1245-1270. DOI: 10.1016/J.Jcss.2007.08.002  0.671
2008 Balcan MF, Blum A, Srebro N. A theory of learning with similarity functions Machine Learning. 72: 89-112. DOI: 10.1007/S10994-008-5059-5  0.613
2007 Balcan M, Blum A. Approximation Algorithms and Online Mechanisms for Item Pricing Theory of Computing. 3: 179-195. DOI: 10.4086/Toc.2007.V003A009  0.628
2007 Balcan M, Blum A. Mechanism design, machine learning, and pricing problems Sigecom Exchanges. 7: 34-36. DOI: 10.1145/1345037.1345045  0.66
2007 Blum A, Chawla S, Karger DR, Lane T, Meyerson A, Minkoff M. Approximation Algorithms for Orienteering and Discounted-Reward TSP Siam Journal On Computing. 37: 653-670. DOI: 10.1137/050645464  0.581
2007 Blum A, Lugosi G, Simon HU. Introduction to the special issue on COLT 2006 Machine Learning. 69: 75-77. DOI: 10.1007/S10994-007-5027-5  0.394
2006 Blum A, Sandholm T, Zinkevich M. Online algorithms for market clearing Journal of the Acm. 53: 845-879. DOI: 10.1145/1183907.1183913  0.673
2006 Balcan MF, Blum A, Vempala S. Kernels as features: On kernels, margins, and low-dimensional mappings Machine Learning. 65: 79-94. DOI: 10.1007/S10994-006-7550-1  0.59
2006 Blum A. Random projection, margins, kernels, and feature-selection Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3940: 52-68. DOI: 10.1007/11752790_3  0.414
2005 Azar Y, Blum A, Bunde DP, Mansour Y. Combining Online Algorithms for Acceptance and Rejection Theory of Computing. 1: 105-117. DOI: 10.4086/Toc.2005.V001A006  0.436
2004 Blum A, Kalai A, Kleinberg J. Admission control to minimize rejections Internet Mathematics. 1: 165-176. DOI: 10.1080/15427951.2004.10129085  0.694
2004 Blum A, Kumar V, Rudra A, Wu F. Online learning in online auctions Theoretical Computer Science. 324: 137-146. DOI: 10.1016/J.Tcs.2004.05.012  0.417
2004 Blum A, Jackson J, Sandholm T, Zinkevich M. Preference Elicitation and Query Learning Journal of Machine Learning Research. 5: 649-667. DOI: 10.1007/978-3-540-45167-9_3  0.646
2003 Blum A, Kalai A, Wasserman H. Noise-tolerant learning, the parity problem, and the statistical query model Journal of the Acm. 50: 506-519. DOI: 10.1145/792538.792543  0.694
2003 Langford J, Blum A. Microchoice Bounds and Self Bounding Learning Algorithms Machine Learning. 51: 165-179. DOI: 10.1023/A:1022806918936  0.444
2000 Blum A, Karloff H, Rabani Y, Saks M. A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems Siam Journal On Computing. 30: 1624-1661. DOI: 10.1137/S0097539799351882  0.358
2000 Blum A, Chalasani P. An Online Algorithm for Improving Performance in Navigation Siam Journal On Computing. 29: 1907-1938. DOI: 10.1137/S0097539795290593  0.353
2000 Blum A, Burch C. On-line learning and the Metrical Task System problem Machine Learning. 39: 35-58. DOI: 10.1023/A:1007621832648  0.675
2000 Blum A, Konjevod G, Ravi R, Vempala S. Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems Theoretical Computer Science. 235: 25-42. DOI: 10.1016/S0304-3975(99)00181-4  0.333
1999 Mitchell JSB, Blum A, Chalasani P, Vempala S. A Constant-Factor Approximation Algorithm for the Geometric k -MST Problem in the Plane Siam Journal On Computing. 28: 771-781. DOI: 10.1137/S0097539796303299  0.401
1999 Awerbuch B, Azar Y, Blum A, Vempala S. New Approximation Guarantees for Minimum-Weight k -Trees and Prize-Collecting Salesmen Siam Journal On Computing. 28: 254-262. DOI: 10.1137/S009753979528826X  0.384
1999 Blum A, Ravi R, Vempala S. A Constant-Factor Approximation Algorithm for thek-MST Problem Journal of Computer and System Sciences. 58: 101-108. DOI: 10.1006/Jcss.1997.1542  0.445
1998 Blum A, Raghavan P. On a theory of computing symposia Sigact News. 29: 104-111. DOI: 10.1145/300307.300315  0.406
1998 Aizenstein H, Blum A, Khardon R, Kushilevitz E, Pitt L, Roth D. On Learning Read- k -Satisfy- j DNF Siam Journal On Computing. 27: 1515-1530. DOI: 10.1137/S0097539794274398  0.398
1998 Blum A. On-line Algorithms in Machine Learning Lecture Notes in Computer Science. 306-325. DOI: 10.1007/Bfb0029575  0.455
1998 Blum A, Chalasani P, Goldman SA, Slonim DK. Learning with Unreliable Boundary Queries Journal of Computer and System Sciences. 56: 209-222. DOI: 10.1006/Jcss.1997.1559  0.396
1997 Blum A, Raghavan P, Schieber B. Navigating in Unfamiliar Geometric Terrain Siam Journal On Computing. 26: 110-137. DOI: 10.1137/S0097539791194931  0.315
1997 Blum A. Empirical Support for Winnow and Weighted-MajorityAlgorithms: Results on a Calendar Scheduling Domain Machine Learning. 26: 5-23. DOI: 10.1023/A:1007335615132  0.415
1997 Blum A, Karger D. An Õ( n 3/14 )-coloring algorithm for 3-colorable graphs Information Processing Letters. 61: 49-53. DOI: 10.1016/S0020-0190(96)00190-1  0.339
1995 Blum A, Hellerstein L, Littlestone N. Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes Journal of Computer and System Sciences. 50: 32-40. DOI: 10.1006/Jcss.1995.1004  0.449
1995 Blum A, Spencer J. Coloring random and semi-random k -colorable graphs Journal of Algorithms. 19: 204-234. DOI: 10.1006/Jagm.1995.1034  0.326
1994 Blum A, Jiang T, Li M, Tromp J, Yannakakis M. Linear approximation of shortest superstrings Journal of the Acm. 41: 630-647. DOI: 10.1145/179812.179818  0.406
1994 Blum A. New Approximation Algorithms for Graph Coloring Journal of the Acm (Jacm). 41: 470-516. DOI: 10.1145/176584.176586  0.341
1992 Blum A. Learning Boolean Functions in an Infinite Attribute Space Machine Learning. 9: 373-386. DOI: 10.1023/A:1022653502461  0.444
Show low-probability matches.