Jan Vondrák

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

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

2019
Submodular Optimization in the MapReduce Model.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 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

2015
Limitations of randomized mechanisms for combinatorial auctions.
Games and Economic Behavior, 2015

Optimal approximation for submodular and supermodular optimization with bounded curvature.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles.
Proceedings of the IEEE 56th Annual Symposium on Foundations of 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

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

Optimal bounds on approximation of submodular and XOS functions by juntas.
Proceedings of the 2014 Information Theory and Applications Workshop, 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 Exchanges, 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.
PVLDB, 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

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 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

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

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 function maximization via the multilinear relaxation and contention resolution schemes.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 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

Maximizing conjunctive views in deletion propagation.
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Is Submodularity Testable?
Proceedings of the Innovations in Computer Science, 2011

Limitations of Randomized Mechanisms for Combinatorial Auctions.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On Variants of the Matroid Secretary Problem.
Proceedings of the Algorithms - ESA 2011, 2011

2010
The Submodular Welfare Problem with Demand Queries.
Theory of Computing, 2010

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

A randomized embedding algorithm for trees.
Combinatorica, 2010

Matroid matching: the power of local search.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 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

Symmetry and Approximability of Submodular Maximization Problems.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties.
Proceedings of the Approximation, 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

Maximizing Non-Monotone Submodular Functions.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 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

2004
Covering minimum spanning trees of random subgraphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Towards a theory of frustrated degeneracy.
Discrete Mathematics, 2003

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

The limit checker number of a graph.
Discrete Mathematics, 2001

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


  Loading...