Avrim Blum
Papers
8
Total Citations
874
H-Index
8
About
Avrim Blum is a prominent theoretical computer scientist whose research spans algorithmic machine learning, approximation algorithms, and robot navigation under uncertainty. His most influential contributions lie at the intersection of planning, optimization, and adversarial settings — areas where classical assumptions about complete information must be abandoned in favor of online or robust approaches. Blum's work on robot navigation in unfamiliar geometric terrain, dating back to 1991, established foundational competitive analysis frameworks for mobile agents navigating unknown obstacle-laden environments, garnering nearly 200 combined citations across multiple versions. His development of the first constant-factor approximation algorithms for the Orienteering and Discounted-Reward Traveling Salesman problems (2004/2007, ~375 combined citations) provided breakthrough tools for reward-collecting path planning problems relevant to robotics and operations research. More recently, his investigation of Markov Decision Processes with adversarially controlled cost functions (2018, 228 citations) has proven highly impactful for robust reinforcement learning research. Across his career, Blum has consistently advanced theoretical guarantees for algorithms operating under incomplete or adversarial information — work that continues to influence both the machine learning and autonomous systems communities. His contributions reflect a rare ability to bridge rigorous theory with compelling practical motivation.
Research Focus
Key Achievements
Top Papers
- 1Planning in the Presence of Cost Functions Controlled by an Adversary228 citations · 2018
- 2Approximation Algorithms for Orienteering and Discounted-Reward TSP197 citations · 2007
- 3Approximation algorithms for orienteering and discounted-reward TSP175 citations · 2004
- 4Navigating in unfamiliar geometric terrain103 citations · 1991
- 5Navigating in Unfamiliar Geometric Terrain93 citations · 1997
- 6Randomized robot navigation algorithms44 citations · 1996
- 7An on-line algorithm for improving performance in navigation25 citations · 2002
- 8An Online Algorithm for Improving Performance in Navigation9 citations · 2000