Jan Vondrak: papers
(listed chronologically based on the first publication, if conference/journal versions exist)
2023
- Jugal Garg, Edin Husic, Wenzheng Li, Laszlo Vegh, Jan Vondrak:
Approximating Nash Social Welfare by Matching and Local Search
in STOC 2023, 1298-1310.
- Shahar Dobzinski, Shiri Ron, Jan Vondrak:
Fairness and Incentive Compatibility via Percentage Fees
in EC 2023.
- Monika Henzinger, Paul Liu, Jan Vondrak, Da Wei Zheng:
Faster Submodular Maximization for Several Classes of Matroids
in ICALP 2023.
- Pranav Nuti, Jan Vondrak:
Towards an Optimal Contention Resolution Scheme for Matchings
in IPCO 2023, 378-392.
- Pranav Nuti, Jan Vondrak:
Secretary Problems: The Power of a Single Sample
in SODA 2023, 2015-2029.
- Ferenc Bencs, Peter Csikvari, Piyush Srivastava, Jan Vondrak:
On complex roots of the independence polynomial
in SODA 2023, 675-699.
2022
2021
2020
2019
2018
2017
- Nick Harvey, Jan Vondrak:
Short proofs for generalizations of the Lovasz Local Lemma: Shearer's condition and cluster expansion
manuscript, 2017.
- Vitaly Feldman, Pravesh Kothari, Jan Vondrak:
Tight bounds on l1 approximation and learning of self-bounding functions
in ALT 2017.
- Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrak:
When are welfare guarantees robust?
in APPROX-RANDOM 2017, 22:1-22:23.
- Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrak:
Stability and recovery for independence systems
in ESA 2017, 26:1-26:15.
2016
2015
- Maryam Mirzakhani, Jan Vondrak:
Sperner's colorings and optimal partitiongs of the simplex
in A Journey Through Discrete Mathematics, a tribute to Jiri Matousek, Springer 2017.
A conference version published as
Sperner's colorings, hypergraph labeling problems and fair division
in SODA 2015.
- Nick Harvey, Jan Vondrak:
An algorithmic proof of the Lovasz Local Lemma via resampling oracles
SIAM J. Comput. 49:2, 394-428, 2020
conference version in FOCS 2015.
- Vitaly Feldman, Jan Vondrak:
Tight bounds on low-degree spectral concentration of submodular and XOS functions
in FOCS 2015.
full version on arxiv.org:1504.03391.
- Maxim Sviridenko, Jan Vondrak, Justin Ward:
Optimal approximation for submodular and supermodular optimization with bounded curvature
Math. Oper. Res. 42(4), 1197-1218, 2017;
earlier version in SODA 2015.
- Chandra Chekuri, T.S. Jayram, Jan Vondrak:
On Multiplicative Weight Updates for Concave and Submodular Function Maximization
in ITCS 2015.
- Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, Andreas Krause:
Lazier than Lazy Greedy
in AAAI 2015.
2014
2013
- Vitaly Feldman, Jan Vondrak:
Optimal bounds on approximation of submodular and XOS functions by juntas.
SIAM J. Comput. 45(3): 1129-1170, 2016.
conference version
in FOCS 2013,
- Vitaly Feldman, Pravesh Kothari, Jan Vondrak:
Representation, approximation and learning of submodular functions using low-rank decision trees
in COLT 2013,
full version on arxiv.org:1304.0730.
- Michael Kapralov, Ian Post, Jan Vondrak:
Online submodular welfare maximization: Greedy is optimal
in SODA 2013, 1216-1225.
full version on arxiv.org:1204.1025.
- Shahar Dobzinski, Jan Vondrak:
Communication complexity of combinatorial auctions with submodular bidders
in SODA 2013, 1205-1215.
- Alina Ene, Jan Vondrak, Yi Wu:
Local distribution and the symmetry gap: Approximability of multiway partitioning problems
in SODA 2013, 306-325.
- Benny Kimelfeld, Jan Vondrak, David P. Woodruff:
Multi-Tuple Deletion Propagation: Approximations and Complexity
in PVLDB 6:13, 1558-1569, 2013.
2012
2011
- Shaddin Dughmi, Jan Vondrak:
Limitations of randomized mechanisms for combinatorial auctions
Games and Economic Behavior 92: 370-400, 2015.
conference version
in FOCS 2011, 502-511.
- Shaddin Dughmi, Tim Roughgarden, Jan Vondrak, Qiqi Yan:
An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries,
arxiv:1109.1053, 2011.
- C. Seshadhri, Jan Vondrak:
Is submodularity testable?
Algorithmica 69:1, 1-25, 2014;
an extended abstract
appeared in Innovations in Computer Science 2011, 195-210.
- Shayan Oveis Gharan, Jan Vondrak:
On variants of the matroid secretary problem
Algorithmica 67:4, 472-497, 2013;
extended abstract
in ESA 2011, 335-346.
- Chandra Chekuri, Jan Vondrak, Rico Zenklusen:
Submodular function maximization via the multilinear relaxation and contention resolution schemes
in STOC 2011, 783-792;
full version on arxiv.org:1105.4593.
- Shayan Oveis Gharan, Jan Vondrak:
Submodular maximization by simulated annealing
in SODA 2011, 1098-1117;
full version on arxiv.org:1007.1632.
- Chandra Chekuri, Jan Vondrak, Rico Zenklusen:
Multi-budgeted matchings and matroid intersection via dependent rounding
in SODA 2011, 1080-1097.
- Benny Kimelfeld, Jan Vondrak and Ryan Williams:
Maximizing conjunctive views in deletion propagation
ACM Trans. Database Syst. (TODS) 37(4):24, 2012;
extended abstract in PODS 2011, 187-198.
2010
- Chandra Chekuri, Jan Vondrak, Rico Zenklusen:
Dependent randomized rounding via exchange properties of combinatorial structures
in FOCS 2010, 575-584;
full version on arxiv.org:0909.4348.
- Jon Lee, Maxim Sviridenko, Jan Vondrak:
Matroid matching: the power of local search
SIAM Journal on Computing 42:1, 357-379, 2013.
an extended abstract
appeared in STOC 2010, 369-378.
- Jan Vondrak:
Submodularity and curvature: the optimal algorithm
in RIMS Kokyuroku Bessatsu B23, Kyoto, 2010, 253-266.
- Benny Sudakov and Jan Vondrak:
A randomized embedding algorithm for trees
Combinatorica 30:4 (2010), 445-470.
- Jan Vondrak:
A note on concentration of submodular functions
Manuscript, 2010, arXiv:1005.2791v1.
2009
- Jan Vondrak:
Symmetry and approximability of submodular maximization problems
SIAM Journal on Computing 42:1, 265-304, 2013,
an extended abstract
appeared in FOCS 2009, 651-670.
- Jon Lee, Maxim Sviridenko, Jan Vondrak:
Submodular maximization over multiple matroids via generalized exchange properties
Math. of Operations Research 35 (2010), 795-806.
an earlier version
appeared in APPROX 2009, 244-257.
- Gruia Calinescu, Chandra Chekuri and Jan Vondrak:
Disjoint bases in a polymatroid
Random Structures and Algorithms, 35:4, 418-430, 2009.
- Lalitha Sankar, Jan Vondrak and Vincent Poor:
K-user fading interference channels: The ergodic very strong case
in Allerton conference on Communication, Control and Computing, 2009.
2008
2007
2006
- Uriel Feige, Jan Vondrak:
The submodular welfare problem with demand queries
Theory of Computation 6 (2010), 247-290.
An extended abstract with other results appeared in
Approximation algorithms
for allocation problems: Improving the factor of 1-1/e,
in FOCS 2006, 667-676.
Further details and proofs can be found in my Charles University thesis, see bottom of this page.
- Michel Goemans and Jan Vondrak:
Stochastic covering and adaptivity
in LATIN 2006, Theoretical informatics, 532-543, LNCS 3887 (2006).
- Noga Alon, Rados Radoicic, Benny Sudakov and Jan Vondrak:
A Ramsey-type result for
the hypercube
Journal of graph theory 53 (2006), 196-208.
- Janos Pach, Rados Radoicic and Jan Vondrak:
On the diameter of separated point
sets with many nearly equal distances
European journal of combinatorics 27:8, 1321-1332 (2006).
An earlier version
appeared in Computational Geometry: Theory and Applications 34,
11-19 (2006).
2005
2004
Prior to 2004
- Tim Chow, Kenneth Fan, Michel Goemans and Jan Vondrak:
Wide partitions, Latin tableaux,
and Rota's basis conjecture
Advances in Applied Mathematics, 31:2, 334-358 (2003).
- Martin Loebl and Jan Vondrak:
Towards a theory of frustrated
degeneracy
Discrete Mathematics 271, 179-193 (2003).
- Robert Samal and Jan Vondrak:
The limit checker number of a graph
Discrete Math. 235, 343-347 (2001).
- Anna Galluccio, Martin Loebl and Jan Vondrak:
Optimization via enumeration:
a new algorithm for the Max Cut problem
Mathematical Programming 90-2A, 273-290 (2001).
- Anna Galluccio, Martin Loebl and Jan Vondrak:
New algorithm for the Ising problem:
Partition function for finite lattice graphs
Physical Review Letters 84-26, 5924-5927 (2000).
- Robert Babilon, Helena Nyklova, Ondrej Pangrac and Jan Vondrak:
Visibility representations of
graphs
Graph Drawing 1999, 333-340, Lecture Notes in CS 1731,
Springer (1999).
Theses
- Probabilistic methods in combinatorial
and stochastic optimization, PhD thesis, MIT, 2005.
- Submodularity in combinatorial
optimization, PhD thesis, Charles University,
Prague, 2007.
- Implementation and testing of a new
algorithm for the Max Cut problem,
Master's thesis, Charles University,
Prague, 1999.