Gábor Tardos

Am. Math. Mon., March, 2024

Disjointness graphs of short polygonal chains.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, January, 2024

On the Extremal Functions of Acyclic Forbidden 0-1 Matrices.

[BibT_eX]

[DOI]

Seth Pettie

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

2023

A Characterization of Edge-Ordered Graphs with Almost Linear Extremal Functions.

[BibT_eX]

[DOI]

Gaurav Kucheriya

Comb., December, 2023

Turán problems for edge-ordered graphs.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, May, 2023

Successive vertex orderings of fully regular graphs.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2023

2022

Crossings between non-homotopic edges.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2022

Convergence and Limits of Finite Trees.

[BibT_eX]

[DOI]

Gábor Elek

Comb., 2022

2021

Partitioning Transitive Tournaments into Isomorphic Digraphs.

[BibT_eX]

[DOI]

Attila Sali

Order, 2021

Disjointness graphs of segments in the space.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2021

2020

Unlabeled compression schemes exceeding the VC-dimension.

[BibT_eX]

[DOI]

Dömötör Pálvölgyi

Discret. Appl. Math., 2020

2019

Planar point sets determine many pairwise crossing segments.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Extremal theory of vertex or edge ordered graphs.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Andrey Kupavskii

Eur. J. Comb., 2018

2017

On the Turán number of ordered forests.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2017

Tilings of the plane with unit area triangles of bounded diameter.

[BibT_eX]

[DOI]

Andrey Kupavskii

CoRR, 2017

A Crossing Lemma for Jordan Curves.

[BibT_eX]

[DOI]

CoRR, 2017

Controlling Lipschitz functions.

[BibT_eX]

[DOI]

Andrey Kupavskii

CoRR, 2017

Regular families of forests, antichains and duality pairs of relational structures.

[BibT_eX]

[DOI]

Comb., 2017

On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers.

[BibT_eX]

[DOI]

Chaya Keller

Shakhar Smorodinsky

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Disjointness Graphs of Segments.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Improved bounds for the randomized decision tree Complexity of recursive majority.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

Separation with restricted families of sets.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2016

The Local Lemma Is Asymptotically Tight for SAT.

[BibT_eX]

[DOI]

Heidi Gebauer

J. ACM, 2016

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2016

Beyond the Richter-Thomassen Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Relations between the Local Chromatic Number and Its Directed Version.

[BibT_eX]

[DOI]

Ambrus Zsbán

J. Graph Theory, 2015

Cross-Intersecting Families of Vectors.

[BibT_eX]

[DOI]

Graphs Comb., 2015

Erdős-Pyber Theorem for Hypergraphs and Secret Sharing.

[BibT_eX]

[DOI]

Péter Ligeti

Graphs Comb., 2015

2014

On List Coloring and List Homomorphism of Permutation and Interval Graphs.

[BibT_eX]

[DOI]

Jessica A. Enright

Lorna Stewart

SIAM J. Discret. Math., 2014

Conflict-Free Colouring of Graphs.

[BibT_eX]

[DOI]

Roman Glebov

Comb. Probab. Comput., 2014

The visible perimeter of an arrangement of disks.

[BibT_eX]

[DOI]

Gabriel Nivasch

Comput. Geom., 2014

2013

Optimal Information Rate of Secret Sharing Schemes on Trees.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2013

Caterpillar Dualities and Regular Languages.

[BibT_eX]

[DOI]

Péter L. Erdös

Claude Tardif

SIAM J. Discret. Math., 2013

On Infinite-finite Duality Pairs of Directed Graphs.

[BibT_eX]

[DOI]

Péter L. Erdös

Claude Tardif

Order, 2013

The Range of a Random Walk on a Comb.

[BibT_eX]

[DOI]

Electron. J. Comb., 2013

Local chromatic number of quadrangulations of surfaces.

[BibT_eX]

[DOI]

