Gábor Tardos

160 papers A* 25A 7B 1C 1Journal 111Unranked 15
YearRankTypeTitle / Venue / Authors
2026 A* conf
On a Clique Game and the Erdős-Hajnal Problem on High-Chromatic High-Girth Subgraphs.
SODA
Seth Pettie, Gábor Tardos, Bartosz Walczak
2025 A* conf
A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices.
SODA
Seth Pettie, Gábor Tardos
2025 J jnl
A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices.
Comb.
Seth Pettie, Gábor Tardos
2025 J jnl
Unavoidable patterns and plane paths in dense topological graphs.
CoRR
Balázs Keszegh, Andrew Suk, Gábor Tardos, Ji Zeng
2024 J jnl
A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices.
CoRR
Seth Pettie, Gábor Tardos
2024 J jnl
Disjointness graphs of short polygonal chains.
J. Comb. Theory B
János Pach, Gábor Tardos, Géza Tóth
2024 A* conf
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices.
SODA
Seth Pettie, Gábor Tardos
2024 J jnl
Random Necklaces Require Fewer Cuts.
SIAM J. Discret. Math.
Noga Alon, Dor Elboim, János Pach, Gábor Tardos
2024 J jnl
Where Have All the Grasshoppers Gone?
Am. Math. Mon.
János Pach, Gábor Tardos
2023 J jnl
A Characterization of Edge-Ordered Graphs with Almost Linear Extremal Functions.
Comb.
Gaurav Kucheriya, Gábor Tardos
2023 J jnl
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices.
CoRR
Seth Pettie, Gábor Tardos
2023 J jnl
Successive vertex orderings of fully regular graphs.
J. Comb. Theory A
Lixing Fang, Hao Huang, János Pach, Gábor Tardos, Junchi Zuo
2023 J jnl
Turán problems for edge-ordered graphs.
J. Comb. Theory B
Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Dömötör Pálvölgyi, Gábor Tardos, Máté Vizer
2022 J jnl
Convergence and Limits of Finite Trees.
Comb.
Gábor Elek, Gábor Tardos
2022 J jnl
Crossings between non-homotopic edges.
J. Comb. Theory B
János Pach, Gábor Tardos, Géza Tóth
2022 A* conf
Disjointness Graphs of Short Polygonal Chains.
SoCG
János Pach, Gábor Tardos, Géza Tóth
2021 J jnl
Disjointness graphs of segments in the space.
Comb. Probab. Comput.
János Pach, Gábor Tardos, Géza Tóth
2021 J jnl
Partitioning Transitive Tournaments into Isomorphic Digraphs.
Order
Attila Sali, Gábor Simonyi, Gábor Tardos
2020 A conf
Crossings Between Non-homotopic Edges.
GD
János Pach, Gábor Tardos, Géza Tóth
2020 J jnl
Unlabeled compression schemes exceeding the VC-dimension.
Discret. Appl. Math.
Dömötör Pálvölgyi, Gábor Tardos
2019 — conf
Extremal theory of vertex or edge ordered graphs.
BCC
Gábor Tardos
2019 J jnl
On the Turán number of ordered forests.
J. Comb. Theory A
Dániel Korándi, Gábor Tardos, István Tomon, Craig Weidert
2019 J jnl
Planar Point Sets Determine Many Pairwise Crossing Segments.
CoRR
János Pach, Natan Rubin, Gábor Tardos
2019 A* conf
Planar point sets determine many pairwise crossing segments.
STOC
János Pach, Natan Rubin, Gábor Tardos
2018 J jnl
Tilings with noncongruent triangles.
Eur. J. Comb.
Andrey Kupavskii, János Pach, Gábor Tardos
2018 J jnl
Unlabeled Compression Schemes Exceeding the VC-dimension.
CoRR
Dömötör Pálvölgyi, Gábor Tardos
2017 J jnl
A Crossing Lemma for Jordan Curves.
CoRR
János Pach, Natan Rubin, Gábor Tardos
2017 J jnl
Controlling Lipschitz functions.
CoRR
Andrey Kupavskii, János Pach, Gábor Tardos
2017 A* conf
Disjointness Graphs of Segments.
SoCG
János Pach, Gábor Tardos, Géza Tóth
2017 A* conf
On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers.
SODA
Chaya Keller, Shakhar Smorodinsky, Gábor Tardos
2017 J jnl
On the Turán number of ordered forests.
Electron. Notes Discret. Math.
Dániel Korándi, Gábor Tardos, István Tomon, Craig Weidert
2017 J jnl
Regular families of forests, antichains and duality pairs of relational structures.
Comb.
Péter L. Erdös, Dömötör Pálvölgyi, Claude Tardif, Gábor Tardos
2017 J jnl
Tilings of the plane with unit area triangles of bounded diameter.
CoRR
Andrey Kupavskii, János Pach, Gábor Tardos
2017 J jnl
Tilings with noncongruent triangles.
CoRR
Andrey Kupavskii, János Pach, Gábor Tardos
2016 A* conf
Beyond the Richter-Thomassen Conjecture.
SODA
János Pach, Natan Rubin, Gábor Tardos
2016 J jnl
Improved bounds for the randomized decision tree Complexity of recursive majority.
Random Struct. Algorithms
Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao
2016 J jnl
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.
Comb. Probab. Comput.
János Pach, Natan Rubin, Gábor Tardos
2016 J jnl
Separation with restricted families of sets.
J. Comb. Theory A
Zsolt Lángi, Márton Naszódi, János Pach, Gábor Tardos, Géza Tóth
2016 J jnl
The Local Lemma Is Asymptotically Tight for SAT.
J. ACM
Heidi Gebauer, Tibor Szabó, Gábor Tardos
2015 J jnl
Beyond the Richter-Thomassen Conjecture.
CoRR
János Pach, Natan Rubin, Gábor Tardos
2015 J jnl
Cross-Intersecting Families of Vectors.
Graphs Comb.
János Pach, Gábor Tardos
2015 J jnl
Erdős-Pyber Theorem for Hypergraphs and Secret Sharing.
Graphs Comb.
László Csirmaz, Péter Ligeti, Gábor Tardos
2015 A* conf
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.
SODA
János Pach, Natan Rubin, Gábor Tardos
2015 J jnl
Relations between the Local Chromatic Number and Its Directed Version.
J. Graph Theory
Gábor Simonyi, Gábor Tardos, Ambrus Zsbán
2014 J jnl
Conflict-Free Colouring of Graphs.
Comb. Probab. Comput.
Roman Glebov, Tibor Szabó, Gábor Tardos
2014 J jnl
On List Coloring and List Homomorphism of Permutation and Interval Graphs.
SIAM J. Discret. Math.
Jessica A. Enright, Lorna Stewart, Gábor Tardos
2014 J jnl
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.
CoRR
János Pach, Natan Rubin, Gábor Tardos
2014 J jnl
On-line secret sharing.
CoRR
László Csirmaz, Gábor Tardos
2014 J jnl
The visible perimeter of an arrangement of disks.
Comput. Geom.
Gabriel Nivasch, János Pach, Gábor Tardos
2013 J jnl
Caterpillar Dualities and Regular Languages.
SIAM J. Discret. Math.
Péter L. Erdös, Claude Tardif, Gábor Tardos
2013 — conf
Cross-Intersecting Families of Vectors.
JCDCGG
János Pach, Gábor Tardos
2013 J jnl
Erdős-Pyber theorem for hypergraphs and secret sharing.
CoRR
László Csirmaz, Péter Ligeti, Gábor Tardos
2013 J jnl
Improved bounds for the randomized decision tree complexity of recursive majority.
CoRR
Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao
2013 J jnl
Local chromatic number of quadrangulations of surfaces.
Comb.
Bojan Mohar, Gábor Simonyi, Gábor Tardos
2013 J jnl
On Infinite-finite Duality Pairs of Directed Graphs.
Order
Péter L. Erdös, Claude Tardif, Gábor Tardos
2013 A* conf
On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems.
FOCS
Mert Saglam, Gábor Tardos
2013 J jnl
On the communication complexity of sparse set disjointness and exists-equal problems
CoRR
Mert Saglam, Gábor Tardos
2013 J jnl
Optimal Information Rate of Secret Sharing Schemes on Trees.
IEEE Trans. Inf. Theory
László Csirmaz, Gábor Tardos
2013 J jnl
Optimal information rate of secret sharing schemes on trees
CoRR
László Csirmaz, Gábor Tardos
2013 J jnl
The Range of a Random Walk on a Comb.
Electron. J. Comb.
János Pach, Gábor Tardos
2012 J jnl
Caterpillar dualities and regular languages
CoRR
Péter L. Erdös, Claude Tardif, Gábor Tardos
2012 J jnl
On List Colouring and List Homomorphism of Permutation and Interval Graphs
CoRR
Jessica A. Enright, Lorna Stewart, Gábor Tardos
2012 J jnl
On infinite-finite duality pairs of directed graphs
CoRR
Péter L. Erdös, Claude Tardif, Gábor Tardos
2012 J jnl
On infinite-finite tree-duality pairs of relational structures
CoRR
Péter L. Erdös, Dömötör Pálvölgyi, Claude Tardif, Gábor Tardos
2012 J jnl
On-line secret sharing.
Des. Codes Cryptogr.
László Csirmaz, Gábor Tardos
2012 J jnl
Piercing quasi-rectangles - On a problem of Danzer and Rogers.
J. Comb. Theory A
János Pach, Gábor Tardos
2012 J jnl
Remarks on a Ramsey theory for trees.
Comb.
János Pach, Gábor Tardos, József Solymosi
2012 A conf
The Visible Perimeter of an Arrangement of Disks.
GD
Gabriel Nivasch, János Pach, Gábor Tardos
2012 J jnl
The visible perimeter of an arrangement of disks
CoRR
Gabriel Nivasch, János Pach, Gábor Tardos
2011 J jnl
On directed local chromatic number, shift graphs, and Borsuk-like graphs.
J. Graph Theory
Gábor Simonyi, Gábor Tardos
2011 J jnl
On-line secret sharing.
IACR Cryptol. ePrint Arch.
László Csirmaz, Gábor Tardos
2011 B conf
Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers.
WADS
János Pach, Gábor Tardos
2011 A* conf
The Local Lemma is Tight for SAT.
SODA
Heidi Gebauer, Tibor Szabó, Gábor Tardos
2011 A* conf
Tight bounds for Lp samplers, finding duplicates in streams, and related problems.
PODS
Hossein Jowhari, Mert Saglam, Gábor Tardos
2011 — conf
Tight lower bounds for the size of epsilon-nets.
SCG
János Pach, Gábor Tardos
2010 J jnl
A constructive proof of the general lovász local lemma.
J. ACM
Robin A. Moser, Gábor Tardos
2010 — conf
Capacity of Collusion Secure Fingerprinting - A Tradeoff between Rate and Efficiency - (Extended Abstract of Invited Talk).
Information Hiding
Gábor Tardos
2010 J jnl
Coloring axis-parallel rectangles.
J. Comb. Theory A
János Pach, Gábor Tardos
2010 J jnl
Crossing numbers of imbalanced graphs.
J. Graph Theory
János Pach, József Solymosi, Gábor Tardos
2010 J jnl
The Local Lemma Is Tight for SAT
CoRR
Heidi Gebauer, Tibor Szabó, Gábor Tardos
2010 J jnl
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems
CoRR
Hossein Jowhari, Mert Saglam, Gábor Tardos
2010 J jnl
Tight lower bounds for the size of epsilon-nets
CoRR
János Pach, Gábor Tardos
2009 J jnl
A constructive proof of the general Lovasz Local Lemma
CoRR
Robin A. Moser, Gábor Tardos
2009 J jnl
Conflict-Free Colourings of Graphs and Hypergraphs.
Comb. Probab. Comput.
János Pach, Gábor Tardos
2009 J jnl
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.
Random Struct. Algorithms
Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos
2009 A* conf
High rate fingerprinting codes and the fingerprinting capacity.
SODA
Ehsan Amiri, Gábor Tardos
2009 J jnl
Secret sharing on trees: problem solved.
IACR Cryptol. ePrint Arch.
László Csirmaz, Gábor Tardos
2008 A* conf
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.
SODA
Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos
2008 J jnl
Graph Colouring with No Large Monochromatic Components.
Comb. Probab. Comput.
Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos
2008 J jnl
Optimal probabilistic fingerprint codes.
J. ACM
Gábor Tardos
2007 J jnl
Colorful subgraphs in Kneser-like graphs.
Eur. J. Comb.
Gábor Simonyi, Gábor Tardos
2007 — conf
Coloring Axis-Parallel Rectangles.
KyotoCGGT
János Pach, Gábor Tardos
2007 J jnl
Crossing Stars in Topological Graphs.
SIAM J. Discret. Math.
Gábor Tardos, Géza Tóth
2007 J jnl
Deterministic random walks on the integers.
Eur. J. Comb.
Joshua N. Cooper, Benjamin Doerr, Joel H. Spencer, Gábor Tardos
2007 J jnl
Graph coloring with no large monochromatic components.
Electron. Notes Discret. Math.
Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos
2007 J jnl
Multiple Coverings of the Plane with Triangles.
Discret. Comput. Geom.
Gábor Tardos, Géza Tóth
2007 J jnl
On the maximum number of edges in quasi-planar graphs.
J. Comb. Theory A
Eyal Ackerman, Gábor Tardos
2007 — conf
On the number of k-rich transformations.
SCG
József Solymosi, Gábor Tardos
2007 J jnl
Partitioning multi-dimensional sets in a small number of "uniform" parts.
Eur. J. Comb.
Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2006 — conf
Deterministic Random Walks.
ANALCO
Joshua N. Cooper, Benjamin Doerr, Joel Spencer, Gábor Tardos
2006 J jnl
Extremal Problems For Transversals In Graphs With Bounded Degree.
Comb.
Tibor Szabó, Gábor Tardos
2006 J jnl
Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs.
Discret. Comput. Geom.
János Pach, Rados Radoicic, Gábor Tardos, Géza Tóth
2006 J jnl
Intersection reverse sequences and geometric applications.
J. Comb. Theory A
Adam Marcus, Gábor Tardos
2006 J jnl
Local Chromatic Number, KY Fan's Theorem, And Circular Colorings.
Comb.
Gábor Simonyi, Gábor Tardos
2006 J jnl
Waiting for a Bat to Fly By (in Polynomial Time).
Comb. Probab. Comput.
Itai Benjamini, Gady Kozma, László Lovász, Dan Romik, Gábor Tardos
2005 — conf
Forbidden patterns and unit distances.
SCG
János Pach, Gábor Tardos
2005 — conf
Indecomposable Coverings.
CJCDGCGT
János Pach, Gábor Tardos, Géza Tóth
2005 J jnl
On 0-1 matrices and small excluded submatrices.
J. Comb. Theory A
Gábor Tardos
2005 J jnl
Partitioning multi-dimensional sets in a small number of "uniform" parts
Electron. Colloquium Comput. Complex.
Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2004 — conf
Crossing Stars in Topological Graphs.
JCDCG
Gábor Tardos, Géza Tóth
2004 J jnl
Distinct Distances in Three and Higher Dimensions.
Comb. Probab. Comput.
Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
2004 J jnl
Excluded permutation matrices and the Stanley-Wilf conjecture.
J. Comb. Theory A
Adam Marcus, Gábor Tardos
2004 J jnl
Geometric graphs with no self-intersecting path of length three.
Eur. J. Comb.
János Pach, Rom Pinchasi, Gábor Tardos, Géza Tóth
2004 — conf
Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract].
SCG
János Pach, Rados Radoicic, Gábor Tardos, Géza Tóth
2004 A conf
Intersection Reverse Sequences and Geometric Applications.
GD
Adam Marcus, Gábor Tardos
2003 J jnl
A Note on Non-Deterministic Communication Complexity with Few Witnesses.
Theory Comput. Syst.
Vince Grolmusz, Gábor Tardos
2003 J jnl
Bounded size components--partitions and transversals.
J. Comb. Theory B
Penny E. Haxell, Tibor Szabó, Gábor Tardos
2003 A* conf
Distinct distances in three and higher dimensions.
STOC
Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
2003 A* conf
Optimal probabilistic fingerprint codes.
STOC
Gábor Tardos
2002 J jnl
Covering lattice points by subspaces.
Period. Math. Hung.
Imre Bárány, Gergely Harcos, János Pach, Gábor Tardos
2002 A conf
Geometric Graphs with No Self-intersecting Path of Length Three.
GD
János Pach, Rom Pinchasi, Gábor Tardos, Géza Tóth
2002 J jnl
Isosceles Triangles Determined by a Planar Point Set.
Graphs Comb.
János Pach, Gábor Tardos
2002 J jnl
On the Boundary Complexity of the Union of Fat Triangles.
SIAM J. Comput.
János Pach, Gábor Tardos
2002 J jnl
On the Knowledge Complexity of
Comb.
Erez Petrank, Gábor Tardos
2002 J jnl
The k Most Frequent Distances in the Plane.
Discret. Comput. Geom.
József Solymosi, Gábor Tardos, Csaba D. Tóth
2002 J jnl
Untangling a Polygon.
Discret. Comput. Geom.
János Pach, Gábor Tardos
2001 J jnl
A Multidimensional Generalization Of The Erdös-Szekeres Lemma On Monotone Subsequences.
Comb. Probab. Comput.
Tibor Szabó, Gábor Tardos
2001 J jnl
An Improved Bound for
Discret. Comput. Geom.
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
2001 J jnl
Separating convex sets by straight lines.
Discret. Math.
János Pach, Gábor Tardos
2001 A conf
Untangling a Polygon.
GD
János Pach, Gábor Tardos
2000 C conf
An Improved Bound for k-Sets in Three Dimensions.
EuroCG
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
2000 — conf
An improved bound for
SCG
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
2000 J jnl
Cutting Glass.
Discret. Comput. Geom.
János Pach, Gábor Tardos
2000 — conf
Cutting glass.
SCG
János Pach, Gábor Tardos
2000 J jnl
Lower Bounds for (MOD
SIAM J. Comput.
Vince Grolmusz, Gábor Tardos
2000 A* conf
On the boundary complexity of the union of fat triangles.
FOCS
János Pach, Gábor Tardos
2000 J jnl
Ups and Downs of First Order Sentences on Random Graphs.
Comb.
Joel Spencer, Gábor Tardos
1999 J jnl
Arthur-Merlin Games in Boolean Decision Trees.
J. Comput. Syst. Sci.
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1999 J jnl
Linear Hash Functions.
J. ACM
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
1998 J jnl
A Lower Bound on the Mod 6 Degree of the Or Function.
Comput. Complex.
Gábor Tardos, David A. Mix Barrington
1998 A conf
Arthur-Merlin Games in Boolean Decision Trees.
CCC
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1998 A* conf
Lower Bounds for (MOD p - MOD m) Circuits.
FOCS
Vince Grolmusz, Gábor Tardos
1998 J jnl
Lower Bounds for (MOD p -- MOD m) Circuits
Electron. Colloquium Comput. Complex.
Vince Grolmusz, Gábor Tardos
1997 J jnl
Arthur-Merlin Games in Boolean Decision Trees
Electron. Colloquium Comput. Complex.
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin
1997 A* conf
Is Linear Hashing Good?
STOC
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
1997 A* conf
Probabilistically Checkable Proofs with Zero Knowledge.
STOC
Joe Kilian, Erez Petrank, Gábor Tardos
1997 A conf
The Communication Complexity of the Universal Relation.
CCC
Gábor Tardos, Uri Zwick
1996 J jnl
Multi-prover Encoding Schemes and Three-prover Proof Systems.
J. Comput. Syst. Sci.
Gábor Tardos
1996 J jnl
On Point Covers of Multiple Intervals and Axis-Parallel Rectangles.
Comb.
Gyula Károlyi, Gábor Tardos
1996 A* conf
On the Knowledge Complexity of NP.
FOCS
Erez Petrank, Gábor Tardos
1995 — conf
A Lower Bound on the Mod 6 Degree of the OR Function.
ISTCS
Gábor Tardos, David A. Mix Barrington
1995 J jnl
Transversals of 2-Intervals, a Topological Approach.
Comb.
Gábor Tardos
1994 — conf
Multi-Prover Encoding Schemes and Three-Prover Proof Systems.
SCT
Gábor Tardos
1994 J jnl
On the Power of Randomization in On-Line Algorithms.
Algorithmica
Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson
1990 A* conf
A Competitive 3-Server Algorithm.
SODA
Piotr Berman, Howard J. Karloff, Gábor Tardos
1990 A* conf
On the Power of Randomization in Online Algorithms (Extended Abstract)
STOC
Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson
1989 A* conf
Decision Versus Search Problems in Super-Polynomial Time
FOCS
Russell Impagliazzo, Gábor Tardos
1989 A* conf
Planning and Learning in Permutation Groups
FOCS
Amos Fiat, Shahar Moses, Adi Shamir, Ilan Shimshoni, Gábor Tardos
1989 J jnl
Query complexity, or why is it difficult to seperate NP
Comb.
Gábor Tardos
1988 J jnl
Polynomial Bound for a Chip Firing Game on Graphs.
SIAM J. Discret. Math.
Gábor Tardos