Jan Vondrák

According to our database1, Jan Vondrák authored at least 77 papers between 1999 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Tight bounds on 1 approximation and learning of self-bounding functions.
Theor. Comput. Sci., 2020

An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles.
SIAM J. Comput., 2020

Submodular Maximization Through Barrier Functions.
CoRR, 2020

A polynomial lower bound on adaptive complexity of submodular maximization.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019
Submodular Optimization in the MapReduce Model.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.
Proceedings of the Conference on Learning Theory, 2019

2018
Computing the Independence Polynomial: from the Tree Threshold down to the Roots.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Generalization Bounds for Uniformly Stable Algorithms.
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.
Math. Oper. Res., 2017

Stability and Recovery for Independence Systems.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

When Are Welfare Guarantees Robust?.
Proceedings of the Approximation, 2017

Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
SIAM J. Comput., 2016

Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations.
J. ACM, 2016

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

2015
Limitations of randomized mechanisms for combinatorial auctions.
Games Econ. Behav., 2015

An Algorithmic Proof of the Lopsided Lovasz Local Lemma.
CoRR, 2015

Sperner's Colorings, Hypergraph Labeling Problems and Fair Division.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Information-theoretic lower bounds for convex optimization with erroneous oracles.
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.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Lazier Than Lazy Greedy.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes.
SIAM J. Comput., 2014

Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions.
CoRR, 2014

Is Submodularity Testable?
Algorithmica, 2014

Multiway cut, pairwise realizable distributions, and descending thresholds.
Proceedings of the Symposium on Theory of Computing, 2014

Fast algorithms for maximizing submodular functions.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Exchangeability and Realizability: De Finetti Theorems on Graphs.
Proceedings of the Approximation, 2014

Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture.
Proceedings of the Approximation, 2014

2013
Structure and learning of valuation functions.
SIGecom Exch., 2013

Symmetry and Approximability of Submodular Maximization Problems.
SIAM J. Comput., 2013

Matroid Matching: The Power of Local Search.
SIAM J. Comput., 2013

Multi-Tuple Deletion Propagation: Approximations and Complexity.
Proc. VLDB Endow., 2013

Multiway Cut, the Golden Ratio, and Descending Thresholds.
CoRR, 2013

On Variants of the Matroid Secretary Problem.
Algorithmica, 2013

Online Submodular Welfare Maximization: Greedy is Optimal.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Communication Complexity of Combinatorial Auctions with Submodular Valuations.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Eagle-eyed elephant: split-oriented indexing in Hadoop.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.
Proceedings of the COLT 2013, 2013

2012
Maximizing Conjunctive Views in Deletion Propagation.
ACM Trans. Database Syst., 2012

Online and stochastic variants of welfare maximization
CoRR, 2012

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

From query complexity to computational complexity.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The computational complexity of truthfulness in combinatorial auctions.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

2011
Maximizing Non-monotone Submodular Functions.
SIAM J. Comput., 2011

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.
SIAM J. Comput., 2011

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

On Principles of Egocentric Person Search in Social Networks.
Proceedings of the First International Workshop on Searching and Integrating New Web Data Sources, 2011

Submodular Maximization by Simulated Annealing.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010
The Submodular Welfare Problem with Demand Queries.
Theory Comput., 2010

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties.
Math. Oper. Res., 2010

A note on concentration of submodular functions
CoRR, 2010

A randomized embedding algorithm for trees.
Combinatorica, 2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Disjoint bases in a polymatroid.
Random Struct. Algorithms, 2009

K-User Fading Interference Channels: The Ergodic Very Strong Case
CoRR, 2009

Randomized Pipage Rounding for Matroid Polytopes and Applications
CoRR, 2009

2008
How many random edges make a dense hypergraph non-2-colorable?
Random Struct. Algorithms, 2008

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.
Math. Oper. Res., 2008

Optimal approximation for the submodular welfare problem in the value oracle model.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

2007
Shortest-path metric approximation for random subgraphs.
Random Struct. Algorithms, 2007

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract).
Proceedings of the Integer Programming and Combinatorial Optimization, 2007

2006
Covering minimum spanning trees of random subgraphs.
Random Struct. Algorithms, 2006

A Ramsey-type result for the hypercube.
Journal of Graph Theory, 2006

On the diameter of separated point sets with many nearly equal distances.
Eur. J. Comb., 2006

Nearly equal distances and Szemerédi's regularity lemma.
Comput. Geom., 2006

Stochastic Covering and Adaptivity.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Adaptivity and approximation for stochastic packing problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2003
Towards a theory of frustrated degeneracy.
Discret. Math., 2003

Wide partitions, Latin tableaux, and Rota's basis conjecture.
Adv. Appl. Math., 2003

2001
Optimization via enumeration: a new algorithm for the Max Cut Problem.
Math. Program., 2001

The limit checker number of a graph.
Discret. Math., 2001

1999
Visibility Representations of Complete Graphs.
Proceedings of the Graph Drawing, 7th International Symposium, 1999


  Loading...