Bojan Mohar

Comb., 2013

On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems.

[BibT_eX]

[DOI]

Mert Saglam

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Piercing quasi-rectangles - On a problem of Danzer and Rogers.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2012

On-line secret sharing.

[BibT_eX]

[DOI]

Des. Codes Cryptogr., 2012

On infinite-finite tree-duality pairs of relational structures

[BibT_eX]

[DOI]

CoRR, 2012

On List Colouring and List Homomorphism of Permutation and Interval Graphs

[BibT_eX]

[DOI]

Jessica A. Enright

Lorna Stewart

CoRR, 2012

Remarks on a Ramsey theory for trees.

[BibT_eX]

[DOI]

Comb., 2012

2011

On directed local chromatic number, shift graphs, and Borsuk-like graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2011

The Local Lemma is Tight for SAT.

[BibT_eX]

[DOI]

Heidi Gebauer

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.

[BibT_eX]

[DOI]

Hossein Jowhari

Mert Saglam

Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Tight lower bounds for the size of epsilon-nets.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Crossing numbers of imbalanced graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2010

Coloring axis-parallel rectangles.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2010

A constructive proof of the general lovász local lemma.

[BibT_eX]

[DOI]

Robin A. Moser

J. ACM, 2010

Capacity of Collusion Secure Fingerprinting - A Tradeoff between Rate and Efficiency - (Extended Abstract of Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the Information Hiding - 12th International Conference, 2010

2009

Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2009

Secret sharing on trees: problem solved.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2009

Conflict-Free Colourings of Graphs and Hypergraphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2009

High rate fingerprinting codes and the fingerprinting capacity.

[BibT_eX]

[DOI]

Ehsan Amiri

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Optimal probabilistic fingerprint codes.

[BibT_eX]

[DOI]

J. ACM, 2008

Graph Colouring with No Large Monochromatic Components.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2008

2007

Crossing Stars in Topological Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2007

On the maximum number of edges in quasi-planar graphs.

[BibT_eX]

[DOI]

Eyal Ackerman

J. Comb. Theory, Ser. A, 2007

Graph coloring with no large monochromatic components.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2007

Colorful subgraphs in Kneser-like graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2007

Deterministic random walks on the integers.

[BibT_eX]

[DOI]

Eur. J. Comb., 2007

Partitioning multi-dimensional sets in a small number of "uniform" parts.

[BibT_eX]

[DOI]

Nikolai K. Vereshchagin

Eur. J. Comb., 2007

Multiple Coverings of the Plane with Triangles.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2007

On the number of k-rich transformations.

[BibT_eX]

[DOI]

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

Intersection reverse sequences and geometric applications.

[BibT_eX]

[DOI]

Adam Marcus

J. Comb. Theory, Ser. A, 2006

Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2006

Waiting for a Bat to Fly By (in Polynomial Time).

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2006

Extremal Problems For Transversals In Graphs With Bounded Degree.

[BibT_eX]

[DOI]

Comb., 2006

Local Chromatic Number, KY Fan's Theorem, And Circular Colorings.

[BibT_eX]

[DOI]

Comb., 2006

Deterministic Random Walks.

[BibT_eX]

[DOI]

Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

2005

On 0-1 matrices and small excluded submatrices.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2005

Forbidden patterns and unit distances.

[BibT_eX]

[DOI]

Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

Indecomposable Coverings.

[BibT_eX]

[DOI]

Proceedings of the Discrete Geometry, 2005

2004

Excluded permutation matrices and the Stanley-Wilf conjecture.

[BibT_eX]

[DOI]

Adam Marcus

J. Comb. Theory, Ser. A, 2004

Geometric graphs with no self-intersecting path of length three.

[BibT_eX]

[DOI]

Eur. J. Comb., 2004

Distinct Distances in Three and Higher Dimensions.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2004

Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract].

[BibT_eX]

[DOI]

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003

