2025
A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices.
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025
2024
Where Have All the Grasshoppers Gone?
Am. Math. Mon., March, 2024
Disjointness graphs of short polygonal chains.
J. Comb. Theory B, January, 2024
Random Necklaces Require Fewer Cuts.
SIAM J. Discret. Math., 2024
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
2023
A Characterization of Edge-Ordered Graphs with Almost Linear Extremal Functions.
Comb., December, 2023
Turán problems for edge-ordered graphs.
J. Comb. Theory B, May, 2023
Successive vertex orderings of fully regular graphs.
J. Comb. Theory A, 2023
2022
Crossings between non-homotopic edges.
J. Comb. Theory B, 2022
Convergence and Limits of Finite Trees.
Comb., 2022
2021
Partitioning Transitive Tournaments into Isomorphic Digraphs.
Order, 2021
Disjointness graphs of segments in the space.
Comb. Probab. Comput., 2021
2020
Unlabeled compression schemes exceeding the VC-dimension.
Discret. Appl. Math., 2020
2019
On the Turán number of ordered forests.
J. Comb. Theory A, 2019
Planar point sets determine many pairwise crossing segments.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
Extremal theory of vertex or edge ordered graphs.
Proceedings of the Surveys in Combinatorics, 2019: Invited lectures from the 27th British Combinatorial Conference, Birmingham, UK, July 29, 2019
2018
Tilings with noncongruent triangles.
Eur. J. Comb., 2018
2017
Tilings of the plane with unit area triangles of bounded diameter.
CoRR, 2017
A Crossing Lemma for Jordan Curves.
CoRR, 2017
Controlling Lipschitz functions.
CoRR, 2017
Regular families of forests, antichains and duality pairs of relational structures.
Comb., 2017
On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Disjointness Graphs of Segments.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017
2016
Improved bounds for the randomized decision tree Complexity of recursive majority.
Random Struct. Algorithms, 2016
Separation with restricted families of sets.
J. Comb. Theory A, 2016
The Local Lemma Is Asymptotically Tight for SAT.
J. ACM, 2016
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.
Comb. Probab. Comput., 2016
Beyond the Richter-Thomassen Conjecture.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
2015
Relations between the Local Chromatic Number and Its Directed Version.
J. Graph Theory, 2015
Cross-Intersecting Families of Vectors.
Graphs Comb., 2015
Erdős-Pyber Theorem for Hypergraphs and Secret Sharing.
Graphs Comb., 2015
2014
On List Coloring and List Homomorphism of Permutation and Interval Graphs.
SIAM J. Discret. Math., 2014
Conflict-Free Colouring of Graphs.
Comb. Probab. Comput., 2014
The visible perimeter of an arrangement of disks.
Comput. Geom., 2014
2013
Optimal Information Rate of Secret Sharing Schemes on Trees.
IEEE Trans. Inf. Theory, 2013
Caterpillar Dualities and Regular Languages.
SIAM J. Discret. Math., 2013
On Infinite-finite Duality Pairs of Directed Graphs.
Order, 2013
The Range of a Random Walk on a Comb.
Electron. J. Comb., 2013
Local chromatic number of quadrangulations of surfaces.
Comb., 2013
On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013
2012
Piercing quasi-rectangles - On a problem of Danzer and Rogers.
J. Comb. Theory A, 2012
Des. Codes Cryptogr., 2012
On infinite-finite tree-duality pairs of relational structures
CoRR, 2012
On List Colouring and List Homomorphism of Permutation and Interval Graphs
CoRR, 2012
Remarks on a Ramsey theory for trees.
Comb., 2012
2011
On directed local chromatic number, shift graphs, and Borsuk-like graphs.
J. Graph Theory, 2011
The Local Lemma is Tight for SAT.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Tight bounds for Lp samplers, finding duplicates in streams, and related problems.
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011
Tight lower bounds for the size of epsilon-nets.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011
2010
Crossing numbers of imbalanced graphs.
J. Graph Theory, 2010
Coloring axis-parallel rectangles.
J. Comb. Theory A, 2010
A constructive proof of the general lovász local lemma.
J. ACM, 2010
Capacity of Collusion Secure Fingerprinting - A Tradeoff between Rate and Efficiency - (Extended Abstract of Invited Talk).
Proceedings of the Information Hiding - 12th International Conference, 2010
2009
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.
Random Struct. Algorithms, 2009
Secret sharing on trees: problem solved.
IACR Cryptol. ePrint Arch., 2009
Conflict-Free Colourings of Graphs and Hypergraphs.
Comb. Probab. Comput., 2009
High rate fingerprinting codes and the fingerprinting capacity.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
2008
Optimal probabilistic fingerprint codes.
J. ACM, 2008
Graph Colouring with No Large Monochromatic Components.
Comb. Probab. Comput., 2008
2007
Crossing Stars in Topological Graphs.
SIAM J. Discret. Math., 2007
On the maximum number of edges in quasi-planar graphs.
J. Comb. Theory A, 2007
Graph coloring with no large monochromatic components.
Electron. Notes Discret. Math., 2007
Colorful subgraphs in Kneser-like graphs.
Eur. J. Comb., 2007
Deterministic random walks on the integers.
Eur. J. Comb., 2007
Multiple Coverings of the Plane with Triangles.
Discret. Comput. Geom., 2007
On the number of k-rich transformations.
Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007
2006
Intersection reverse sequences and geometric applications.
J. Comb. Theory A, 2006
Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs.
Discret. Comput. Geom., 2006
Waiting for a Bat to Fly By (in Polynomial Time).
Comb. Probab. Comput., 2006
Extremal Problems For Transversals In Graphs With Bounded Degree.
Comb., 2006
Local Chromatic Number, KY Fan's Theorem, And Circular Colorings.
Comb., 2006
Deterministic Random Walks.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006
2005
On 0-1 matrices and small excluded submatrices.
J. Comb. Theory A, 2005
Partitioning multi-dimensional sets in a small number of "uniform" parts
Electron. Colloquium Comput. Complex., 2005
Forbidden patterns and unit distances.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005
Indecomposable Coverings.
Proceedings of the Discrete Geometry, 2005
2004
Excluded permutation matrices and the Stanley-Wilf conjecture.
J. Comb. Theory A, 2004
Geometric graphs with no self-intersecting path of length three.
Eur. J. Comb., 2004
Distinct Distances in Three and Higher Dimensions.
Comb. Probab. Comput., 2004
Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract].
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004
2003
A Note on Non-Deterministic Communication Complexity with Few Witnesses.
Theory Comput. Syst., 2003
Bounded size components--partitions and transversals.
J. Comb. Theory B, 2003
2002
On the Boundary Complexity of the Union of Fat Triangles.
SIAM J. Comput., 2002
Covering lattice points by subspaces.
Period. Math. Hung., 2002
Isosceles Triangles Determined by a Planar Point Set.
Graphs Comb., 2002
The k Most Frequent Distances in the Plane.
Discret. Comput. Geom., 2002
Discret. Comput. Geom., 2002
On the Knowledge Complexity of <i>NP</i>.
Comb., 2002
2001
Separating convex sets by straight lines.
Discret. Math., 2001
An Improved Bound for <i>k</i>-Sets in Three Dimensions.
Discret. Comput. Geom., 2001
A Multidimensional Generalization Of The Erdös-Szekeres Lemma On Monotone Subsequences.
Comb. Probab. Comput., 2001
2000
Lower Bounds for (MOD<sub>p</sub>-MOD<sub>m</sub>) Circuits.
SIAM J. Comput., 2000
Discret. Comput. Geom., 2000
Ups and Downs of First Order Sentences on Random Graphs.
Comb., 2000
An Improved Bound for k-Sets in Three Dimensions.
EuroCG, 2000
1999
Arthur-Merlin Games in Boolean Decision Trees.
J. Comput. Syst. Sci., 1999
1998
Lower Bounds for (MOD p -- MOD m) Circuits
Electron. Colloquium Comput. Complex., 1998
A Lower Bound on the Mod 6 Degree of the Or Function.
Comput. Complex., 1998
1997
Probabilistically Checkable Proofs with Zero Knowledge.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
The Communication Complexity of the Universal Relation.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997
1996
Multi-prover Encoding Schemes and Three-prover Proof Systems.
J. Comput. Syst. Sci., 1996
On Point Covers of Multiple Intervals and Axis-Parallel Rectangles.
Comb., 1996
On the Knowledge Complexity of NP.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
1995
Transversals of 2-Intervals, a Topological Approach.
Comb., 1995
1994
On the Power of Randomization in On-Line Algorithms.
Algorithmica, 1994
1990
On the Power of Randomization in Online Algorithms (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
A Competitive 3-Server Algorithm.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990
1989
Query complexity, or why is it difficult to seperate NP <sup>A</sup> cap co NP<sup>A</sup> from P<sup>A</sup> by random oracles A?.
Comb., 1989
Decision Versus Search Problems in Super-Polynomial Time
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
Planning and Learning in Permutation Groups
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
1988
Polynomial Bound for a Chip Firing Game on Graphs.
SIAM J. Discret. Math., 1988
