default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAvrim Blum
Person information
- affiliation: Toyota Technological Institute at Chicago, IL, USA
- affiliation (former): Carnegie Mellon University, Pittsburgh, USA
- award (2021): Paris Kanellakis Award
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2025
[c172]Avrim Blum, Kavya Ravichandran:
Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem. ALT 2025: 228-245- [c171]Avrim Blum, Kavya Ravichandran:
A Model for Combinatorial Dictionary Learning and Inference. ALT 2025: 246-288 - [c170]Avrim Blum, Vaidehi Srinivas:
Competitive strategies to use "warm start" algorithms with predictions. SODA 2025: 3775-3801 - [i70]Avrim Blum, Emily Diana, Kavya Ravichandran, Alexander Williams Tolbert:
A Theoretical Model for Grit in Pursuing Ambitious Ends. CoRR abs/2503.02952 (2025) - [i69]Idan Attias, Avrim Blum, Keziah Naggita, Donya Saless, Dravyansh Sharma, Matthew R. Walter:
PAC Learning with Improvements. CoRR abs/2503.03184 (2025) - 2024
- [c169]Saba Ahmadi, Avrim Blum, Omar Montasser, Kevin M. Stangl:
Agnostic Multi-Robust Learning using ERM. AISTATS 2024: 2242-2250 - [c168]Avrim Blum, Princewill Okoroafor, Aadirupa Saha, Kevin M. Stangl:
On the Vulnerability of Fairness Constrained Learning to Malicious Noise. AISTATS 2024: 4096-4104 - [c167]Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj
, Aadirupa Saha, Yuanyuan Yang:
Dueling Optimization with a Monotone Adversary. ALT 2024: 221-243 - [c166]Avrim Blum, Melissa Dutz:
Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round. ITCS 2024: 18:1-18:18 - [i68]Avrim Blum, Melissa Dutz:
Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round. CoRR abs/2404.00150 (2024) - [i67]Avrim Blum, Kavya Ravichandran:
Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem. CoRR abs/2404.01198 (2024) - [i66]Keziah Naggita, Matthew R. Walter, Avrim Blum:
Learning Actionable Counterfactual Explanations in Large State Spaces. CoRR abs/2404.17034 (2024) - [i65]Vaidehi Srinivas, Avrim Blum:
Competitive strategies to use "warm start" algorithms with predictions. CoRR abs/2405.03661 (2024) - [i64]Saba Ahmadi, Siddharth Bhandari, Avrim Blum, Chen Dan, Prabhav Jain:
Distributional Adversarial Loss. CoRR abs/2406.03458 (2024) - [i63]Emily Diana, Alexander Williams Tolbert, Kavya Ravichandran, Avrim Blum:
Adaptive Algorithmic Interventions for Escaping Pessimism Traps in Dynamic Sequential Decisions. CoRR abs/2406.04462 (2024) - [i62]Avrim Blum, Kavya Ravichandran:
A Model for Combinatorial Dictionary Learning and Inference. CoRR abs/2407.18436 (2024) - [i61]Avrim Blum, Donya Saless:
Regularized Robustly Reliable Learners and Instance Targeted Attacks. CoRR abs/2410.10572 (2024) - [i60]Saba Ahmadi, Siddharth Bhandari, Avrim Blum:
Replicable Online Learning. CoRR abs/2411.13730 (2024) - 2023
- [j62]Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, Hongyang Zhang:
An Analysis of Robustness of Non-Lipschitz Networks. J. Mach. Learn. Res. 24: 98:1-98:43 (2023) - [c165]Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, Keziah Naggita:
Setting Fair Incentives to Maximize Improvement. FORC 2023: 5:1-5:22 - [c164]Han Shao, Lee Cohen, Avrim Blum, Yishay Mansour, Aadirupa Saha, Matthew R. Walter:
Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback. NeurIPS 2023 - [c163]Han Shao, Avrim Blum, Omar Montasser:
Strategic Classification under Unknown Personalized Manipulation. NeurIPS 2023 - [c162]Saba Ahmadi, Avrim Blum, Kunhe Yang:
Fundamental Bounds on Online Strategic Classification. EC 2023: 22-58 - [i59]Han Shao, Lee Cohen, Avrim Blum, Yishay Mansour, Aadirupa Saha, Matthew R. Walter:
Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback. CoRR abs/2302.03805 (2023) - [i58]Saba Ahmadi, Avrim Blum, Kunhe Yang:
Fundamental Bounds on Online Strategic Classification. CoRR abs/2302.12355 (2023) - [i57]Saba Ahmadi, Avrim Blum, Omar Montasser, Kevin Stangl:
Certifiable (Multi)Robustness Against Patch Attacks Using ERM. CoRR abs/2303.08944 (2023) - [i56]Han Shao, Avrim Blum, Omar Montasser:
Strategic Classification under Unknown Personalized Manipulation. CoRR abs/2305.16501 (2023) - [i55]Avrim Blum, Princewill Okoroafor, Aadirupa Saha, Kevin Stangl:
On the Vulnerability of Fairness Constrained Learning to Malicious Noise. CoRR abs/2307.11892 (2023) - [i54]Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, Yuanyuan Yang:
Dueling Optimization with a Monotone Adversary. CoRR abs/2311.11185 (2023) - 2022
- [c161]Maria-Florina Balcan, Avrim Blum, Steve Hanneke, Dravyansh Sharma:
Robustly-reliable learners under poisoning attacks. COLT 2022: 4498-4534 - [c160]Avrim Blum, Kevin Stangl, Ali Vakilian:
Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline. FAccT 2022: 1178-1193 - [c159]Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, Keziah Naggita:
On Classification of Strategic Agents Who Can Both Game and Improve. FORC 2022: 3:1-3:22 - [c158]Avrim Blum, Omar Montasser, Greg Shakhnarovich, Hongyang Zhang:
Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness. NeurIPS 2022 - [c157]Han Shao, Omar Montasser, Avrim Blum:
A Theory of PAC Learnability under Transformation Invariances. NeurIPS 2022 - [c156]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan:
Stochastic Vertex Cover with Few Queries. SODA 2022: 1808-1846 - [i53]Avrim Blum, Omar Montasser, Greg Shakhnarovich, Hongyang Zhang:
Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness. CoRR abs/2202.05920 (2022) - [i52]Han Shao, Omar Montasser, Avrim Blum:
A Theory of PAC Learnability under Transformation Invariances. CoRR abs/2202.07552 (2022) - [i51]Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, Keziah Naggita:
On classification of strategic agents who can both game and improve. CoRR abs/2203.00124 (2022) - [i50]Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, Keziah Naggita:
Setting Fair Incentives to Maximize Improvement. CoRR abs/2203.00134 (2022) - [i49]Maria-Florina Balcan, Avrim Blum, Steve Hanneke, Dravyansh Sharma:
Robustly-reliable learners under poisoning attacks. CoRR abs/2203.04160 (2022) - [i48]Avrim Blum, Kevin Stangl, Ali Vakilian:
Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline. CoRR abs/2203.07513 (2022) - 2021
- [c155]Avrim Blum, Shelby Heinecke, Lev Reyzin:
Communication-Aware Collaborative Learning. AAAI 2021: 6786-6793 - [c154]Avrim Blum, Chen Dan, Saeed Seddighin:
Learning Complexity of Simulated Annealing. AISTATS 2021: 1540-1548 - [c153]Avrim Blum, Steve Hanneke, Jian Qian, Han Shao:
Robust learning under clean-label attack. COLT 2021: 591-634 - [c152]Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, Han Shao:
One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning. ICML 2021: 1005-1014 - [c151]Naren Manoj, Avrim Blum:
Excess Capacity and Backdoor Poisoning. NeurIPS 2021: 20373-20384 - [c150]Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, Keziah Naggita:
The Strategic Perceptron. EC 2021: 6-25 - [c149]Avrim Blum, Paul Gölz:
Incentive-Compatible Kidney Exchange in a Slightly Semi-Random Model. EC 2021: 138-156 - [i47]Avrim Blum, Steve Hanneke, Jian Qian, Han Shao:
Robust learning under clean-label attack. CoRR abs/2103.00671 (2021) - [i46]Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, Han Shao:
One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning. CoRR abs/2103.03228 (2021) - [i45]Avrim Blum, Paul Gölz:
Incentive-Compatible Kidney Exchange in a Slightly Semi-Random Model. CoRR abs/2106.11387 (2021) - [i44]Naren Sarayu Manoj, Avrim Blum:
Excess Capacity and Backdoor Poisoning. CoRR abs/2109.00685 (2021) - [i43]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan:
Stochastic Vertex Cover with Few Queries. CoRR abs/2112.05415 (2021) - 2020
- [j61]Avrim Blum:
Technical perspective: Algorithm selection as a learning problem. Commun. ACM 63(6): 86 (2020) - [j60]Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, Ankit Sharma:
Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries. Oper. Res. 68(1): 16-34 (2020) - [j59]Avrim Blum, Travis Dick, Naren Manoj, Hongyang Zhang:
Random Smoothing Might be Unable to Certify L∞ Robustness for High-Dimensional Images. J. Mach. Learn. Res. 21: 211:1-211:21 (2020) - [j58]Maria-Florina Balcan, Avrim Blum, Vaishnavh Nagarajan:
Lifelong learning in costly feature spaces. Theor. Comput. Sci. 808: 14-37 (2020) - [c148]Arturs Backurs, Avrim Blum, Neha Gupta:
Active Local Learning. COLT 2020: 363-390 - [c147]Avrim Blum, Kevin Stangl:
Recovering from Biased Data: Can Fairness Constraints Improve Accuracy? FORC 2020: 3:1-3:20 - [c146]Avrim Blum, Thodoris Lykouris:
Advancing Subgroup Fairness via Sleeping Experts. ITCS 2020: 55:1-55:24 - [c145]Avrim Blum, Han Shao:
Online Learning with Primary and Secondary Losses. NeurIPS 2020 - [p2]Avrim Blum:
Approximation Stability and Proxy Objectives. Beyond the Worst-Case Analysis of Algorithms 2020: 120-139 - [i42]Avrim Blum, Travis Dick, Naren Manoj, Hongyang Zhang:
Random Smoothing Might be Unable to Certify 𝓁∞ Robustness for High-Dimensional Images. CoRR abs/2002.03517 (2020) - [i41]Avrim Blum, Chen Dan, Saeed Seddighin:
Learning Complexity of Simulated Annealing. CoRR abs/2003.02981 (2020) - [i40]Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, Keziah Naggita:
The Strategic Perceptron. CoRR abs/2008.01710 (2020) - [i39]Arturs Backurs, Avrim Blum, Neha Gupta:
Active Local Learning. CoRR abs/2008.13374 (2020) - [i38]Avrim Blum, Yishay Mansour:
Kidney exchange and endless paths: On the optimal use of an altruistic donor. CoRR abs/2010.01645 (2020) - [i37]Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, Hongyang Zhang:
On the Power of Abstention and Data-Driven Decision Making for Adversarial Robustness. CoRR abs/2010.06154 (2020) - [i36]Avrim Blum, Han Shao:
Online Learning with Primary and Secondary Losses. CoRR abs/2010.14670 (2020) - [i35]Avrim Blum, Shelby Heinecke, Lev Reyzin:
Communication-Aware Collaborative Learning. CoRR abs/2012.10569 (2020)
2010 – 2019
- 2019
- [j57]Avrim Blum, Sariel Har-Peled, Benjamin Raichel:
Sparse Approximation via Generating Point Sets. ACM Trans. Algorithms 15(3): 32:1-32:16 (2019) - [c144]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin:
Optimal Strategies of Blotto Games: Beyond Convexity. EC 2019: 597-616 - [c143]Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan:
Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem. ESA 2019: 7:1-7:16 - [c142]Avrim Blum, Nika Haghtalab, MohammadTaghi Hajiaghayi, Saeed Seddighin:
Computing Stackelberg Equilibria of Large General-Sum Games. SAGT 2019: 168-182 - [i34]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin:
Optimal Strategies of Blotto Games: Beyond Convexity. CoRR abs/1901.04153 (2019) - [i33]Avrim Blum, Nika Haghtalab, MohammadTaghi Hajiaghayi, Saeed Seddighin:
Computing Stackelberg Equilibria of Large General-Sum Games. CoRR abs/1909.03319 (2019) - [i32]Avrim Blum, Thodoris Lykouris:
Advancing subgroup fairness via sleeping experts. CoRR abs/1909.08375 (2019) - [i31]Avrim Blum, Kevin Stangl:
Recovering from Biased Data: Can Fairness Constraints Improve Accuracy? CoRR abs/1912.01094 (2019) - 2018
- [j56]Avrim Blum, Yishay Mansour, Jamie Morgenstern:
Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions. ACM Trans. Economics and Comput. 6(3-4): 13:1-13:20 (2018) - [c141]Avrim Blum, Nika Haghtalab:
Algorithms for Generalized Topic Modeling. AAAI 2018: 2730-2737 - [c140]Maria-Florina Balcan, Avrim Blum, Shang-Tse Chen:
Diversified Strategies for Mitigating Adversarial Attacks in Multiagent Systems. AAMAS 2018: 407-415 - [c139]Avrim Blum, Lunjia Hu:
Active Tolerant Testing. COLT 2018: 474-497 - [c138]Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, Lin F. Yang:
Approximate Convex Hull of Data Streams. ICALP 2018: 21:1-21:13 - [c137]Avrim Blum, Yishay Mansour:
On Price versus Quality. ITCS 2018: 16:1-16:12 - [c136]Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, Nati Srebro:
On preserving non-discrimination when combining expert advice. NeurIPS 2018: 8386-8397 - [c135]Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark:
From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. SODA 2018: 2291-2310 - [e2]Avrim Blum:
10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA. LIPIcs 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-095-8 [contents] - [i30]Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan:
Bilu-Linial stability, certified algorithms and the Independent Set problem. CoRR abs/1810.08414 (2018) - [i29]Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, Nathan Srebro:
On preserving non-discrimination when combining expert advice. CoRR abs/1810.11829 (2018) - 2017
- [c134]Maria-Florina Balcan, Avrim Blum, Vaishnavh Nagarajan:
Lifelong Learning in Costly Feature Spaces. ALT 2017: 250-287 - [c133]Pranjal Awasthi, Avrim Blum, Nika Haghtalab, Yishay Mansour:
Efficient PAC Learning from the Crowd. COLT 2017: 127-150 - [c132]Avrim Blum, Yishay Mansour:
Efficient Co-Training of Linear Separators under Weak Dependence. COLT 2017: 302-318 - [c131]Avrim Blum, Nika Haghtalab, Ariel D. Procaccia, Mingda Qiao:
Collaborative PAC Learning. NIPS 2017: 2392-2401 - [c130]Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel D. Procaccia, Eviatar B. Procaccia, Rohit Vaish:
Opting Into Optimal Matchings. SODA 2017: 2351-2363 - [i28]Pranjal Awasthi, Avrim Blum, Nika Haghtalab, Yishay Mansour:
Efficient PAC Learning from the Crowd. CoRR abs/1703.07432 (2017) - [i27]Maria-Florina Balcan, Avrim Blum, Vaishnavh Nagarajan:
Lifelong Learning in Costly Feature Spaces. CoRR abs/1706.10271 (2017) - [i26]Avrim Blum, Lunjia Hu:
Active Tolerant Testing. CoRR abs/1711.00388 (2017) - [i25]Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, Lin F. Yang:
Approximate Convex Hull of Data Streams. CoRR abs/1712.04564 (2017) - 2016
- [c129]Rohit Vaish, Neeldhara Misra, Shivani Agarwal, Avrim Blum:
On the Computational Hardness of Manipulating Pairwise Voting Rules. AAMAS 2016: 358-367 - [c128]Avrim Blum, Sariel Har-Peled, Benjamin Raichel:
Sparse Approximation via Generating Point Sets. SODA 2016: 548-557 - [r1]Avrim Blum:
Semi-supervised Learning. Encyclopedia of Algorithms 2016: 1936-1941 - [i24]Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel D. Procaccia, Eviatar B. Procaccia, Rohit Vaish:
Opting Into Optimal Matchings. CoRR abs/1609.04051 (2016) - [i23]Avrim Blum, Nika Haghtalab:
Generalized Topic Modeling. CoRR abs/1611.01259 (2016) - 2015
- [j55]Avrim Blum, Philip M. Long:
Special Issue on New Theoretical Challenges in Machine Learning. Algorithmica 72(1): 191-192 (2015) - [c127]Avrim Blum, Yishay Mansour, Jamie Morgenstern:
Learning Valuation Distributions from Partial Observation. AAAI 2015: 798-804 - [c126]Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala:
Efficient Representations for Lifelong Learning and Autoencoding. COLT 2015: 191-210 - [c125]Avrim Blum, Moritz Hardt:
The Ladder: A Reliable Leaderboard for Machine Learning Competitions. ICML 2015: 1006-1014 - [c124]Avrim Blum, Jamie Morgenstern, Ankit Sharma, Adam D. Smith:
Privacy-Preserving Public Information for Sequential Games. ITCS 2015: 173-180 - [c123]Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, Ariel D. Procaccia:
Commitment Without Regrets: Online Learning in Stackelberg Security Games. EC 2015: 61-78 - [c122]Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, Ankit Sharma:
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries. EC 2015: 325-342 - [c121]Avrim Blum, Yishay Mansour, Jamie Morgenstern:
Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions. EC 2015: 601-618 - [c120]Avrim Blum, Yishay Mansour, Liu Yang:
Online Allocation and Pricing with Economies of Scale. WINE 2015: 159-172 - [i22]Avrim Blum, Moritz Hardt:
The Ladder: A Reliable Leaderboard for Machine Learning Competitions. CoRR abs/1502.04585 (2015) - [i21]Avrim Blum, Sariel Har-Peled, Benjamin Raichel:
Sparse Approximation via Generating Point Sets. CoRR abs/1507.02574 (2015) - 2014
- [c119]Avrim Blum, Nika Haghtalab, Ariel D. Procaccia:
Lazy Defenders Are Almost Optimal against Diligent Attackers. AAAI 2014: 573-579 - [c118]Avrim Blum, Nika Haghtalab, Ariel D. Procaccia:
Learning Optimal Commitment to Overcome Insecurity. NIPS 2014: 1826-1834 - [c117]Maria-Florina Balcan, Christopher Berlind, Avrim Blum, Emma Cohen, Kaushik Patnaik, Le Song:
Active Learning and Best-Response Dynamics. NIPS 2014: 2222-2230 - [c116]Pranjal Awasthi, Avrim Blum, Or Sheffet, Aravindan Vijayaraghavan:
Learning Mixtures of Ranking Models. NIPS 2014: 2609-2617 - [c115]Emmanouil Antonios Platanios, Avrim Blum, Tom M. Mitchell:
Estimating Accuracy from Unlabeled Data. UAI 2014: 682-691 - [i20]Avrim Blum, Jamie Morgenstern, Ankit Sharma, Adam D. Smith:
Privacy-Preserving Public Information for Sequential Games. CoRR abs/1402.4488 (2014) - [i19]Maria-Florina Balcan, Christopher Berlind, Avrim Blum, Emma Cohen, Kaushik Patnaik, Le Song:
Active Learning and Best-Response Dynamics. CoRR abs/1406.6633 (2014) - [i18]Avrim Blum, Yishay Mansour, Jamie Morgenstern:
Learning Valuation Distributions from Partial Observation. CoRR abs/1407.2855 (2014) - [i17]Avrim Blum, Nika Haghtalab, Ariel D. Procaccia, Ankit Sharma:
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries. CoRR abs/1407.4094 (2014) - [i16]Avrim Blum, Yishay Mansour, Jamie Morgenstern:
Learning What's going on: reconstructing preferences and priorities from opaque transactions. CoRR abs/1408.6575 (2014) - [i15]Pranjal Awasthi, Avrim Blum, Or Sheffet, Aravindan Vijayaraghavan:
Learning Mixtures of Ranking Models. CoRR abs/1410.8750 (2014) - [i14]Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala:
Efficient Representations for Life-Long Learning and Autoencoding. CoRR abs/1411.1490 (2014) - 2013
- [j54]Maria-Florina Balcan, Avrim Blum, Anupam Gupta:
Clustering under approximation stability. J. ACM 60(2): 8:1-8:34 (2013) - [j53]Avrim Blum, Katrina Ligett, Aaron Roth:
A learning theory approach to noninteractive database privacy. J. ACM 60(2): 12:1-12:25 (2013) - [j52]Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior. SIAM J. Comput. 42(1): 230-264 (2013) - [j51]Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
The Price of Uncertainty. ACM Trans. Economics and Comput. 1(3): 15:1-15:29 (2013) - [c114]Avrim Blum, Aaron Roth:
Fast Private Data Release Algorithms for Sparse Queries. APPROX-RANDOM 2013: 395-410 - [c113]Nina Balcan, Avrim Blum, Yishay Mansour:
Exploiting Ontology Structures and Unlabeled Data for Learning. ICML (3) 2013: 1112-1120 - [c112]Liu Yang, Avrim Blum, Jaime G. Carbonell:
Learnability of DNF with representation-specific queries. ITCS 2013: 37-46 - [c111]Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet:
Differentially private data analysis of social networks via restricted sensitivity. ITCS 2013: 87-96 - [c110]Avrim Blum, Anupam Gupta, Ariel D. Procaccia, Ankit Sharma:
Harnessing the power of two crossmatches. EC 2013: 123-140 - 2012
- [j50]Pranjal Awasthi, Avrim Blum, Or Sheffet:
Center-based clustering under perturbation stability. Inf. Process. Lett. 112(1-2): 49-54 (2012) - [c109]Pranjal Awasthi, Avrim Blum, Jamie Morgenstern, Or Sheffet:
Additive Approximation for Near-Perfect Phylogeny Construction. APPROX-RANDOM 2012: 25-36 - [c108]Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang:
Active Property Testing. FOCS 2012: 21-30 - [c107]Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet:
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy. FOCS 2012: 410-419 - [c106]Maria-Florina Balcan, Avrim Blum, Shai Fine, Yishay Mansour:
Distributed Learning, Communication Complexity and Privacy. COLT 2012: 26.1-26.22 - [i13]Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet:
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy. CoRR abs/1204.2136 (2012) - [i12]Maria-Florina Balcan, Avrim Blum, Shai Fine, Yishay Mansour:
Distributed Learning, Communication Complexity and Privacy. CoRR abs/1204.3514 (2012) - [i11]Pranjal Awasthi, Avrim Blum, Jamie Morgenstern, Or Sheffet:
Additive Approximation for Near-Perfect Phylogeny Construction. CoRR abs/1206.3334 (2012) - [i10]Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet:
Differentially Private Data Analysis of Social Networks via Restricted Sensitivity. CoRR abs/1208.4586 (2012) - 2011
- [c105]Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma:
Welfare and Profit Maximization with Production Costs. FOCS 2011: 77-86 - [i9]Avrim Blum, Katrina Ligett, Aaron Roth:
A Learning Theory Approach to Non-Interactive Database Privacy. CoRR abs/1109.2229 (2011) - [i8]Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma:
Welfare and Profit Maximization with Production Costs. CoRR abs/1110.4992 (2011) - [i7]Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang:
Active Testing. CoRR abs/1111.0897 (2011) - [i6]Avrim Blum, Aaron Roth:
Fast Private Data Release Algorithms for Sparse Queries. CoRR abs/1111.6842 (2011) - 2010
- [j49]Maria-Florina Balcan, Avrim Blum:
A discriminative model for semi-supervised learning. J. ACM 57(3): 19:1-19:46 (2010) - [j48]Avrim Blum, Eyal Even-Dar, Katrina Ligett:
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games. Theory Comput. 6(1): 179-199 (2010) - [c104]Pranjal Awasthi, Avrim Blum, Or Sheffet:
Improved Guarantees for Agnostic Learning of Disjunctions. COLT 2010: 359-367 - [c103]Pranjal Awasthi, Avrim Blum, Or Sheffet:
Stability Yields a PTAS for k-Median and k-Means Clustering. FOCS 2010: 309-318 - [c102]Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior. ICS 2010: 200-213 - [c101]Amin Sayedi, Morteza Zadimoghaddam, Avrim Blum:
Trading off Mistakes and Don't-Know Predictions. NIPS 2010: 2092-2100 - [c100]Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, Santosh S. Vempala:
On Nash-Equilibria of Approximation-Stable Games. SAGT 2010: 78-89 - [i5]Pranjal Awasthi, Avrim Blum, Or Sheffet:
Center-based Clustering under Perturbation Stability. CoRR abs/1009.3594 (2010)
2000 – 2009
- 2009
- [j47]Sharath R. Cholleti, Sally A. Goldman, Avrim Blum, David G. Politte, Steven Don, Kirk E. Smith, Fred W. Prior:
Veritas: Combining Expert Opinions without Labeled Data. Int. J. Artif. Intell. Tools 18(5): 633-651 (2009) - [c99]Shobha Venkataraman, Avrim Blum, Dawn Song, Subhabrata Sen, Oliver Spatscheck:
Tracking Dynamic Sources of Malicious Activity at Internet Scale. NIPS 2009: 1946-1954 - [c98]Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
The price of uncertainty. EC 2009: 285-294 - [c97]Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Improved equilibria via public service advertising. SODA 2009: 728-737 - [c96]Maria-Florina Balcan, Avrim Blum, Anupam Gupta:
Approximate clustering without the approximation. SODA 2009: 1068-1077 - 2008
- [j46]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) - [j45]Maria-Florina Balcan, Avrim Blum, Nathan Srebro:
A theory of learning with similarity functions. Mach. Learn. 72(1-2): 89-112 (2008) - [j44]Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Item pricing for revenue maximization. SIGecom Exch. 7(3) (2008) - [c95]Maria-Florina Balcan, Avrim Blum:
Clustering with Interactive Feedback. ALT 2008: 316-328 - [c94]Maria-Florina Balcan, Avrim Blum, Nathan Srebro:
Improved Guarantees for Learning via Similarity Functions. COLT 2008: 287-298 - [c93]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 - [c92]Shobha Venkataraman, Avrim Blum, Dawn Song:
Limits of Learning-based Signature Generation with Adversaries. NDSS 2008 - [c91]Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Item pricing for revenue maximization. EC 2008: 50-59 - [c90]Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, Aaron Roth:
Regret minimization and the price of total anarchy. STOC 2008: 373-382 - [c89]Avrim Blum, Katrina Ligett, Aaron Roth:
A learning theory approach to non-interactive database privacy. STOC 2008: 609-618 - [c88]Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala:
A discriminative framework for clustering via similarity functions. STOC 2008: 671-680 - 2007
- [j43]Avrim Blum, Yishay Mansour:
From External to Internal Regret. J. Mach. Learn. Res. 8: 1307-1324 (2007) - [j42]Avrim Blum, Gábor Lugosi, Hans Ulrich Simon:
Introduction to the special issue on COLT 2006. Mach. Learn. 69(2-3): 75-77 (2007) - [j41]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) - [j40]Maria-Florina Balcan, Avrim Blum:
Mechanism design, machine learning, and pricing problems. SIGecom Exch. 7(1): 34-36 (2007) - [j39]Maria-Florina Balcan, Avrim Blum:
Approximation Algorithms and Online Mechanisms for Item Pricing. Theory Comput. 3(1): 179-195 (2007) - [c87]Avrim Blum:
A Theory of Similarity Functions for Learning and Clustering. ALT 2007: 9 - [c86]Avrim Blum, Maria-Florina Balcan:
Open Problems in Efficient Semi-supervised PAC Learning. COLT 2007: 622-624 - [c85]Avrim Blum:
A Theory of Similarity Functions for Learning and Clustering. Discovery Science 2007: 39 - [c84]Avrim Blum, Amin Coja-Oghlan, Alan M. Frieze, Shuheng Zhou:
Separating Populations with Wide Data: A Spectral Analysis. ISAAC 2007: 439-451 - [c83]David J. Abraham, Avrim Blum, Tuomas Sandholm:
Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges. EC 2007: 295-304 - [c82]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 - 2006
- [j38]Avrim Blum, Tuomas Sandholm, Martin Zinkevich:
Online algorithms for market clearing. J. ACM 53(5): 845-879 (2006) - [j37]Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala:
Kernels as features: On kernels, margins, and low-dimensional mappings. Mach. Learn. 65(1): 79-94 (2006) - [c81]Avrim Blum, T.-H. Hubert Chan, Mugizi Robert Rwebangira:
A Random-Surfer Web-Graph Model. ANALCO 2006: 238-246 - [c80]Shobha Venkataraman, Juan Caballero, Dawn Song, Avrim Blum, Jennifer Yates:
Black Box Anomaly Detection: Is It Utopian?. HotNets 2006 - [c79]Maria-Florina Balcan, Avrim Blum:
On a theory of learning with similarity functions. ICML 2006: 73-80 - [c78]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 - [c77]Maria-Florina Balcan, Avrim Blum:
Approximation algorithms and online mechanisms for item pricing. EC 2006: 29-35 - [p1]Maria-Florina Balcan, Avrim Blum:
An Augmented PAC Model for Semi-Supervised Learning. Semi-Supervised Learning 2006: 396-419 - 2005
- [j36]Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour:
Combining Online Algorithms for Acceptance and Rejection. Theory Comput. 1(1): 105-117 (2005) - [c76]Maria-Florina Balcan, Avrim Blum:
A PAC-Style Model for Learning from Labeled and Unlabeled Data. COLT 2005: 111-126 - [c75]Avrim Blum, Yishay Mansour:
From External to Internal Regret. COLT 2005: 621-636 - [c74]Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour:
Mechanism Design via Machine Learning. FOCS 2005: 605-614 - [c73]Shobha Venkataraman, Dawn Xiaodong Song, Phillip B. Gibbons, Avrim Blum:
New Streaming Algorithms for Fast Detection of Superspreaders. NDSS 2005 - [c72]Avrim Blum, Cynthia Dwork, Frank McSherry, Kobbi Nissim:
Practical privacy: the SuLQ framework. PODS 2005: 128-138 - [c71]Avrim Blum:
Random Projection, Margins, Kernels, and Feature-Selection. SLSFS 2005: 52-68 - [c70]Avrim Blum, Jason D. Hartline:
Near-optimal online auctions. SODA 2005: 1156-1163 - 2004
- [j35]Avrim Blum, Jeffrey C. Jackson, Tuomas Sandholm, Martin Zinkevich:
Preference Elicitation and Query Learning. J. Mach. Learn. Res. 5: 649-667 (2004) - [j34]Nikhil Bansal, Avrim Blum, Shuchi Chawla:
Correlation Clustering. Mach. Learn. 56(1-3): 89-113 (2004) - [j33]Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu:
Online learning in online auctions. Theor. Comput. Sci. 324(2-3): 137-146 (2004) - [c69]Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala:
On Kernels, Margins, and Low-Dimensional Mappings. ALT 2004: 194-205 - [c68]H. Brendan McMahan, Avrim Blum:
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. COLT 2004: 109-123 - [c67]Avrim Blum, John D. Lafferty, Mugizi Robert Rwebangira, Rajashekar Reddy:
Semi-supervised learning using randomized mincuts. ICML 2004 - [c66]Maria-Florina Balcan, Avrim Blum, Ke Yang:
Co-Training and Expansion: Towards Bridging Theory and Practice. NIPS 2004: 89-96 - [c65]Avrim Blum, Dawn Xiaodong Song, Shobha Venkataraman:
Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds. RAID 2004: 258-277 - [c64]Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson:
Approximation algorithms for deadline-TSP and vehicle routing with time-windows. STOC 2004: 166-174 - 2003
- [j32]Avrim Blum, Shuchi Chawla, Adam Kalai:
Static Optimality and Dynamic Search-Optimality in Lists and Trees. Algorithmica 36(3): 249-260 (2003) - [j31]Avrim Blum, Adam Tauman Kalai, Jon M. Kleinberg:
Admission Control to Minimize Rejections. Internet Math. 1(2): 165-176 (2003) - [j30]Avrim Blum, Adam Kalai, Hal Wasserman:
Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4): 506-519 (2003) - [j29]John Langford, Avrim Blum:
Microchoice Bounds and Self Bounding Learning Algorithms. Mach. Learn. 51(2): 165-179 (2003) - [c63]Ke Yang, Avrim Blum:
On Statistical Query Sampling and NMR Quantum Computing. CCC 2003: 194- - [c62]Avrim Blum, Jeffrey C. Jackson, Tuomas Sandholm, Martin Zinkevich:
Preference Elicitation and Query Learning. COLT 2003: 13-25 - [c61]Avrim Blum, John Langford:
PAC-MDL Bounds. COLT 2003: 344-357 - [c60]Avrim Blum:
Learning a Function of r Relevant Variables. COLT 2003: 731-733 - [c59]Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere:
Scheduling for Flow-Time with Admission Control. ESA 2003: 43-54 - [c58]Avrim Blum:
Machine Learning: My Favorite Results, Directions, and Open Problems. FOCS 2003: 2- - [c57]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 - [c56]H. Brendan McMahan, Geoffrey J. Gordon, Avrim Blum:
Planning in the Presence of Cost Functions Controlled by an Adversary. ICML 2003: 536-543 - [c55]Martin Zinkevich, Avrim Blum, Tuomas Sandholm:
On polynomial-time preference elicitation with value queries. EC 2003: 176-185 - [c54]Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu:
Online learning in online auctions. SODA 2003: 202-204 - [c53]Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson:
Online oblivious routing. SPAA 2003: 44-49 - [c52]Yossi Azar, Avrim Blum, Yishay Mansour:
Combining online algorithms for rejection and acceptance. SPAA 2003: 159-163 - [i4]Avrim Blum, Ke Yang:
On Statistical Query Sampling and NMR Quantum Computing. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [c51]Nikhil Bansal, Avrim Blum, Shuchi Chawla:
Correlation Clustering. FOCS 2002: 238- - [c50]Avrim Blum, Shuchi Chawla, Adam Kalai:
Static optimality and dynamic search-optimality in lists and trees. SODA 2002: 1-8 - [c49]Avrim Blum, John Dunagan:
Smoothed analysis of the perceptron algorithm for linear programming. SODA 2002: 905-914 - [c48]Avrim Blum, Tuomas Sandholm, Martin Zinkevich:
Online algorithms for market clearing. SODA 2002: 971-980 - 2001
- [c47]Avrim Blum, Shuchi Chawla:
Learning from Labeled and Unlabeled Data using Graph Mincuts. ICML 2001: 19-26 - [c46]Avrim Blum, Adam Kalai, Jon M. Kleinberg:
Admission Control to Minimize Rejections. WADS 2001: 155-164 - 2000
- [j28]Avrim Blum, Carl Burch:
On-line Learning and the Metrical Task System Problem. Mach. Learn. 39(1): 35-58 (2000) - [j27]Avrim Blum, Prasad Chalasani:
An Online Algorithm for Improving Performance in Navigation. SIAM J. Comput. 29(6): 1907-1938 (2000) - [j26]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) - [j25]Avrim Blum, Goran Konjevod, R. Ravi, Santosh S. Vempala:
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theor. Comput. Sci. 235(1): 25-42 (2000) - [c45]Joseph O'Sullivan, John Langford, Rich Caruana, Avrim Blum:
FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness. ICML 2000: 703-710 - [c44]Avrim Blum, Adam Kalai, Hal Wasserman:
Noise-tolerant learning, the parity problem, and the statistical query model. STOC 2000: 435-440 - [i3]Avrim Blum, Adam Kalai, Hal Wasserman:
Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model. CoRR cs.LG/0010022 (2000)
1990 – 1999
- 1999
- [j24]Avrim Blum, R. Ravi, Santosh S. Vempala:
A Constant-Factor Approximation Algorithm for the k-MST Problem. J. Comput. Syst. Sci. 58(1): 101-108 (1999) - [j23]Avrim Blum, Adam Kalai:
Universal Portfolios With and Without Transaction Costs. Mach. Learn. 35(3): 193-205 (1999) - [c43]Avrim Blum, Adam Kalai, John Langford:
Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation. COLT 1999: 203-208 - [c42]John Langford, Avrim Blum:
Microchoice Bounds and Self Bounding Learning Algorithms. COLT 1999: 209-214 - [c41]Avrim Blum, John Langford:
Probabilistic Planning in the Graphplan Framework. ECP 1999: 319-332 - [c40]Avrim Blum, Carl Burch, Adam Kalai:
Finely-Competitive Paging. FOCS 1999: 450-458 - [c39]Adam Kalai, Stanley F. Chen, Avrim Blum, Ronald Rosenfeld:
On-line algorithms for combining language models. ICASSP 1999: 745-748 - 1998
- [j22]Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Algorithmica 22(1/2): 35-52 (1998) - [j21]Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim:
Learning with Unreliable Boundary Queries. J. Comput. Syst. Sci. 56(2): 209-222 (1998) - [j20]Avrim Blum, Adam Kalai:
A Note on Learning from Multiple-Instance Examples. Mach. Learn. 30(1): 23-29 (1998) - [j19]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) - [j18]Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala:
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen. SIAM J. Comput. 28(1): 254-262 (1998) - [j17]Joseph S. B. Mitchell, Avrim Blum, Prasad Chalasani, Santosh S. Vempala:
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane. SIAM J. Comput. 28(3): 771-781 (1998) - [j16]Avrim Blum, Prabhakar Raghavan:
On a theory of computing symposia. SIGACT News 29(3): 104-111 (1998) - [c38]Avrim Blum, Tom M. Mitchell:
Combining Labeled and Unlabeled Data with Co-Training. COLT 1998: 92-100 - [c37]Avrim Blum, Carl Burch, John Langford:
On Learning Monotone Boolean Functions. FOCS 1998: 408-415 - [c36]Avrim Blum, Goran Konjevod, R. Ravi, Santosh S. Vempala:
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. STOC 1998: 100-105 - 1997
- [j15]Avrim Blum, Merrick L. Furst:
Fast Planning Through Planning Graph Analysis. Artif. Intell. 90(1-2): 281-300 (1997) - [j14]Avrim Blum, Pat Langley:
Selection of Relevant Features and Examples in Machine Learning. Artif. Intell. 97(1-2): 245-271 (1997) - [j13]Avrim Blum, David R. Karger:
An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs. Inf. Process. Lett. 61(1): 49-53 (1997) - [j12]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) - [j11]Avrim Blum:
Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain. Mach. Learn. 26(1): 5-23 (1997) - [j10]Avrim Blum, Prabhakar Raghavan, Baruch Schieber:
Navigating in Unfamiliar Geometric Terrain. SIAM J. Comput. 26(1): 110-137 (1997) - [c35]Avrim Blum, Carl Burch:
On-line Learning and the Metrical Task System Problem. COLT 1997: 45-53 - [c34]Avrim Blum, Adam Kalai:
Universal Portfolios With and Without Transaction Costs. COLT 1997: 309-313 - [c33]Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins:
A polylog(n)-Competitive Algorithm for Metrical Task Systems. STOC 1997: 711-719 - 1996
- [c32]Avrim Blum:
On-line Algorithms in Machine Learning. Online Algorithms 1996: 306-325 - [c31]Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala:
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS 1996: 330-338 - [c30]Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosén, Michael E. Saks:
Randomized Robot Navigation Algorithms. SODA 1996: 75-84 - [c29]Avrim Blum, R. Ravi, Santosh S. Vempala:
A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract). STOC 1996: 442-448 - [e1]Avrim Blum, Michael J. Kearns:
Proceedings of the Ninth Annual Conference on Computational Learning Theory, COLT 1996, Desenzano del Garda, Italy, June 28-July 1, 1996. ACM 1996, ISBN 0-89791-811-8 [contents] - 1995
- [j9]Avrim Blum, Joel Spencer:
Coloring Random and Semi-Random k-Colorable Graphs. J. Algorithms 19(2): 204-234 (1995) - [j8]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) - [j7]Avrim Blum, Steven Rudich:
Fast Learning of k-Term DNF Formulas with Queries. J. Comput. Syst. Sci. 51(3): 367-373 (1995) - [c28]Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim:
Learning with Unreliable Boundary Queries. COLT 1995: 98-107 - [c27]Avrim Blum:
Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain. ICML 1995: 64-72 - [c26]Avrim Blum, Merrick L. Furst:
Fast Planning Through Planning Graph Analysis. IJCAI 1995: 1636-1642 - [c25]Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala:
Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. STOC 1995: 277-283 - [c24]Avrim Blum, Prasad Chalasani, Santosh S. Vempala:
A constant-factor approximation for the k-MST problem in the plane. STOC 1995: 294-302 - 1994
- [j6]Avrim Blum:
New Approximation Algorithms for Graph Coloring. J. ACM 41(3): 470-516 (1994) - [j5]Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis:
Linear Approximation of Shortest Superstrings. J. ACM 41(4): 630-647 (1994) - [j4]Avrim Blum:
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain. SIAM J. Comput. 23(5): 990-1000 (1994) - [c23]Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth:
On Learning Read-k-Satisfy-j DNF. COLT 1994: 110-117 - [c22]Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan:
The minimum latency problem. STOC 1994: 163-171 - [c21]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 - [i2]Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan:
On the minimum latency problem. CoRR abs/math/9409223 (1994) - [i1]Avrim Blum, Prasad Chalasani:
An on-line algorithm for improving performance in navigation. CoRR abs/math/9409224 (1994) - 1993
- [c20]Avrim Blum, Prasad Chalasani, Jeffrey C. Jackson:
On Learning Embedded Symmetric Concepts. COLT 1993: 337-346 - [c19]Avrim Blum, Merrick L. Furst, Michael J. Kearns, Richard J. Lipton:
Cryptographic Primitives Based on Hard Learning Problems. CRYPTO 1993: 278-291 - [c18]Avrim Blum, Prasad Chalasani:
An On-Line Algorithm for Improving Performance in Navigation. FOCS 1993: 2-11 - [c17]Avrim Blum, Ravi Kannan:
Learning an Intersection of k Halfspaces over a Uniform Distribution. FOCS 1993: 312-320 - [c16]Avrim Blum, Ronald L. Rivest:
Training a 3-Node Neural Network is NP-Complete. Machine Learning: From Theory to Applications 1993: 9-28 - 1992
- [j3]Avrim Blum:
Rank-r Decision Trees are a Subclass of r-Decision Lists. Inf. Process. Lett. 42(4): 183-185 (1992) - [j2]Avrim Blum:
Learning Boolean Functions in an Infinite Attribute Space. Mach. Learn. 9: 373-386 (1992) - [j1]Avrim Blum, Ronald L. Rivest:
Training a 3-node neural network is NP-complete. Neural Networks 5(1): 117-127 (1992) - [c15]Avrim Blum, Prasad Chalasani:
Learning Switching Concepts. COLT 1992: 231-242 - [c14]Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks:
A Decomposition Theorem and Bounds for Randomized Server Problems. FOCS 1992: 197-207 - [c13]Avrim Blum, Steven Rudich:
Fast Learning of k-Term DNF Formulas with Queries. STOC 1992: 382-389 - 1991
- [c12]Avrim Blum, Lisa Hellerstein, Nick Littlestone:
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. COLT 1991: 157-166 - [c11]Avrim Blum, Prabhakar Raghavan, Baruch Schieber:
Navigating in Unfamiliar Geometric Terrain (Extended Summary). On-Line Algorithms 1991: 151-156 - [c10]Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis:
Linear Approximation of Shortest Superstrings. STOC 1991: 328-336 - [c9]Avrim Blum, Prabhakar Raghavan, Baruch Schieber:
Navigating in Unfamiliar Geometric Terrain (Preliminary Version). STOC 1991: 494-504 - 1990
- [c8]Avrim Blum, Mona Singh:
Learning Functions of k Terms. COLT 1990: 144-153 - [c7]Avrim Blum:
Separating PAC and Mistake-Bound Learning Models Over the Boolean Domain (Abstract). COLT 1990: 393 - [c6]Avrim Blum:
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain. FOCS 1990: 211-218 - [c5]Avrim Blum:
Some Tools for Approximate 3-Coloring (Extended Abstract). FOCS 1990: 554-562 - [c4]Avrim Blum:
Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract). STOC 1990: 64-72
1980 – 1989
- 1989
- [c3]Avrim Blum:
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring). STOC 1989: 535-542 - 1988
- [c2]Avrim Blum, Ronald L. Rivest:
Training a 3-Node Neural Network is NP-Complete. COLT 1988: 9-18 - [c1]Avrim Blum, Ronald L. Rivest:
Training a 3-Node Neural Network is NP-Complete. NIPS 1988: 494-501
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-04-22 22:09 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
