Jan Vondrák - RankMe

142 papers A* 46A 5B 5Misc 1Journal 77Unranked 8

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Computation of Approximately Stable Committees in Approval-based Elections. CoRR Drew Gao, Yihang Sun, Jan Vondrák
2025	J	`jnl`	Cycle Cancellation for Submodular Fractional Allocations and Applications. CoRR Chandra Chekuri, Pooja Kulkarni, Ruta Mehta, Jan Vondrák
2025	J	`jnl`	Towards an optimal contention resolution scheme for matchings. Math. Program. Pranav Nuti, Jan Vondrák
2024	A*	`conf`	A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. STOC Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák
2024	J	`jnl`	A Simple Proof of the Nonuniform Kahn-Kalai Conjecture. SIAM J. Discret. Math. Bryan Park, Jan Vondrák
2024	J	`jnl`	Fairness and Incentive Compatibility via Percentage Fees. CoRR Shahar Dobzinski, Sigal Oren, Jan Vondrák
2024	A*	`conf`	Prophet Inequalities with Cancellation Costs. STOC Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, Jan Vondrák
2024	J	`jnl`	Prophet Inequalities with Cancellation Costs. CoRR Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, Jan Vondrák
2023	J	`jnl`	A constant factor approximation for Nash social welfare with subadditive valuations. CoRR Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák
2023	A*	`conf`	Approximating Nash Social Welfare by Matching and Local Search. STOC Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, Jan Vondrák
2023	A*	`conf`	Fairness and Incentive Compatibility via Percentage Fees. EC Shahar Dobzinski, Sigal Oren, Jan Vondrák
2023	A*	`conf`	Faster Submodular Maximization for Several Classes of Matroids. ICALP Monika Henzinger, Paul Liu, Jan Vondrák, Da Wei Zheng
2023	J	`jnl`	Faster Submodular Maximization for Several Classes of Matroids. CoRR Monika Henzinger, Paul Liu, Jan Vondrák, Da Wei Zheng
2023	A*	`conf`	On complex roots of the independence polynomial. SODA Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák
2023	A*	`conf`	Secretary Problems: The Power of a Single Sample. SODA Pranav Nuti, Jan Vondrák
2023	B	`conf`	Towards an Optimal Contention Resolution Scheme for Matchings. IPCO Pranav Nuti, Jan Vondrák
2022	J	`jnl`	Approximating Nash Social Welfare by Matching and Local Search. CoRR Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, Jan Vondrák
2022	A*	`conf`	Fixed-Price Approximations in Bilateral Trade. SODA Zi Yang Kang, Francisco Pernice, Jan Vondrák
2022	J	`jnl`	On complex roots of the independence polynomial. CoRR Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák
2022	J	`jnl`	On the Hardness of Dominant Strategy Mechanism Design. CoRR Shahar Dobzinski, Shiri Ron, Jan Vondrák
2022	A*	`conf`	On the hardness of dominant strategy mechanism design. STOC Shahar Dobzinski, Shiri Ron, Jan Vondrák
2022	J	`jnl`	Secretary Problems: The Power of a Single Sample. CoRR Pranav Nuti, Jan Vondrák
2022	J	`jnl`	Towards an Optimal Contention Resolution Scheme for Matchings. CoRR Pranav Nuti, Jan Vondrák
2021	A*	`conf`	A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. FOCS Wenzheng Li, Jan Vondrák
2021	J	`jnl`	A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. CoRR Wenzheng Li, Jan Vondrák
2021	A*	`conf`	Cardinality constrained submodular maximization for random streams. NeurIPS Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
2021	J	`jnl`	Cardinality constrained submodular maximization for random streams. CoRR Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
2021	A*	`conf`	Estimating the Nash Social Welfare for coverage and other submodular valuations. SODA Wenzheng Li, Jan Vondrák
2021	J	`jnl`	Estimating the Nash Social Welfare for coverage and other submodular valuations. CoRR Wenzheng Li, Jan Vondrák
2021	J	`jnl`	Fixed-Price Approximations in Bilateral Trade. CoRR Zi Yang Kang, Francisco Pernice, Jan Vondrák
2020	A*	`conf`	A polynomial lower bound on adaptive complexity of submodular maximization. STOC Wenzheng Li, Paul Liu, Jan Vondrák
2020	J	`jnl`	A polynomial lower bound on adaptive complexity of submodular maximization. CoRR Wenzheng Li, Paul Liu, Jan Vondrák
2020	J	`jnl`	An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles. SIAM J. Comput. Nicholas J. A. Harvey, Jan Vondrák
2020	A*	`conf`	Submodular Maximization Through Barrier Functions. NeurIPS Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, Jan Vondrák
2020	J	`jnl`	Submodular Maximization Through Barrier Functions. CoRR Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, Jan Vondrák
2020	J	`jnl`	Tight bounds on Theor. Comput. Sci. Vitaly Feldman, Pravesh Kothari, Jan Vondrák
2019	A*	`conf`	High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. COLT Vitaly Feldman, Jan Vondrák
2019	J	`jnl`	High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. CoRR Vitaly Feldman, Jan Vondrák
2019	—	`conf`	Submodular Optimization in the MapReduce Model. SOSA Paul Liu, Jan Vondrák
2018	A*	`conf`	Computing the Independence Polynomial: from the Tree Threshold down to the Roots. SODA Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák
2018	A*	`conf`	Generalization Bounds for Uniformly Stable Algorithms. NeurIPS Vitaly Feldman, Jan Vondrák
2018	J	`jnl`	Generalization Bounds for Uniformly Stable Algorithms. CoRR Vitaly Feldman, Jan Vondrák
2018	J	`jnl`	Submodular Optimization in the MapReduce Model. CoRR Paul Liu, Jan Vondrák
2017	J	`jnl`	Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature. Math. Oper. Res. Maxim Sviridenko, Jan Vondrák, Justin Ward
2017	A	`conf`	Stability and Recovery for Independence Systems. ESA Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák
2017	J	`jnl`	Stability and Recovery for Independence Systems. CoRR Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák
2017	B	`conf`	Tight Bounds on ℓ ALT Vitaly Feldman, Pravesh Kothari, Jan Vondrák
2017	—	`conf`	When Are Welfare Guarantees Robust?. APPROX-RANDOM Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák
2016	J	`jnl`	Computing the independence polynomial in Shearer's region for the LLL. CoRR Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák
2016	J	`jnl`	Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations. J. ACM Shahar Dobzinski, Jan Vondrák
2016	J	`jnl`	Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. SIAM J. Comput. Vitaly Feldman, Jan Vondrák
2016	J	`jnl`	When Are Welfare Guarantees Robust? CoRR Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák
2015	J	`jnl`	An Algorithmic Proof of the Lopsided Lovasz Local Lemma. CoRR Nicholas J. A. Harvey, Jan Vondrák
2015	A*	`conf`	An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles. FOCS Nicholas J. A. Harvey, Jan Vondrák
2015	—	`conf`	Information-theoretic lower bounds for convex optimization with erroneous oracles. NIPS Yaron Singer, Jan Vondrák
2015	A*	`conf`	Lazier Than Lazy Greedy. AAAI Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause
2015	J	`jnl`	Limitations of randomized mechanisms for combinatorial auctions. Games Econ. Behav. Shaddin Dughmi, Jan Vondrák
2015	J	`jnl`	Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. CoRR Alina Ene, Jan Vondrák, Yi Wu
2015	A	`conf`	On Multiplicative Weight Updates for Concave and Submodular Function Maximization. ITCS Chandra Chekuri, T. S. Jayram, Jan Vondrák
2015	A*	`conf`	Optimal approximation for submodular and supermodular optimization with bounded curvature. SODA Maxim Sviridenko, Jan Vondrák, Justin Ward
2015	A*	`conf`	Sperner's Colorings, Hypergraph Labeling Problems and Fair Division. SODA Maryam Mirzakhani, Jan Vondrák
2015	A*	`conf`	Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions. FOCS Vitaly Feldman, Jan Vondrák
2015	J	`jnl`	Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions. CoRR Vitaly Feldman, Jan Vondrák
2014	—	`conf`	Exchangeability and Realizability: De Finetti Theorems on Graphs. APPROX-RANDOM T. S. Jayram, Jan Vondrák
2014	A*	`conf`	Fast algorithms for maximizing submodular functions. SODA Ashwinkumar Badanidiyuru, Jan Vondrák
2014	—	`conf`	Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture. APPROX-RANDOM Alina Ene, Jan Vondrák
2014	J	`jnl`	Is Submodularity Testable? Algorithmica C. Seshadhri, Jan Vondrák
2014	J	`jnl`	Lazier Than Lazy Greedy. CoRR Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause
2014	A*	`conf`	Multiway cut, pairwise realizable distributions, and descending thresholds. STOC Ankit Sharma, Jan Vondrák
2014	J	`jnl`	Nearly Tight Bounds on ℓ CoRR Vitaly Feldman, Pravesh Kothari, Jan Vondrák
2014	Misc	`conf`	Optimal bounds on approximation of submodular and XOS functions by juntas. ITA Vitaly Feldman, Jan Vondrák
2014	J	`jnl`	Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. SIAM J. Comput. Chandra Chekuri, Jan Vondrák, Rico Zenklusen
2013	A*	`conf`	Communication Complexity of Combinatorial Auctions with Submodular Valuations. SODA Shahar Dobzinski, Jan Vondrák
2013	B	`conf`	Eagle-eyed elephant: split-oriented indexing in Hadoop. EDBT Mohamed Y. Eltabakh, Fatma Özcan, Yannis Sismanis, Peter J. Haas, Hamid Pirahesh, Jan Vondrák
2013	A*	`conf`	Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. SODA Alina Ene, Jan Vondrák, Yi Wu
2013	J	`jnl`	Matroid Matching: The Power of Local Search. SIAM J. Comput. Jon Lee, Maxim Sviridenko, Jan Vondrák
2013	J	`jnl`	Multi-Tuple Deletion Propagation: Approximations and Complexity. Proc. VLDB Endow. Benny Kimelfeld, Jan Vondrák, David P. Woodruff
2013	J	`jnl`	Multiway Cut, the Golden Ratio, and Descending Thresholds. CoRR Ankit Sharma, Jan Vondrák
2013	J	`jnl`	On Variants of the Matroid Secretary Problem. Algorithmica Shayan Oveis Gharan, Jan Vondrák
2013	A*	`conf`	Online Submodular Welfare Maximization: Greedy is Optimal. SODA Michael Kapralov, Ian Post, Jan Vondrák
2013	A*	`conf`	Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. FOCS Vitaly Feldman, Jan Vondrák
2013	J	`jnl`	Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. CoRR Vitaly Feldman, Jan Vondrák
2013	J	`jnl`	Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees CoRR Vitaly Feldman, Pravesh Kothari, Jan Vondrák
2013	A*	`conf`	Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. COLT Vitaly Feldman, Pravesh Kothari, Jan Vondrák
2013	J	`jnl`	Structure and learning of valuation functions. SIGecom Exch. Vitaly Feldman, Jan Vondrák
2013	J	`jnl`	Symmetry and Approximability of Submodular Maximization Problems. SIAM J. Comput. Jan Vondrák
2012	A*	`conf`	From query complexity to computational complexity. STOC Shahar Dobzinski, Jan Vondrák
2012	J	`jnl`	Maximizing Conjunctive Views in Deletion Propagation. ACM Trans. Database Syst. Benny Kimelfeld, Jan Vondrák, Ryan Williams
2012	J	`jnl`	On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations CoRR Shahar Dobzinski, Jan Vondrák
2012	J	`jnl`	Online and stochastic variants of welfare maximization CoRR Mikhail Kapralov, Ian Post, Jan Vondrák
2012	J	`jnl`	The Computational Complexity of Truthfulness in Combinatorial Auctions CoRR Shahar Dobzinski, Jan Vondrák
2012	A*	`conf`	The computational complexity of truthfulness in combinatorial auctions. EC Shahar Dobzinski, Jan Vondrák
2011	J	`jnl`	An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries CoRR Shaddin Dughmi, Tim Roughgarden, Jan Vondrák, Qiqi Yan
2011	A	`conf`	Is Submodularity Testable? ICS C. Seshadhri, Jan Vondrák
2011	A*	`conf`	Limitations of Randomized Mechanisms for Combinatorial Auctions. FOCS Shaddin Dughmi, Jan Vondrák
2011	J	`jnl`	Limitations of randomized mechanisms for combinatorial auctions CoRR Shaddin Dughmi, Jan Vondrák
2011	J	`jnl`	Maximizing Non-monotone Submodular Functions. SIAM J. Comput. Uriel Feige, Vahab S. Mirrokni, Jan Vondrák
2011	J	`jnl`	Maximizing a Monotone Submodular Function Subject to a Matroid Constraint. SIAM J. Comput. Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák
2011	A*	`conf`	Maximizing conjunctive views in deletion propagation. PODS Benny Kimelfeld, Jan Vondrák, Ryan Williams
2011	A*	`conf`	Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. SODA Chandra Chekuri, Jan Vondrák, Rico Zenklusen
2011	—	`conf`	On Principles of Egocentric Person Search in Social Networks. VLDS Sara Cohen, Benny Kimelfeld, Georgia Koutrika, Jan Vondrák
2011	J	`jnl`	On Variants of the Matroid Secretary Problem CoRR Shayan Oveis Gharan, Jan Vondrák
2011	A	`conf`	On Variants of the Matroid Secretary Problem. ESA Shayan Oveis Gharan, Jan Vondrák
2011	J	`jnl`	Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes CoRR Chandra Chekuri, Jan Vondrák, Rico Zenklusen
2011	A*	`conf`	Submodular Maximization by Simulated Annealing. SODA Shayan Oveis Gharan, Jan Vondrák
2011	A*	`conf`	Submodular function maximization via the multilinear relaxation and contention resolution schemes. STOC Jan Vondrák, Chandra Chekuri, Rico Zenklusen
2011	J	`jnl`	Symmetry and approximability of submodular maximization problems CoRR Jan Vondrák
2010	J	`jnl`	A note on concentration of submodular functions CoRR Jan Vondrák
2010	J	`jnl`	A randomized embedding algorithm for trees. Comb. Benny Sudakov, Jan Vondrák
2010	A*	`conf`	Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. FOCS Chandra Chekuri, Jan Vondrák, Rico Zenklusen
2010	J	`jnl`	Is submodularity testable? CoRR C. Seshadhri, Jan Vondrák
2010	A*	`conf`	Matroid matching: the power of local search. STOC Jon Lee, Maxim Sviridenko, Jan Vondrák
2010	J	`jnl`	Submodular Maximization by Simulated Annealing CoRR Shayan Oveis Gharan, Jan Vondrák
2010	J	`jnl`	Submodular Maximization over Multiple Matroids via Generalized Exchange Properties. Math. Oper. Res. Jon Lee, Maxim Sviridenko, Jan Vondrák
2010	J	`jnl`	The Submodular Welfare Problem with Demand Queries. Theory Comput. Uriel Feige, Jan Vondrák
2009	J	`jnl`	Disjoint bases in a polymatroid. Random Struct. Algorithms Gruia Calinescu, Chandra Chekuri, Jan Vondrák
2009	J	`jnl`	K-User Fading Interference Channels: The Ergodic Very Strong Case CoRR Lalitha Sankar, Jan Vondrák, H. Vincent Poor
2009	—	`conf`	K-user fading interference channels: The ergodic very strong case. Allerton Lalitha Sankar, Jan Vondrák, H. Vincent Poor
2009	J	`jnl`	Randomized Pipage Rounding for Matroid Polytopes and Applications CoRR Chandra Chekuri, Jan Vondrák
2009	—	`conf`	Submodular Maximization over Multiple Matroids via Generalized Exchange Properties. APPROX-RANDOM Jon Lee, Maxim Sviridenko, Jan Vondrák
2009	A*	`conf`	Symmetry and Approximability of Submodular Maximization Problems. FOCS Jan Vondrák
2008	J	`jnl`	Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. Math. Oper. Res. Brian C. Dean, Michel X. Goemans, Jan Vondrák
2008	J	`jnl`	How many random edges make a dense hypergraph non-2-colorable? Random Struct. Algorithms Benny Sudakov, Jan Vondrák
2008	A*	`conf`	Optimal approximation for the submodular welfare problem in the value oracle model. STOC Jan Vondrák
2008	A*	`conf`	Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. EC Vahab S. Mirrokni, Michael Schapira, Jan Vondrák
2007	A*	`conf`	Maximizing Non-Monotone Submodular Functions. FOCS Uriel Feige, Vahab S. Mirrokni, Jan Vondrák
2007	B	`conf`	Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract). IPCO Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák
2007	J	`jnl`	Shortest-path metric approximation for random subgraphs. Random Struct. Algorithms Jan Vondrák
2006	J	`jnl`	A Ramsey-type result for the hypercube. J. Graph Theory Noga Alon, Rados Radoicic, Benny Sudakov, Jan Vondrák
2006	A*	`conf`	Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. FOCS Uriel Feige, Jan Vondrák
2006	J	`jnl`	Covering minimum spanning trees of random subgraphs. Random Struct. Algorithms Michel X. Goemans, Jan Vondrák
2006	J	`jnl`	Nearly equal distances and Szemerédi's regularity lemma. Comput. Geom. János Pach, Rados Radoicic, Jan Vondrák
2006	J	`jnl`	On the diameter of separated point sets with many nearly equal distances. Eur. J. Comb. János Pach, Rados Radoicic, Jan Vondrák
2006	B	`conf`	Stochastic Covering and Adaptivity. LATIN Michel X. Goemans, Jan Vondrák
2005	A*	`conf`	Adaptivity and approximation for stochastic packing problems. SODA Brian C. Dean, Michel X. Goemans, Jan Vondrák
2004	A*	`conf`	Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. FOCS Brian C. Dean, Michel X. Goemans, Jan Vondrák
2004	A*	`conf`	Covering minimum spanning trees of random subgraphs. SODA Michel X. Goemans, Jan Vondrák
2003	J	`jnl`	Towards a theory of frustrated degeneracy. Discret. Math. Martin Loebl, Jan Vondrák
2003	J	`jnl`	Wide partitions, Latin tableaux, and Rota's basis conjecture. Adv. Appl. Math. Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan Vondrák
2001	J	`jnl`	Optimization via enumeration: a new algorithm for the Max Cut Problem. Math. Program. Anna Galluccio, Martin Loebl, Jan Vondrák
2001	J	`jnl`	The limit checker number of a graph. Discret. Math. Robert Sámal, Jan Vondrák
1999	A	`conf`	Visibility Representations of Complete Graphs. GD Robert Babilon, Helena Nyklová, Ondrej Pangrác, Jan Vondrák