Avrim Blum's research projects

• Models for non-worst-case analysis, including those motivated by how instances are constructed and how solutions will be used.
  • E.g., approximation-stability, perturbation-stability, semi-random models.
• Approximation algorithms for phylogenetic trees.
• Algorithms and analysis of privacy in release of information from databases including:
  • preserving privacy in release of "sanitized" social networks
  • connections to issues/concepts in computational learning theory.
• Property testing from a machine learning angle
• Machine Learning Theory, including:
  • distributed machine learning
  • models of learning
  • semi-supervised learning
  • online learning
  • approximation algorithms for agnostic learning
• Algorithmic Game Theory and Mechanism Design
  • Allocation and pricing under increasing and decreasing marginal costs
  • Relations between learning/dynamics and equilibria
  • More algorithmic notions of price of anarchy.
• Approximation algorithms for TSP-related problems.
  • TSP with Deadlines, Orienteering, Discounted-TSP, and the k-MST problem.
• Other approximation algorithms.
• Other online algorithms (routing, admission control, scheduling,...).

For the most up-to-date information, see my publications page.

See also my survey talks page.