Gábor Tardos
Person information
- affiliation: Simon Fraser University, School of Computing Science
- affiliation: Eötvös Loránd University, Computer Science Department
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
showing all ?? records
2010 – today
- 2017
- [j67]Péter L. Erdös, Dömötör Pálvölgyi, Claude Tardif, Gábor Tardos:
Regular families of forests, antichains and duality pairs of relational structures. Combinatorica 37(4): 651-672 (2017) - [j66]Dániel Korándi, Gábor Tardos, István Tomon, Craig Weidert:
On the Turán number of ordered forests. Electronic Notes in Discrete Mathematics 61: 773-779 (2017) - [c41]János Pach, Gábor Tardos, Géza Tóth:
Disjointness Graphs of Segments. Symposium on Computational Geometry 2017: 59:1-59:15 - [c40]Chaya Keller, Shakhar Smorodinsky, Gábor Tardos:
On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers. SODA 2017: 2254-2263 - [i26]Andrey Kupavskii, János Pach, Gábor Tardos:
Controlling Lipschitz functions. CoRR abs/1704.03062 (2017) - [i25]János Pach, Natan Rubin, Gábor Tardos:
A Crossing Lemma for Jordan Curves. CoRR abs/1708.02077 (2017) - [i24]Andrey Kupavskii, János Pach, Gábor Tardos:
Tilings with noncongruent triangles. CoRR abs/1711.04504 (2017) - [i23]Andrey Kupavskii, János Pach, Gábor Tardos:
Tilings of the plane with unit area triangles of bounded diameter. CoRR abs/1712.03118 (2017) - 2016
- [j65]János Pach, Natan Rubin, Gábor Tardos:
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves†. Combinatorics, Probability & Computing 25(6): 941-958 (2016) - [j64]Heidi Gebauer, Tibor Szabó, Gábor Tardos:
The Local Lemma Is Asymptotically Tight for SAT. J. ACM 63(5): 43:1-43:32 (2016) - [j63]Zsolt Lángi, Márton Naszódi, János Pach, Gábor Tardos, Géza Tóth:
Separation with restricted families of sets. J. Comb. Theory, Ser. A 144: 292-305 (2016) - [j62]Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao:
Improved bounds for the randomized decision tree Complexity of recursive majority. Random Struct. Algorithms 48(3): 612-638 (2016) - [c39]
- 2015
- [j61]János Pach, Gábor Tardos:
Cross-Intersecting Families of Vectors. Graphs and Combinatorics 31(2): 477-495 (2015) - [j60]László Csirmaz, Péter Ligeti, Gábor Tardos:
Erdős-Pyber Theorem for Hypergraphs and Secret Sharing. Graphs and Combinatorics 31(5): 1335-1346 (2015) - [j59]Gábor Simonyi, Gábor Tardos, Ambrus Zsbán:
Relations between the Local Chromatic Number and Its Directed Version. Journal of Graph Theory 79(4): 318-330 (2015) - [c38]János Pach, Natan Rubin, Gábor Tardos:
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves. SODA 2015: 1506-1516 - [i22]János Pach, Natan Rubin, Gábor Tardos:
Beyond the Richter-Thomassen Conjecture. CoRR abs/1504.08250 (2015) - 2014
- [j58]Gabriel Nivasch, János Pach, Gábor Tardos:
The visible perimeter of an arrangement of disks. Comput. Geom. 47(1): 42-51 (2014) - [j57]Roman Glebov, Tibor Szabó, Gábor Tardos:
Conflict-Free Colouring of Graphs. Combinatorics, Probability & Computing 23(3): 434-448 (2014) - [j56]Jessica Enright, Lorna Stewart, Gábor Tardos:
On List Coloring and List Homomorphism of Permutation and Interval Graphs. SIAM J. Discrete Math. 28(4): 1675-1685 (2014) - [i21]
- [i20]János Pach, Natan Rubin, Gábor Tardos:
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves. CoRR abs/1412.6676 (2014) - 2013
- [j55]Bojan Mohar, Gábor Simonyi, Gábor Tardos:
Local chromatic number of quadrangulations of surfaces. Combinatorica 33(4): 467-495 (2013) - [j54]
- [j53]Péter L. Erdös, Claude Tardif, Gábor Tardos:
On Infinite-finite Duality Pairs of Directed Graphs. Order 30(3): 807-819 (2013) - [j52]Péter L. Erdös, Claude Tardif, Gábor Tardos:
Caterpillar Dualities and Regular Languages. SIAM J. Discrete Math. 27(3): 1287-1294 (2013) - [j51]László Csirmaz, Gábor Tardos:
Optimal Information Rate of Secret Sharing Schemes on Trees. IEEE Trans. Information Theory 59(4): 2527-2530 (2013) - [c37]Mert Saglam, Gábor Tardos:
On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems. FOCS 2013: 678-687 - [c36]
- [i19]László Csirmaz, Gábor Tardos:
Optimal information rate of secret sharing schemes on trees. CoRR abs/1302.4609 (2013) - [i18]Mert Saglam, Gábor Tardos:
On the communication complexity of sparse set disjointness and exists-equal problems. CoRR abs/1304.1217 (2013) - [i17]Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao:
Improved bounds for the randomized decision tree complexity of recursive majority. CoRR abs/1309.7565 (2013) - [i16]László Csirmaz, Péter Ligeti, Gábor Tardos:
Erdős-Pyber theorem for hypergraphs and secret sharing. CoRR abs/1311.5027 (2013) - 2012
- [j50]János Pach, Gábor Tardos, József Solymosi:
Remarks on a Ramsey theory for trees. Combinatorica 32(4): 473-482 (2012) - [j49]
- [j48]János Pach, Gábor Tardos:
Piercing quasi-rectangles - On a problem of Danzer and Rogers. J. Comb. Theory, Ser. A 119(7): 1391-1397 (2012) - [c35]Gabriel Nivasch, János Pach, Gábor Tardos:
The Visible Perimeter of an Arrangement of Disks. Graph Drawing 2012: 364-375 - [i15]Péter L. Erdös, Claude Tardif, Gábor Tardos:
On infinite-finite duality pairs of directed graphs. CoRR abs/1203.1257 (2012) - [i14]Péter L. Erdös, Claude Tardif, Gábor Tardos:
Caterpillar dualities and regular languages. CoRR abs/1203.1347 (2012) - [i13]Gabriel Nivasch, János Pach, Gábor Tardos:
The visible perimeter of an arrangement of disks. CoRR abs/1206.1422 (2012) - [i12]Jessica Enright, Lorna Stewart, Gábor Tardos:
On List Colouring and List Homomorphism of Permutation and Interval Graphs. CoRR abs/1206.5106 (2012) - [i11]Péter L. Erdös, Dömötör Pálvölgyi, Claude Tardif, Gábor Tardos:
On infinite-finite tree-duality pairs of relational structures. CoRR abs/1207.4402 (2012) - 2011
- [j47]Gábor Simonyi, Gábor Tardos:
On directed local chromatic number, shift graphs, and Borsuk-like graphs. Journal of Graph Theory 66(1): 65-82 (2011) - [c34]János Pach, Gábor Tardos:
Tight lower bounds for the size of epsilon-nets. Symposium on Computational Geometry 2011: 458-463 - [c33]Hossein Jowhari, Mert Saglam, Gábor Tardos:
Tight bounds for Lp samplers, finding duplicates in streams, and related problems. PODS 2011: 49-58 - [c32]
- [c31]János Pach, Gábor Tardos:
Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers. WADS 2011: 654 - [i10]László Csirmaz, Gábor Tardos:
On-line secret sharing. IACR Cryptology ePrint Archive 2011: 174 (2011) - 2010
- [j46]Robin A. Moser, Gábor Tardos:
A constructive proof of the general lovász local lemma. J. ACM 57(2): 11:1-11:15 (2010) - [j45]János Pach, Gábor Tardos:
Coloring axis-parallel rectangles. J. Comb. Theory, Ser. A 117(6): 776-782 (2010) - [j44]János Pach, József Solymosi, Gábor Tardos:
Crossing numbers of imbalanced graphs. Journal of Graph Theory 64(1): 12-21 (2010) - [c30]Gábor Tardos:
Capacity of Collusion Secure Fingerprinting - A Tradeoff between Rate and Efficiency - (Extended Abstract of Invited Talk). Information Hiding 2010: 81-85 - [i9]Heidi Gebauer, Tibor Szabó, Gábor Tardos:
The Local Lemma Is Tight for SAT. CoRR abs/1006.0744 (2010) - [i8]János Pach, Gábor Tardos:
Tight lower bounds for the size of epsilon-nets. CoRR abs/1012.1240 (2010) - [i7]Hossein Jowhari, Mert Saglam, Gábor Tardos:
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems. CoRR abs/1012.4889 (2010)
2000 – 2009
- 2009
- [j43]János Pach, Gábor Tardos:
Conflict-Free Colourings of Graphs and Hypergraphs. Combinatorics, Probability & Computing 18(5): 819-834 (2009) - [j42]Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos:
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Random Struct. Algorithms 34(1): 11-23 (2009) - [c29]Ehsan Amiri, Gábor Tardos:
High rate fingerprinting codes and the fingerprinting capacity. SODA 2009: 336-345 - [i6]Robin A. Moser, Gábor Tardos:
A constructive proof of the general Lovasz Local Lemma. CoRR abs/0903.0544 (2009) - [i5]László Csirmaz, Gábor Tardos:
Secret sharing on trees: problem solved. IACR Cryptology ePrint Archive 2009: 71 (2009) - 2008
- [j41]Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos:
Graph Colouring with No Large Monochromatic Components. Combinatorics, Probability & Computing 17(4): 577-589 (2008) - [j40]
- [c28]Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos:
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. SODA 2008: 94-101 - 2007
- [j39]Gábor Tardos, Géza Tóth:
Multiple Coverings of the Plane with Triangles. Discrete & Computational Geometry 38(2): 443-450 (2007) - [j38]Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb. 28(1): 134-144 (2007) - [j37]Joshua N. Cooper, Benjamin Doerr, Joel H. Spencer, Gábor Tardos:
Deterministic random walks on the integers. Eur. J. Comb. 28(8): 2072-2090 (2007) - [j36]Gábor Simonyi, Gábor Tardos:
Colorful subgraphs in Kneser-like graphs. Eur. J. Comb. 28(8): 2188-2200 (2007) - [j35]Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos:
Graph coloring with no large monochromatic components. Electronic Notes in Discrete Mathematics 29: 115-122 (2007) - [j34]Eyal Ackerman, Gábor Tardos:
On the maximum number of edges in quasi-planar graphs. J. Comb. Theory, Ser. A 114(3): 563-571 (2007) - [j33]Gábor Tardos, Géza Tóth:
Crossing Stars in Topological Graphs. SIAM J. Discrete Math. 21(3): 737-749 (2007) - [c27]József Solymosi, Gábor Tardos:
On the number of k-rich transformations. Symposium on Computational Geometry 2007: 227-231 - [c26]
- 2006
- [j32]Tibor Szabó, Gábor Tardos:
Extremal Problems For Transversals In Graphs With Bounded Degree. Combinatorica 26(3): 333-351 (2006) - [j31]Gábor Simonyi, Gábor Tardos:
Local Chromatic Number, KY Fan's Theorem, And Circular Colorings. Combinatorica 26(5): 587-626 (2006) - [j30]Itai Benjamini, Gady Kozma, László Lovász, D. A. N. Romik, Gábor Tardos:
Waiting for a Bat to Fly By (in Polynomial Time). Combinatorics, Probability & Computing 15(5): 673-683 (2006) - [j29]János Pach, Rados Radoicic, Gábor Tardos, Géza Tóth:
Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs. Discrete & Computational Geometry 36(4): 527-552 (2006) - [j28]Adam Marcus, Gábor Tardos:
Intersection reverse sequences and geometric applications. J. Comb. Theory, Ser. A 113(4): 675-691 (2006) - [c25]Joshua N. Cooper, Benjamin Doerr, Joel Spencer, Gábor Tardos:
Deterministic Random Walks. ANALCO 2006: 185-197 - 2005
- [j27]Gábor Tardos:
On 0-1 matrices and small excluded submatrices. J. Comb. Theory, Ser. A 111(2): 266-288 (2005) - [c24]
- [c23]János Pach, Gábor Tardos:
Forbidden patterns and unit distances. Symposium on Computational Geometry 2005: 1-9 - [i4]Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts. Electronic Colloquium on Computational Complexity (ECCC)(095) (2005) - 2004
- [j26]Boris Aronov, János Pach, Micha Sharir, Gábor Tardos:
Distinct Distances in Three and Higher Dimensions. Combinatorics, Probability & Computing 13(3): 283-293 (2004) - [j25]János Pach, Rom Pinchasi, Gábor Tardos, Géza Tóth:
Geometric graphs with no self-intersecting path of length three. Eur. J. Comb. 25(6): 793-811 (2004) - [j24]Adam Marcus, Gábor Tardos:
Excluded permutation matrices and the Stanley-Wilf conjecture. J. Comb. Theory, Ser. A 107(1): 153-160 (2004) - [c22]János Pach, Rados Radoicic, Gábor Tardos, Géza Tóth:
Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract]. Symposium on Computational Geometry 2004: 68-75 - [c21]Adam Marcus, Gábor Tardos:
Intersection Reverse Sequences and Geometric Applications. Graph Drawing 2004: 349-359 - [c20]
- 2003
- [j23]Penny E. Haxell, Tibor Szabó, Gábor Tardos:
Bounded size components--partitions and transversals. J. Comb. Theory, Ser. B 88(2): 281-297 (2003) - [j22]Vince Grolmusz, Gábor Tardos:
A Note on Non-Deterministic Communication Complexity with Few Witnesses. Theory Comput. Syst. 36(4): 387-391 (2003) - [c19]
- [c18]Boris Aronov, János Pach, Micha Sharir, Gábor Tardos:
Distinct distances in three and higher dimensions. STOC 2003: 541-546 - 2002
- [j21]
- [j20]János Pach, Gábor Tardos:
Untangling a Polygon. Discrete & Computational Geometry 28(4): 585-592 (2002) - [j19]József Solymosi, Gábor Tardos, Csaba D. Tóth:
The k Most Frequent Distances in the Plane. Discrete & Computational Geometry 28(4): 639-648 (2002) - [j18]János Pach, Gábor Tardos:
Isosceles Triangles Determined by a Planar Point Set. Graphs and Combinatorics 18(4): 769-779 (2002) - [j17]Imre Bárány, Gergely Harcos, János Pach, Gábor Tardos:
Covering lattice points by subspaces. Periodica Mathematica Hungarica 43(1-2): 93-103 (2002) - [j16]János Pach, Gábor Tardos:
On the Boundary Complexity of the Union of Fat Triangles. SIAM J. Comput. 31(6): 1745-1760 (2002) - [c17]János Pach, Rom Pinchasi, Gábor Tardos, Géza Tóth:
Geometric Graphs with No Self-intersecting Path of Length Three. Graph Drawing 2002: 295-311 - 2001
- [j15]Tibor Szabó, Gábor Tardos:
A Multidimensional Generalization Of The Erdös-Szekeres Lemma On Monotone Subsequences. Combinatorics, Probability & Computing 10(6): 557-565 (2001) - [j14]Micha Sharir, Shakhar Smorodinsky, Gábor Tardos:
An Improved Bound for k-Sets in Three Dimensions. Discrete & Computational Geometry 26(2): 195-204 (2001) - [j13]János Pach, Gábor Tardos:
Separating convex sets by straight lines. Discrete Mathematics 241(1-3): 427-433 (2001) - [c16]
- 2000
- [j12]Joel Spencer, Gábor Tardos:
Ups and Downs of First Order Sentences on Random Graphs. Combinatorica 20(2): 263-280 (2000) - [j11]
- [j10]Vince Grolmusz, Gábor Tardos:
Lower Bounds for (MODp-MODm) Circuits. SIAM J. Comput. 29(4): 1209-1222 (2000) - [c15]Micha Sharir, Shakhar Smorodinsky, Gábor Tardos:
An improved bound for k-sets in three dimensions. Symposium on Computational Geometry 2000: 43-49 - [c14]
- [c13]János Pach, Gábor Tardos:
On the boundary complexity of the union of fat triangles. FOCS 2000: 423-431 - [i3]Micha Sharir, Shakhar Smorodinsky, Gábor Tardos:
An Improved Bound for k-Sets in Three Dimensions. EuroCG 2000: 132-135
1990 – 1999
- 1999
- [j9]Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos:
Linear Hash Functions. J. ACM 46(5): 667-683 (1999) - [j8]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. J. Comput. Syst. Sci. 59(2): 346-372 (1999) - 1998
- [j7]Gábor Tardos, David A. Mix Barrington:
A Lower Bound on the Mod 6 Degree of the Or Function. Computational Complexity 7(2): 99-108 (1998) - [c12]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. IEEE Conference on Computational Complexity 1998: 58-67 - [c11]
- [i2]Vince Grolmusz, Gábor Tardos:
Lower Bounds for (MOD p -- MOD m) Circuits. Electronic Colloquium on Computational Complexity (ECCC) 5(36) (1998) - 1997
- [c10]Gábor Tardos, Uri Zwick:
The Communication Complexity of the Universal Relation. IEEE Conference on Computational Complexity 1997: 247-259 - [c9]Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos:
Is Linear Hashing Good? STOC 1997: 465-474 - [c8]Joe Kilian, Erez Petrank, Gábor Tardos:
Probabilistically Checkable Proofs with Zero Knowledge. STOC 1997: 496-505 - [i1]Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. Electronic Colloquium on Computational Complexity (ECCC) 4(54) (1997) - 1996
- [j6]Gyula Károlyi, Gábor Tardos:
On Point Covers of Multiple Intervals and Axis-Parallel Rectangles. Combinatorica 16(2): 213-222 (1996) - [j5]Gábor Tardos:
Multi-prover Encoding Schemes and Three-prover Proof Systems. J. Comput. Syst. Sci. 53(2): 251-260 (1996) - [c7]
- 1995
- [j4]Gábor Tardos:
Transversals of 2-Intervals, a Topological Approach. Combinatorica 15(1): 123-134 (1995) - [c6]Gábor Tardos, David A. Mix Barrington:
A Lower Bound on the Mod 6 Degree of the OR Function. ISTCS 1995: 52-56 - 1994
- [j3]Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson:
On the Power of Randomization in On-Line Algorithms. Algorithmica 11(1): 2-14 (1994) - [c5]Gábor Tardos:
Multi-Prover Encoding Schemes and Three-Prover Proof Systems. Structure in Complexity Theory Conference 1994: 308-317 - 1990
- [c4]
- [c3]Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson:
On the Power of Randomization in Online Algorithms (Extended Abstract). STOC 1990: 379-386
1980 – 1989
- 1989
- [j2]Gábor Tardos:
Query complexity, or why is it difficult to seperate NP A cap co NPA from PA by random oracles A?. Combinatorica 9(4): 385-392 (1989) - [c2]