Optimal bounds on approximation of submodular and XOS functions by juntas
- Vitaly Feldman
- Jan Vondrák
- 2016
- SIAM Journal on Computing
Paper
Publications
40 results for Jan Vondrák
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
- Vitaly Feldman
- Jan Vondrák
- 2015
- FOCS 2015
Conference paperAn Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
- Nicholas J.A. Harvey
- Jan Vondrák
- 2015
- FOCS 2015
Conference paperInformation-theoretic lower bounds for convex optimization with erroneous oracles
- Yaron Singer
- Jan Vondrák
- 2015
- NeurIPS 2015
Conference paperOn multiplicative weight updates for concave and submodular function maximization [extended abstract]
- Chandra Chekuri
- T. S. Jayram
- et al.
- 2015
- ITCS 2015
Conference paperSperner's colorings, hypergraph labeling problems and fair division
- Maryam Mirzakhani
- Jan Vondrák
- 2015
- SODA 2015
Conference paperOptimal approximation for submodular and supermodular optimization with bounded curvature
- Maxim Sviridenko
- Jan Vondrák
- et al.
- 2015
- SODA 2015
Conference paperLimitations of randomized mechanisms for combinatorial auctions
- Shaddin Dughmi
- Jan Vondrák
- 2015
- Games and Economic Behavior
PaperExchangeability and realizability: De finetti theorems on graphs
- T. S. Jayram
- Jan Vondrák
- 2014
- APPROX/RANDOM 2014
Conference paperHardness of submodular cost allocation: Lattice matching and a simplex coloring conjecture
- Alina Ene
- Jan Vondrák
- 2014
- APPROX/RANDOM 2014
Conference paper