Jan Vondrák

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 61

Top Venues

Publications

Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, Jan Vondrák
Prophet Inequalities with Cancellation Costs. STOC (2024)
Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, Jan Vondrák
Prophet Inequalities with Cancellation Costs. CoRR (2024)
Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák
A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. STOC (2024)
Bryan Park, Jan Vondrák
A Simple Proof of the Nonuniform Kahn-Kalai Conjecture. SIAM J. Discret. Math. 38 (3) (2024)
Shahar Dobzinski, Sigal Oren, Jan Vondrák
Fairness and Incentive Compatibility via Percentage Fees. CoRR (2024)
Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák
A constant factor approximation for Nash social welfare with subadditive valuations. CoRR (2023)
Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, Jan Vondrák
Approximating Nash Social Welfare by Matching and Local Search. STOC (2023)
Monika Henzinger, Paul Liu, Jan Vondrák, Da Wei Zheng
Faster Submodular Maximization for Several Classes of Matroids. CoRR (2023)
Pranav Nuti, Jan Vondrák
Towards an Optimal Contention Resolution Scheme for Matchings. IPCO (2023)
Monika Henzinger, Paul Liu, Jan Vondrák, Da Wei Zheng
Faster Submodular Maximization for Several Classes of Matroids. ICALP (2023)
Pranav Nuti, Jan Vondrák
Secretary Problems: The Power of a Single Sample. SODA (2023)
Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák
On complex roots of the independence polynomial. SODA (2023)
Shahar Dobzinski, Sigal Oren, Jan Vondrák
Fairness and Incentive Compatibility via Percentage Fees. EC (2023)
Shahar Dobzinski, Shiri Ron, Jan Vondrák
On the Hardness of Dominant Strategy Mechanism Design. CoRR (2022)
Zi Yang Kang, Francisco Pernice, Jan Vondrák
Fixed-Price Approximations in Bilateral Trade. SODA (2022)
Shahar Dobzinski, Shiri Ron, Jan Vondrák
On the hardness of dominant strategy mechanism design. STOC (2022)
Wenzheng Li, Jan Vondrák
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. FOCS (2022)
Pranav Nuti, Jan Vondrák
Secretary Problems: The Power of a Single Sample. CoRR (2022)
Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, Jan Vondrák
Approximating Nash Social Welfare by Matching and Local Search. CoRR (2022)
Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák
On complex roots of the independence polynomial. CoRR (2022)
Pranav Nuti, Jan Vondrák
Towards an Optimal Contention Resolution Scheme for Matchings. CoRR (2022)
Wenzheng Li, Jan Vondrák
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. FOCS (2021)
Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
Cardinality constrained submodular maximization for random streams. CoRR (2021)
Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
Cardinality constrained submodular maximization for random streams. NeurIPS (2021)
Zi Yang Kang, Francisco Pernice, Jan Vondrák
Fixed-Price Approximations in Bilateral Trade. CoRR (2021)
Wenzheng Li, Jan Vondrák
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. CoRR (2021)
Wenzheng Li, Jan Vondrák
Estimating the Nash Social Welfare for coverage and other submodular valuations. CoRR (2021)
Wenzheng Li, Jan Vondrák
Estimating the Nash Social Welfare for coverage and other submodular valuations. SODA (2021)
Wenzheng Li, Paul Liu, Jan Vondrák
A polynomial lower bound on adaptive complexity of submodular maximization. STOC (2020)
Wenzheng Li, Paul Liu, Jan Vondrák
A polynomial lower bound on adaptive complexity of submodular maximization. CoRR (2020)
Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, Jan Vondrák
Submodular Maximization Through Barrier Functions. CoRR (2020)
Nicholas J. A. Harvey, Jan Vondrák
An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles. SIAM J. Comput. 49 (2) (2020)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
approximation and learning of self-bounding functions. Theor. Comput. Sci. 808 (2020)
Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, Jan Vondrák
Submodular Maximization Through Barrier Functions. NeurIPS (2020)
Paul Liu, Jan Vondrák
Submodular Optimization in the MapReduce Model. SOSA (2019)
Vitaly Feldman, Jan Vondrák
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. COLT (2019)
Vitaly Feldman, Jan Vondrák
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. CoRR (2019)
Paul Liu, Jan Vondrák
Submodular Optimization in the MapReduce Model. CoRR (2018)
Vitaly Feldman, Jan Vondrák
Generalization Bounds for Uniformly Stable Algorithms. NeurIPS (2018)
Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák
Computing the Independence Polynomial: from the Tree Threshold down to the Roots. SODA (2018)
Vitaly Feldman, Jan Vondrák
Generalization Bounds for Uniformly Stable Algorithms. CoRR (2018)
Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák
When Are Welfare Guarantees Robust?. APPROX-RANDOM (2017)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Approximation and Learning of Self-Bounding Functions. ALT (2017)
Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák
Stability and Recovery for Independence Systems. CoRR (2017)
Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák
Stability and Recovery for Independence Systems. ESA (2017)
Maxim Sviridenko, Jan Vondrák, Justin Ward
Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature. Math. Oper. Res. 42 (4) (2017)
Vitaly Feldman, Jan Vondrák
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. SIAM J. Comput. 45 (3) (2016)
Shahar Dobzinski, Jan Vondrák
Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations. J. ACM 63 (1) (2016)
Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák
Computing the independence polynomial in Shearer's region for the LLL. CoRR (2016)
Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák
When Are Welfare Guarantees Robust? CoRR (2016)
Yaron Singer, Jan Vondrák
Information-theoretic lower bounds for convex optimization with erroneous oracles. NIPS (2015)
Alina Ene, Jan Vondrák, Yi Wu
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. CoRR (2015)
Nicholas J. A. Harvey, Jan Vondrák
An Algorithmic Proof of the Lopsided Lovasz Local Lemma. CoRR (2015)
Maxim Sviridenko, Jan Vondrák, Justin Ward
Optimal approximation for submodular and supermodular optimization with bounded curvature. SODA (2015)
Vitaly Feldman, Jan Vondrák
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions. FOCS (2015)
Vitaly Feldman, Jan Vondrák
Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions. CoRR (2015)
Chandra Chekuri, T. S. Jayram, Jan Vondrák
On Multiplicative Weight Updates for Concave and Submodular Function Maximization. ITCS (2015)
Shaddin Dughmi, Jan Vondrák
Limitations of randomized mechanisms for combinatorial auctions. Games Econ. Behav. 92 (2015)
Maryam Mirzakhani, Jan Vondrák
Sperner's Colorings, Hypergraph Labeling Problems and Fair Division. SODA (2015)
Nicholas J. A. Harvey, Jan Vondrák
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles. FOCS (2015)
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause
Lazier Than Lazy Greedy. AAAI (2015)
T. S. Jayram, Jan Vondrák
Exchangeability and Realizability: De Finetti Theorems on Graphs. APPROX-RANDOM (2014)
Alina Ene, Jan Vondrák
Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture. APPROX-RANDOM (2014)
Ankit Sharma, Jan Vondrák
Multiway cut, pairwise realizable distributions, and descending thresholds. STOC (2014)
C. Seshadhri, Jan Vondrák
Is Submodularity Testable? Algorithmica 69 (1) (2014)
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause
Lazier Than Lazy Greedy. CoRR (2014)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Approximation of Self-Bounding Functions. CoRR (2014)
Ashwinkumar Badanidiyuru, Jan Vondrák
Fast algorithms for maximizing submodular functions. SODA (2014)
Chandra Chekuri, Jan Vondrák, Rico Zenklusen
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. SIAM J. Comput. 43 (6) (2014)
Vitaly Feldman, Jan Vondrák
Optimal bounds on approximation of submodular and XOS functions by juntas. ITA (2014)
Jan Vondrák
Symmetry and Approximability of Submodular Maximization Problems. SIAM J. Comput. 42 (1) (2013)
Alina Ene, Jan Vondrák, Yi Wu
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. SODA (2013)
Shayan Oveis Gharan, Jan Vondrák
On Variants of the Matroid Secretary Problem. Algorithmica 67 (4) (2013)
Michael Kapralov, Ian Post, Jan Vondrák
Online Submodular Welfare Maximization: Greedy is Optimal. SODA (2013)
Vitaly Feldman, Jan Vondrák
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. CoRR (2013)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees CoRR (2013)
Vitaly Feldman, Jan Vondrák
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. FOCS (2013)
Benny Kimelfeld, Jan Vondrák, David P. Woodruff
Multi-Tuple Deletion Propagation: Approximations and Complexity. Proc. VLDB Endow. 6 (13) (2013)
Ankit Sharma, Jan Vondrák
Multiway Cut, the Golden Ratio, and Descending Thresholds. CoRR (2013)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. COLT (2013)
Jon Lee, Maxim Sviridenko, Jan Vondrák
Matroid Matching: The Power of Local Search. SIAM J. Comput. 42 (1) (2013)
Shahar Dobzinski, Jan Vondrák
Communication Complexity of Combinatorial Auctions with Submodular Valuations. SODA (2013)
Mohamed Y. Eltabakh, Fatma Özcan, Yannis Sismanis, Peter J. Haas, Hamid Pirahesh, Jan Vondrák
Eagle-eyed elephant: split-oriented indexing in Hadoop. EDBT (2013)
Vitaly Feldman, Jan Vondrák
Structure and learning of valuation functions. SIGecom Exch. 12 (2) (2013)
Shahar Dobzinski, Jan Vondrák
The Computational Complexity of Truthfulness in Combinatorial Auctions CoRR (2012)
Shahar Dobzinski, Jan Vondrák
On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations CoRR (2012)
Benny Kimelfeld, Jan Vondrák, Ryan Williams
Maximizing Conjunctive Views in Deletion Propagation. ACM Trans. Database Syst. 37 (4) (2012)
Mikhail Kapralov, Ian Post, Jan Vondrák
Online and stochastic variants of welfare maximization CoRR (2012)
Shahar Dobzinski, Jan Vondrák
The computational complexity of truthfulness in combinatorial auctions. EC (2012)
Shahar Dobzinski, Jan Vondrák
From query complexity to computational complexity. STOC (2012)
Benny Kimelfeld, Jan Vondrák, Ryan Williams
Maximizing conjunctive views in deletion propagation. PODS (2011)
Chandra Chekuri, Jan Vondrák, Rico Zenklusen
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes CoRR (2011)
Shaddin Dughmi, Tim Roughgarden, Jan Vondrák, Qiqi Yan
An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries CoRR (2011)
Shaddin Dughmi, Jan Vondrák
Limitations of Randomized Mechanisms for Combinatorial Auctions. FOCS (2011)
Shayan Oveis Gharan, Jan Vondrák
Submodular Maximization by Simulated Annealing. SODA (2011)
Jan Vondrák, Chandra Chekuri, Rico Zenklusen
Submodular function maximization via the multilinear relaxation and contention resolution schemes. STOC (2011)
Shayan Oveis Gharan, Jan Vondrák
On Variants of the Matroid Secretary Problem CoRR (2011)
Jan Vondrák
Symmetry and approximability of submodular maximization problems CoRR (2011)
Sara Cohen, Benny Kimelfeld, Georgia Koutrika, Jan Vondrák
On Principles of Egocentric Person Search in Social Networks. VLDS (2011)
Chandra Chekuri, Jan Vondrák, Rico Zenklusen
Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. SODA (2011)

Jan Vondrák.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Jan Vondrák