Jan Vondrák

According to our database, Jan Vondrák authored at least 91 papers between 1999 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

A Simple Proof of the Nonuniform Kahn-Kalai Conjecture.

Bryan Park, Jan Vondrák

SIAM J. Discret. Math., 2024

Prophet Inequalities with Cancellation Costs.

Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, Jan Vondrák

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations.

Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Approximating Nash Social Welfare by Matching and Local Search.

Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, Jan Vondrák

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Secretary Problems: The Power of a Single Sample.

Pranav Nuti, Jan Vondrák

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

On complex roots of the independence polynomial.

Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fairness and Incentive Compatibility via Percentage Fees.

Shahar Dobzinski, Sigal Oren, Jan Vondrák

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Towards an Optimal Contention Resolution Scheme for Matchings.

Pranav Nuti, Jan Vondrák

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Faster Submodular Maximization for Several Classes of Matroids.

Monika Henzinger, Paul Liu, Jan Vondrák, Da Wei Zheng

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

On the hardness of dominant strategy mechanism design.

Shahar Dobzinski, Shiri Ron, Jan Vondrák

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Fixed-Price Approximations in Bilateral Trade.

Zi Yang Kang, Francisco Pernice, Jan Vondrák

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

Estimating the Nash Social Welfare for coverage and other submodular valuations.

Wenzheng Li, Jan Vondrák

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Cardinality constrained submodular maximization for random streams.

Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations.

Wenzheng Li, Jan Vondrák

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Tight bounds on <i>ℓ</i>₁ approximation and learning of self-bounding functions.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Theor. Comput. Sci., 2020

An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles.

Nicholas J. A. Harvey, Jan Vondrák

SIAM J. Comput., 2020

A polynomial lower bound on adaptive complexity of submodular maximization.

Wenzheng Li, Paul Liu, Jan Vondrák

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Submodular Maximization Through Barrier Functions.

Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, Jan Vondrák

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019

Submodular Optimization in the MapReduce Model.

Paul Liu, Jan Vondrák

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.

Vitaly Feldman, Jan Vondrák

Proceedings of the Conference on Learning Theory, 2019

2018

Computing the Independence Polynomial: from the Tree Threshold down to the Roots.

Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Generalization Bounds for Uniformly Stable Algorithms.

Vitaly Feldman, Jan Vondrák

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature.

Maxim Sviridenko, Jan Vondrák, Justin Ward

Math. Oper. Res., 2017

Stability and Recovery for Independence Systems.

Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

When Are Welfare Guarantees Robust?.

Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák

Proceedings of the Approximation, 2017

Tight Bounds on ℓ₁ Approximation and Learning of Self-Bounding Functions.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.

Vitaly Feldman, Jan Vondrák

SIAM J. Comput., 2016

Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations.

Shahar Dobzinski, Jan Vondrák

J. ACM, 2016

Computing the independence polynomial in Shearer's region for the LLL.

Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák

CoRR, 2016

2015

Limitations of randomized mechanisms for combinatorial auctions.

Shaddin Dughmi, Jan Vondrák

Games Econ. Behav., 2015

An Algorithmic Proof of the Lopsided Lovasz Local Lemma.

Nicholas J. A. Harvey, Jan Vondrák

CoRR, 2015

Sperner's Colorings, Hypergraph Labeling Problems and Fair Division.

Maryam Mirzakhani, Jan Vondrák

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Information-theoretic lower bounds for convex optimization with erroneous oracles.

Yaron Singer, Jan Vondrák

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

On Multiplicative Weight Updates for Concave and Submodular Function Maximization.

Chandra Chekuri, T. S. Jayram, Jan Vondrák

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions.

Vitaly Feldman, Jan Vondrák

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Lazier Than Lazy Greedy.

Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes.

Chandra Chekuri, Jan Vondrák, Rico Zenklusen

SIAM J. Comput., 2014

Nearly Tight Bounds on ℓ₁ Approximation of Self-Bounding Functions.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

CoRR, 2014

Is Submodularity Testable?

C. Seshadhri, Jan Vondrák

Algorithmica, 2014

Multiway cut, pairwise realizable distributions, and descending thresholds.

Ankit Sharma, Jan Vondrák

Proceedings of the Symposium on Theory of Computing, 2014

Fast algorithms for maximizing submodular functions.

Ashwinkumar Badanidiyuru, Jan Vondrák

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Exchangeability and Realizability: De Finetti Theorems on Graphs.

T. S. Jayram, Jan Vondrák

Proceedings of the Approximation, 2014

Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture.

Alina Ene, Jan Vondrák

Proceedings of the Approximation, 2014

2013

Structure and learning of valuation functions.

Vitaly Feldman, Jan Vondrák

SIGecom Exch., 2013

Symmetry and Approximability of Submodular Maximization Problems.

Jan Vondrák

SIAM J. Comput., 2013

Matroid Matching: The Power of Local Search.

Jon Lee, Maxim Sviridenko, Jan Vondrák

SIAM J. Comput., 2013

Multi-Tuple Deletion Propagation: Approximations and Complexity.

Benny Kimelfeld, Jan Vondrák, David P. Woodruff

Proc. VLDB Endow., 2013

Multiway Cut, the Golden Ratio, and Descending Thresholds.

