☰

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.365
2020 Blum A. Technical perspective: Algorithm selection as a learning problem Communications of the Acm. 63: 86-86. DOI: 10.1145/3394623  0.449
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.31
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.737
2013 Balcan MF, Blum A, Gupta A. Clustering under approximation stability Journal of the Acm. 60. DOI: 10.1145/2450142.2450144  0.589
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.729
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.703
2010 Balcan MF, Blum A. A discriminative model for semi-supervised learning Journal of the Acm. 57. DOI: 10.1145/1706591.1706599  0.658
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.328
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.356
2008 Balcan M, Blum A, Mansour Y. Item pricing for revenue maximization Sigecom Exchanges. 7: 6. DOI: 10.1145/1486877.1486883  0.569
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.614
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.63
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.393
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.674
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.591
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.695
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.414
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.695
2003 Langford J, Blum A. Microchoice Bounds and Self Bounding Learning Algorithms Machine Learning. 51: 165-179. DOI: 10.1023/A:1022806918936  0.445
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.356
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.352
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.676
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.332
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.383
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.408
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.454
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.397
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.416
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.451
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.342
1992 Blum A. Learning Boolean Functions in an Infinite Attribute Space Machine Learning. 9: 373-386. DOI: 10.1023/A:1022653502461  0.446
Show low-probability matches.