Jan Vondrak

IBM Almaden Research Center
650 Harry Rd
San Jose
CA 95120

E-mail: jvondrak-at-gmail-dot-com.
I'm a Research Staff Member in the theory group at IBM Almaden.

Current research interests

  • Approximation algorithms
  • Matroids and submodular functions
  • Stochastic optimization
  • Extremal and probabilistic combinatorics

    Here you can download my curriculum vitae.

    Some presentations

    Lectures/tutorials

    Submodular functions and their applications (SODA 2013 plenary talk)
    Tutorial on submodular optimization: part 1, part 2 (Modern Aspects of Submodularity workshop, Georgia Tech 2012)

    Research talks

    Communication complexity of combinatorial auctions with submodular bidders (SODA 2013 talk)
    Computational complexity of truthful mechanisms for combinatorial auctions (EC 2012 top 10% paper; these slides are from the Algorithmic Frontiers workshop at EPFL)
    From query complexity to computational complexity (STOC 2012 paper)
    Randomized rounding in matroid polytopes (FOCS 2010 paper)
    PTAS for matroid matching (STOC 2010 paper)
    Symmetry and hardness of submodular maximization problems (FOCS 2009 paper)
    Combinatorial allocation and submodular maximization over a matroid (STOC 2008 paper; these slides are from a RIMS workshop in Kyoto)

    Teaching

    I taught Polyhedral techniques in combinatorial optimization at Stanford in Fall 2010.

    Papers

    Combinatorial auctions

    Matroids and submodular functions

    Database theory


    Information Theory


    Stochastic optimization


    Combinatorics


    Discrete Geometry


    Max-Cut and Statistical Physics


    Theses