A Note on Non-Deterministic Communication Complexity with Few Witnesses.

[BibT_eX]

[DOI]

Vince Grolmusz

Theory Comput. Syst., 2003

Bounded size components--partitions and transversals.

[BibT_eX]

[DOI]

Penny E. Haxell

J. Comb. Theory, Ser. B, 2003

2002

On the Boundary Complexity of the Union of Fat Triangles.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

Covering lattice points by subspaces.

[BibT_eX]

[DOI]

Period. Math. Hung., 2002

Isosceles Triangles Determined by a Planar Point Set.

[BibT_eX]

[DOI]

Graphs Comb., 2002

The k Most Frequent Distances in the Plane.

[BibT_eX]

[DOI]

Csaba D. Tóth

Discret. Comput. Geom., 2002

Untangling a Polygon.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2002

On the Knowledge Complexity of NP.

[BibT_eX]

[DOI]

Comb., 2002

2001

Separating convex sets by straight lines.

[BibT_eX]

[DOI]

Discret. Math., 2001

An Improved Bound for k-Sets in Three Dimensions.

[BibT_eX]

[DOI]

Micha Sharir

Shakhar Smorodinsky

Discret. Comput. Geom., 2001

A Multidimensional Generalization Of The Erdös-Szekeres Lemma On Monotone Subsequences.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2001

2000

Lower Bounds for (MODp-MODm) Circuits.

[BibT_eX]

[DOI]

Vince Grolmusz

SIAM J. Comput., 2000

Cutting Glass.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2000

Ups and Downs of First Order Sentences on Random Graphs.

[BibT_eX]

[DOI]

Joel Spencer

Comb., 2000

An Improved Bound for k-Sets in Three Dimensions.

[BibT_eX]

Micha Sharir

Shakhar Smorodinsky

EuroCG, 2000

1999

Arthur-Merlin Games in Boolean Decision Trees.

[BibT_eX]

[DOI]

Ran Raz

Oleg Verbitsky

Nikolai K. Vereshchagin

J. Comput. Syst. Sci., 1999

Linear Hash Functions.

[BibT_eX]

[DOI]

Noga Alon

Martin Dietzfelbinger

Peter Bro Miltersen

J. ACM, 1999

1998

Lower Bounds for (MOD p -- MOD m) Circuits

[BibT_eX]

[DOI]

Vince Grolmusz

Electron. Colloquium Comput. Complex., 1998

A Lower Bound on the Mod 6 Degree of the Or Function.

[BibT_eX]

[DOI]

David A. Mix Barrington

Comput. Complex., 1998

1997

Probabilistically Checkable Proofs with Zero Knowledge.

[BibT_eX]

[DOI]

Joe Kilian

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Is Linear Hashing Good?

[BibT_eX]

[DOI]

Noga Alon

Martin Dietzfelbinger

Peter Bro Miltersen

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

The Communication Complexity of the Universal Relation.

[BibT_eX]

[DOI]

Uri Zwick

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Multi-prover Encoding Schemes and Three-prover Proof Systems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

On Point Covers of Multiple Intervals and Axis-Parallel Rectangles.

[BibT_eX]

[DOI]

Gyula Károlyi

Comb., 1996

On the Knowledge Complexity of NP.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Transversals of 2-Intervals, a Topological Approach.

[BibT_eX]

[DOI]

Comb., 1995

1994

On the Power of Randomization in On-Line Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 1994

1990

On the Power of Randomization in Online Algorithms (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

A Competitive 3-Server Algorithm.

[BibT_eX]

[DOI]

Piotr Berman

Howard J. Karloff

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

1989

Query complexity, or why is it difficult to seperate NP A cap co NPA from PA by random oracles A?.

[BibT_eX]

[DOI]

Comb., 1989

Decision Versus Search Problems in Super-Polynomial Time

[BibT_eX]

[DOI]

Russell Impagliazzo

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]