Avrim Blum's research projects
Here is a rough clustering of current and recent research
projects (note: this page is not updated frequently - for the
most up-to-date information, see my publications page):
- 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.