Jan Vondrák

Follow

Generating author description...

All published works
Action Title Year Authors
+ PDF Chat Secretary Problems: The Power of a Single Sample 2023 Pranav Nuti
Jan Vondrák
+ Faster Submodular Maximization for Several Classes of Matroids 2023 Monika Henzinger
Paul Liu
Jan Vondrák
Da Wei Zheng
+ PDF Chat On the hardness of dominant strategy mechanism design 2022 Shahar Dobzinski
Shiri Ron
Jan Vondrák
+ PDF Chat Fixed-Price Approximations in Bilateral Trade 2022 Zi Yang Kang
Francisco Pernice
Jan Vondrák
+ Secretary Problems: The Power of a Single Sample 2022 Pranav Nuti
Jan Vondrák
+ Towards an Optimal Contention Resolution Scheme for Matchings 2022 Pranav Nuti
Jan Vondrák
+ On the Hardness of Dominant Strategy Mechanism Design 2022 Shahar Dobzinski
Shiri Ron
Jan Vondrák
+ Fixed-Price Approximations in Bilateral Trade. 2021 Zi Yang Kang
Francisco Pernice
Jan Vondrák
+ Estimating the Nash Social Welfare for coverage and other submodular valuations 2021 Wenzheng Li
Jan Vondrák
+ Fixed-Price Approximations in Bilateral Trade 2021 Zi Yang Kang
Francisco Pernice
Jan Vondrák
+ PDF Chat Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature 2017 Maxim Sviridenko
Jan Vondrák
Justin Ward
+ When Are Welfare Guarantees Robust 2016 Tim Roughgarden
Inbal Talgam-Cohen
Jan Vondrák
+ PDF Chat Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas 2016 Vitaly Feldman
Jan Vondrák
+ When Are Welfare Guarantees Robust? 2016 Tim Roughgarden
Inbal Talgam-Cohen
Jan Vondrák
+ PDF Chat Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions 2015 Vitaly Feldman
Jan Vondrák
+ Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions 2015 Vitaly Feldman
Jan Vondrák
+ Optimal approximation for submodular and supermodular optimization with bounded curvature 2015 Maxim Sviridenko
Jan Vondrák
Justin Ward
+ PDF Chat Optimal approximation for submodular and supermodular optimization with bounded curvature 2014 Maxim Sviridenko
Jan Vondrák
Justin Ward
+ PDF Chat Optimal bounds on approximation of submodular and XOS functions by juntas 2014 Vitaly Feldman
Jan Vondrák
+ PDF Chat Limitations of randomized mechanisms for combinatorial auctions 2014 Shaddin Dughmi
Jan Vondrák
+ Exchangeability and Realizability: De Finetti Theorems on Graphs 2014 T. S. Jayram
Jan Vondrák
+ PDF Chat Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas 2013 Vitaly Feldman
Jan Vondrák
+ PDF Chat On Variants of the Matroid Secretary Problem 2013 Shayan Oveis Gharan
Jan Vondrák
+ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas 2013 Vitaly Feldman
Jan Vondrák
+ PDF Chat Online submodular welfare maximization: Greedy is optimal 2013 Michael Kapralov
Ian Post
Jan Vondrák
+ Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems 2013 Alina Ene
Jan Vondrák
Yi Wu
+ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas 2013 Vitaly Feldman
Jan Vondrák
+ PDF Chat The computational complexity of truthfulness in combinatorial auctions 2012 Shahar Dobzinski
Jan Vondrák
+ The Computational Complexity of Truthfulness in Combinatorial Auctions 2012 Shahar Dobzinski
Jan Vondrák
+ Online submodular welfare maximization: Greedy is optimal 2012 Michael Kapralov
Ian Post
Jan Vondrák
+ The Computational Complexity of Truthfulness in Combinatorial Auctions 2012 Shahar Dobzinski
Jan Vondrák
+ Symmetry and approximability of submodular maximization problems 2011 Jan Vondrák
+ Limitations of randomized mechanisms for combinatorial auctions 2011 Shaddin Dughmi
Jan Vondrák
+ Submodular function maximization via the multilinear relaxation and contention resolution schemes 2011 Chandra Chekuri
Jan Vondrák
Rico Zenklusen
+ On Variants of the Matroid Secretary Problem 2011 Shayan Oveis Gharan
Jan Vondrák
+ Multi-budgeted matchings and matroid intersection via dependent rounding 2011 Chandra Chekuri
Jan Vondrák
Rico Zenklusen
+ PDF Chat Submodular Maximization by Simulated Annealing 2011 Shayan Oveis Gharan
Jan Vondrák
+ An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries 2011 Shaddin Dughmi
Tim Roughgarden
Jan Vondrák
Qiqi Yan
+ PDF Chat On Variants of the Matroid Secretary Problem 2011 Shayan Oveis Gharan
Jan Vondrák
+ Symmetry and approximability of submodular maximization problems 2011 Jan Vondrák
+ Limitations of randomized mechanisms for combinatorial auctions 2011 Shaddin Dughmi
Jan Vondrák
+ On Variants of the Matroid Secretary Problem 2011 Shayan Oveis Gharan
Jan Vondrák
+ Submodular Maximization by Simulated Annealing 2010 Shayan Oveis Gharan
Jan Vondrák
+ Randomized Pipage Rounding for Matroid Polytopes and Applications 2009 Chandra Chekuri
Jan Vondrák
Common Coauthors
Commonly Cited References
Action Title Year Authors # of times referenced
+ PDF Chat Symmetry and Approximability of Submodular Maximization Problems 2009 J. Vondrák
6
+ Submodular functions and convexity 1983 László Lovász
6
+ Privately releasing conjunctions and the statistical query barrier 2011 Anupam Gupta
Moritz Hardt
Aaron Roth
Jonathan Ullman
5
+ Submodular Functions: Learnability, Structure, and Optimization 2010 Maria-Florina Balcan
Nicholas J. A. Harvey
5
+ Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees 2013 Vitaly Feldman
Pravesh K. Kothari
J. Vondrák
5
+ On the fourier tails of bounded functions over the discrete cube 2006 Irit Dinur
Ehud Friedgut
Guy Kindler
Ryan O’Donnell
5
+ On the distribution of the fourier spectrum of Boolean functions 2002 Jean Bourgain
4
+ Covering minimum spanning trees of random subgraphs 2005 Michel X. Goemans
J. Vondrák
4
+ PDF Chat Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms 2010 Anupam Gupta
Aaron Roth
Grant Schoenebeck
Kunal Talwar
4
+ PDF Chat A sharp concentration inequality with applications 2000 Stéphane Boucheron
G�bor Lugosi
Pascal Massart
4
+ Matroids and the greedy algorithm 1971 Jack Edmonds
4
+ Boolean functions whose Fourier transform is concentrated on the first two levels 2002 Ehud Friedgut
Gil Kalai
Assaf Naor
4
+ A note on concentration of submodular functions 2010 J. Vondrák
4
+ Concentration for self‐bounding functions and an inequality of Talagrand 2006 Colin McDiarmid
Bruce Reed
4
+ Combinatorial auctions with decreasing marginal utilities 2001 Benny Lehmann
Daniel Lehmann
Noam Nisan
3
+ PDF Chat Near-Optimal Column-Based Matrix Reconstruction 2014 Christos Boutsidis
Petros Drineas
Malik Magdon‐Ismail
3
+ Rademacher penalties and structural risk minimization 2001 Vladimir Koltchinskii
3
+ PDF Chat A truthful randomized mechanism for combinatorial public projects via convex optimization 2011 Shaddin Dughmi
3
+ PDF Chat Comments on bases in dependence structures 1969 Richard A. Brualdi
3
+ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas 2013 Vitaly Feldman
Jan Vondrák
3
+ None 2006 Paul Balister
B Bollobás
Róbert Kozma
3
+ The influence of variables on Boolean functions 1988 J. Kahn
Gil Kalai
Nathan Linial
3
+ PDF Chat Algorithms for Secretary Problems on Graphs and Hypergraphs 2009 Nitish Korula
Martin Pál
3
+ PDF Chat Efficient Volume Sampling for Row/Column Subset Selection 2010 Amit Deshpande
Luis Rademacher
3
+ An Exact Algorithm for Maximum Entropy Sampling 1995 Chun-Wa Ko
Jon Lee
Maurice Queyranne
3
+ None 2006 Martin Dyer
Abraham D. Flaxman
Alan Frieze
Eric Vigoda
3
+ PDF Chat Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas 2013 Vitaly Feldman
Jan Vondrák
3
+ Matroid secretary problem in the random assignment model 2011 José A. Soto
3
+ Learning pseudo-Boolean k-DNF and Submodular Functions 2012 Sofya Raskhodnikova
Grigory Yaroslavtsev
3
+ PDF Chat Symmetry and Approximability of Submodular Maximization Problems 2013 J. Vondrák
3
+ PDF Chat Submodular Functions are Noise Stable 2012 Mahdi Cheraghchi
Adam R. Klivans
Pravesh K. Kothari
Homin K. Lee
3
+ Learning Valuation Functions 2011 Maria Florina Balcan
Florin Constantin
Satoru Iwata
Lei Wang
3
+ DNF Sparsification and a Faster Deterministic Counting Algorithm 2012 Parikshit Gopala
Raghu Meka
Omer Reingold
2
+ On the Power of Randomization in Algorithmic Mechanism Design 2009 Shahar Dobzinski
Shaddin Dughmi
2
+ PDF Chat Online Stochastic Packing Applied to Display Ad Allocation 2010 Jon Feldman
Monika Henzinger
Nitish Korula
Vahab Mirrokni
Clifford Stein
2
+ PDF Chat Étude des coefficients de Fourier des fonctions de $L^p(G)$ 1970 Aline Bonami
2
+ Improved Approximation of Linear Threshold Functions 2009 Ilias Diakonikolas
Rocco A. Servedio
2
+ Submodular function maximization via the multilinear relaxation and contention resolution schemes 2011 Chandra Chekuri
Jan Vondrák
Rico Zenklusen
2
+ Multi-budgeted matchings and matroid intersection via dependent rounding 2011 Chandra Chekuri
Jan Vondrák
Rico Zenklusen
2
+ A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions 2000 Satoru Iwata
Lisa Fleischer
Satoru Fujishige
2
+ PDF Chat DNF Sparsification and a Faster Deterministic Counting Algorithm 2012 Parikshit Gopalan
Raghu Meka
Omer Reingold
2
+ An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries 2011 Shaddin Dughmi
Tim Roughgarden
Jan Vondrák
Qiqi Yan
2
+ Inequalities in Fourier Analysis 1975 William Beckner
2
+ On the degree of Boolean functions as real polynomials 1992 Noam Nisan
Márió Szegedy
2
+ PDF Chat The computational complexity of truthfulness in combinatorial auctions 2012 Shahar Dobzinski
Jan Vondrák
2
+ PDF Chat A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint 2012 Yuval Filmus
Justin Ward
2
+ How much are increasing sets positively correlated? 1996 Michel Talagrand
2
+ An impossibility result for truthful combinatorial auctions with submodular valuations 2011 Shahar Dobzinski
2
+ Multiplicative submodularity of a matrix's principal minor as a function of the set of its rows and some combinatorial applications 1983 Alexander Kelmans
Boris Kimelfeld
2
+ PDF Chat Multiway cut, pairwise realizable distributions, and descending thresholds 2014 Ankit Sharma
J. Vondrák
2