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


    Submodular functions and their applications (plenary talk at SIAM Conference on Discrete Mathematics 2014)
    Submodular functions and their applications (plenary talk at ACM-SIAM Symposium on Discrete Algorithms 2013)
    Tutorial on submodular optimization: part 1, part 2 (Modern Aspects of Submodularity workshop, Georgia Tech 2012)

    Some research talks

    Approximability of multiway partitioning problems (Banff 2014 workshop)
    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)


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


    Recent papers

    Learning and structure of valuation functions

    Combinatorial auctions

    Optimization of submodular functions / matroids

    Database theory

    Information Theory

    Stochastic optimization


    Discrete Geometry

    Max-Cut and Statistical Physics