Ankit Sharma, Jan Vondrák

CoRR, 2013

On Variants of the Matroid Secretary Problem.

Shayan Oveis Gharan, Jan Vondrák

Algorithmica, 2013

Online Submodular Welfare Maximization: Greedy is Optimal.

Michael Kapralov, Ian Post, Jan Vondrák

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems.

Alina Ene, Jan Vondrák, Yi Wu

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Communication Complexity of Combinatorial Auctions with Submodular Valuations.

Shahar Dobzinski, Jan Vondrák

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Eagle-eyed elephant: split-oriented indexing in Hadoop.

Mohamed Y. Eltabakh, Fatma Özcan, Yannis Sismanis, Peter J. Haas, Hamid Pirahesh, Jan Vondrák

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Proceedings of the COLT 2013, 2013

2012

Maximizing Conjunctive Views in Deletion Propagation.

Benny Kimelfeld, Jan Vondrák, Ryan Williams

ACM Trans. Database Syst., 2012

Online and stochastic variants of welfare maximization

Mikhail Kapralov, Ian Post, Jan Vondrák

CoRR, 2012

On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations

Shahar Dobzinski, Jan Vondrák

CoRR, 2012

From query complexity to computational complexity.

Shahar Dobzinski, Jan Vondrák

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The computational complexity of truthfulness in combinatorial auctions.

Shahar Dobzinski, Jan Vondrák

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

2011

Maximizing Non-monotone Submodular Functions.

Uriel Feige, Vahab S. Mirrokni, Jan Vondrák

SIAM J. Comput., 2011

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.

Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák

SIAM J. Comput., 2011

An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries

Shaddin Dughmi, Tim Roughgarden, Jan Vondrák, Qiqi Yan

CoRR, 2011

On Principles of Egocentric Person Search in Social Networks.

Sara Cohen, Benny Kimelfeld, Georgia Koutrika, Jan Vondrák

Proceedings of the First International Workshop on Searching and Integrating New Web Data Sources, 2011

Submodular Maximization by Simulated Annealing.

Shayan Oveis Gharan, Jan Vondrák

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.

Chandra Chekuri, Jan Vondrák, Rico Zenklusen

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

The Submodular Welfare Problem with Demand Queries.

Uriel Feige, Jan Vondrák

Theory Comput., 2010

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties.

Jon Lee, Maxim Sviridenko, Jan Vondrák

Math. Oper. Res., 2010

A note on concentration of submodular functions

Jan Vondrák

CoRR, 2010

A randomized embedding algorithm for trees.

Benny Sudakov, Jan Vondrák

Comb., 2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.

Chandra Chekuri, Jan Vondrák, Rico Zenklusen

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Disjoint bases in a polymatroid.

Gruia Calinescu, Chandra Chekuri, Jan Vondrák

Random Struct. Algorithms, 2009

Randomized Pipage Rounding for Matroid Polytopes and Applications

Chandra Chekuri, Jan Vondrák

CoRR, 2009

K-user fading interference channels: The ergodic very strong case.

Lalitha Sankar, Jan Vondrák, H. Vincent Poor

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

How many random edges make a dense hypergraph non-2-colorable?

Benny Sudakov, Jan Vondrák

Random Struct. Algorithms, 2008

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.

Brian C. Dean, Michel X. Goemans, Jan Vondrák

Math. Oper. Res., 2008

Optimal approximation for the submodular welfare problem in the value oracle model.

Jan Vondrák

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions.

Vahab S. Mirrokni, Michael Schapira, Jan Vondrák

Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

2007

Shortest-path metric approximation for random subgraphs.

Jan Vondrák

Random Struct. Algorithms, 2007

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract).

Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

2006

Covering minimum spanning trees of random subgraphs.

Michel X. Goemans, Jan Vondrák

Random Struct. Algorithms, 2006

A Ramsey-type result for the hypercube.

Noga Alon, Rados Radoicic, Benny Sudakov, Jan Vondrák

J. Graph Theory, 2006

On the diameter of separated point sets with many nearly equal distances.

János Pach, Rados Radoicic, Jan Vondrák

Eur. J. Comb., 2006

Nearly equal distances and Szemerédi's regularity lemma.

János Pach, Rados Radoicic, Jan Vondrák

Comput. Geom., 2006

Stochastic Covering and Adaptivity.

Michel X. Goemans, Jan Vondrák

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.

Uriel Feige, Jan Vondrák

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Adaptivity and approximation for stochastic packing problems.

Brian C. Dean, Michel X. Goemans, Jan Vondrák

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2003

Towards a theory of frustrated degeneracy.

Martin Loebl, Jan Vondrák

Discret. Math., 2003

Wide partitions, Latin tableaux, and Rota's basis conjecture.

Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan Vondrák

Adv. Appl. Math., 2003

2001

Optimization via enumeration: a new algorithm for the Max Cut Problem.

Anna Galluccio, Martin Loebl, Jan Vondrák

Math. Program., 2001

The limit checker number of a graph.

Robert Sámal, Jan Vondrák

Discret. Math., 2001

1999

Visibility Representations of Complete Graphs.

Robert Babilon, Helena Nyklová, Ondrej Pangrác, Jan Vondrák

Proceedings of the Graph Drawing, 7th International Symposium, 1999