Publications of Gábor Tardos


  You can download most of these papers in postscript or pdf form. Ilost the electronic versions of my first 11 papers, but feel free to ask for paper copies.
 
 
 
    1. G. Tardos, A maximal clone of monotone operations which is not finitely generated, Order 3 (1986) (3), 211–218.

      2.  
    2. M. Szegedy, G. Tardos, On the decomposition of infinite series into monotone decreasing parts, Studia Sci. Math. Hung. 23 (1988), 81–83.

      3.  
    3. G. Tardos, Polynomial bound for a chip firing game on graphs, SIAM Journal on Discrete Mathematics 1 (1988) (3), 397–398.

      4.  
    4. G. Tardos, Finitely generated pseudosimple algebras, Algebra Universalis 26 (1989) (2), 127–136.

      5.  
    5. U. Feige, A. Fiat, A. Shamir, I. Shimshoni, G. Tardos, Planning and learning in permutation groups, in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, (FOCS 1989), 274–287.

      6.  
    6. R. Impagliazzo, G. Tardos, Decision versus search in super-polynomial time, in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, (FOCS 1989), 222–227.

      7.  
    7. G. Tardos, Query complexity, or why is it difficult to separate NPA meet coNPA from PA by random oracles A?, Combinatorica, 9 (1989) (4), 385–392.

      8.  
    8. L. Fehér, M. Laczkovich, G. Tardos, Croftian sequences, Acta Mathematica Hungarica  56 (1990) (3-4), 353–359.

      9.  
    9. P. Berman, H. Karloff, G. Tardos, A competitive 3-server algorithm, in: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 1990), 280–290.

      10.  
    10. G. Tardos, On the intersection of subgroups of a free group, Inventiones Mathematicae,  108 (1992) (1), 29–36.

      11.  
    11. S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson, On the power of randomization in on-line algorithms, Algorithmica,  11 (1994) (1), 2–14.
      Preliminary version appeared in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, (STOC 1990), 379–386.

      12.  
    12. G. Tardos, Transversals of 2-intervals, a topological approach, Combinatorica, 15 (1995) (1) 123–134.

      13.  
    13. Gy. Károlyi, G. Tardos, On point covers of multiple intervals and axis parallel rectangles, Combinatorica, 16 (1996) (2) 213–222.

      14.  
    14. G. Tardos, Toward the Hanna Neumann conjecture using Dicks' method, Inventiones Mathematicae, 123 (1996) (1) 95–104.

      15.  
    15. G. Tardos, Multi-prover encoding scemes and three-prover proof systems, Journal of Computer and System Sciences,  53 (1996) (2) 251–260.
      Preliminary version appeared in Proceedings of the 9th Annual Structure in Complexity Theory Conference, (STRUCTURES 1994), 308–317.

      16.  
    16. M. Ruszinkó, G. Tardos, On a search problem in multidimensional grids, J. of  Statistical Planning and Inference, 59 (1997) (1), 101–109.

      17.  
    17. Gy. Károlyi, J. Pach, G. Tardos, G. Tóth, An algorithm for finding many disjoint monochromatic edges in a complete 2-colored geometric graph, in: Intuitive Geometry (I. Bárány, K. Böröczky, eds.), Bolyai Society Mathematical Studies, Budapest, 1997, 367–372.

      18.  
    18. J. Kilian, E. Petrank, G. Tardos, Probabilistically checkable proofs with zero knowledge, in: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, (STOC 1997), 496–505.

      19.  
    19. G. Tardos, U. Zwick, The communication complexity of the universal relation, in: Proceedings of the 12th Annual IEEE Conference on Computational Complexity, (CCC 1997), 247–259.

      20.  
    20. G. Tardos, Trasversals of d-intervals — comparing three approaches, in: Proceedings of the Second European Congress of Mathematics, Progress in Mathematics, Vol. 169, Birkhäuser, 1998, 234–243.

      21.  
    21. G. Tardos, D. A. M. Barrington, A lower bound on the mod 6 degree of the OR function,  Comput. Complex. 7 (1998) (2), 99–108.
      Preliminary version appeared in Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems, (ISTC 1995), 52–56.

      22.  
    22. N. Alon, M. Dietzfelbinger, P. B. Miltersen, E. Petrank, G. Tardos, Linear hash functions,   Journal of the ACM 46 (1999) (5), 667–683.
      Preliminary version appeared as Is linear hashing good?, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, (STOC 1997), 465–474.

      23.  
    23. R. Raz, G. Tardos, O. Verbitsky, N. Vereshchagin, Arthur-Merlin Games in Boolean Decision Trees, Journal of Computer and System Sciences 59 (1999) (2) 346–372.
      Preliminary version appeared in Proceedings of the 13th Annual IEEE Conference on Computational Complexity, (CCC 1998), 58–67.

      24.  
    24. G. Elek, G. Tardos, On roughly transitive amenable graphs and harmonic Dirichlet functions,  Proceedings of the AMS 128 (2000) (8), 2479–2485. Also available at arXiv:math.GT/9806129.

      25.  
    25. V. Grolmusz, G. Tardos, Lower bounds for (MOD p - MOD m) circuits, SIAM Journal on Computing 29 (2000) (4), 1209–1222.
      Preliminary version appeared in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, (FOCS 1998), 279–288.

      26.  
    26. J. Spencer, G. Tardos, Ups and downs of first order sentences on random graphs,  Combinatorica 20 (2000) (2), 263–280.

      27.  
    27. J. Pach, G. Tardos, Cutting glass, Discrete and Computational Geometry, 24 (2000) (2-3), 481–495.
      Preliminary version appeared in Proceedings of the 16th Annual Symposium on Computational Geometry, (SoCG 2000), 360–369.

      28.  
    28. J. Pach, G. Tardos, Separating convex sets by straight lines,  Discrete Mathematics 241 (2001) (1-3), 427–433.

      29.  
    29. M. Sharir, S. Smorodinsky, G. Tardos, An improved bound for k-sets in three dimensions,  Discrete and Computation Geometry 26 (2001) (2), 195–204.
      Preliminary version appeared in Proceedings of the 16th Annual Symposium on Computational Geometry (SoCG 2000), 43–49.

      30.  
    30. T. Szabó, G. Tardos, A multidimensional generalization of the Erdős-Szekeres lemma on monotone subsequences, Combinatorics, Probability and Computing, 10 (2001) (6), 557–565.

      31.  
    31. I. Bárány, G. Harcos, J. Pach, G. Tardos, Covering lattice points by subspaces,  Periodica Mathematica Hungarica 43 (2002) (1-2), 93–103. Also available at arXiv:math.NT/0102030.

      32.  
    32. E. Petrank, G. Tardos, On the knowledge complexity of NP, Combinatorica 22 (2002) (1), 83–121.
      Preliminary version appeared in Proceedings of the 37th Annual Symposium on Foundations of Computer Science, (FOCS 1996), 494–503.

      33.  
    33. J. Pach, G. Tardos, On the boundary complexity of the union of fat triangles, SIAM Journal on Computing, 31 (2002) (6), 1745–1760.
      Preliminary version appeared in Proceedings of the 41st Annual Symposium on Foundations of Computer Science, (FOCS 2000), 423–431.

      34.  
    34. J. Pach, G. Tardos, Untangling a polygon, Discrete and Computational Geometry, 28 (2002) (4), 585–592.
      Preliminary version appeared in Graph Drawing 2001, Lecture Notes in Computer Science 2265, Springer-Verlag, Berlin, Heidelberg, 2002, 154–161.

      35.  
    35. J. Pach, G. Tardos, Isosceles triangles determined by a planar point set, Graphs and Combinatorics, 18 (2002) (4), 769–779.

      36.  
    36. J. Solymosi, G. Tardos, Cs. D. Tóth, The k most frequent distances in the plane, Discrete and Computational Geometry, 28 (2002) (4), 639–648.

      37.  
    37. K. Böröczky, Jr., G. Tardos, The longest segment in the complement of a packing, Mathematika, 49 (2002) (97-98), 45–49.

      38.  
    38. G. Tardos, On distinct sums and distinct distances, Advances in Mathematics 180 (2003) (1), 275–289.

      39.  
    39. P. Haxell, T. Szabó, G. Tardos, Bounded size components - partitions and transversals, Journal of Combinatorial Theory Ser. B, 88 (2003) (2), 281–297.

      40.  
    40. V. Grolmusz, G. Tardos,  A note on non-deterministic communication complexity with few witnesses, Theory of Computing Systems, 36 (2003) (4), 387–391.

      41.  
    41. B. Aronov, J. Pach, M. Sharir, G. Tardos, Distinct distances in three and higher dimensions, Combinatorics, Probability and Computing 13 (2004) (3), 283–293.
      Preliminary version appeared in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, (STOC 2003), 541–546.

      42.  
    42. A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, Journal of Combinatorial Theory Ser. A, 107 (2004) (1), 153–160.

      43.  
    43. N. H. Katz, G. Tardos, A new entropy inequality for the Erdős distance problem, in: Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics 342, AMS, Providence, RI, 2004, 119–126.

      44.  
    44. J. Pach, R. Pinchasi, G. Tardos, G. Tóth, Geometric graphs with no self-intersecting path of length three, European Journal of Combinatorics 25 (2004) (6), 793–811.
      Preliminary version appeared in Graph Drawing 2002 (M. T. Goodrich, S. G. Kobourov, eds.), Lecture Notes in Computer Science 2528, Springer-Verlag, Berlin, Heidelberg, 2002, 295–311.

      45.  
    45. G. Tardos, On 0-1 matrices and small excluded submatrices, Journal of Combinatorial Theory Ser. A 111 (2005) (2), 266–288.

      46.  
    46. G. Simonyi, G. Tardos, Local chromatic number and topological properties of graphs, in: Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05), DMTCS Proceedings, 2005, 375–378.

      47.  
    47. T. Szabó, G. Tardos, Extremal problems for transversals in graphs with bounded degree, Combinatorica 26 (2006) (3), 333–351.

      48.  
    48. J. Pach, R. Radoičić, G. Tardos, G. Tóth, Improving the crossing lemma by finding more crossings in sparse graphs, Discrete and Computational Geometry 36 (2006) (4), 527–552.
      Preliminary version appeared in Proceedings of the 20th Annual Symposium on Computational Geometry, (SoCG 2004), 68–75.

      49.  
    49. A. Marcus, G. Tardos, Intersection reverse sequences and geometric applications, Journal of Combinatorial Theory Ser. A 113 (2006) (4), 675–691.
      Preliminary version appeared in Graph Drawing 2004 (J. Pach, ed.), Lecture Notes in Computer Science 3383, Springer-Verlag, Berlin, Heidelberg, 2005, 349–359.

      50.  
    50. I. Benjamini, G. Kozma, L. Lovász, D. Romik, G. Tardos, Waiting for a bat to fly by (in polynomial time), Combinatorics, Probability and Computing 15 (2006) (5), 673–683. Also available at arXiv:math.PR/0310435

      51.  
    51. G. Simonyi, G. Tardos, Local chromatic number, Ky Fan's theorem, and circular colorings, Combinatorica 26 (2006) (5), 587–626. Also available at arXiv:math.CO/0407075.

      52.  
    52. J. Pach, G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel Journal of Mathematics 155 (2006), 359–380.
      Preliminary version appeared as Forbidden patterns and unit distances, in Proceedings of the 21th Annual Symposium on Computational Geometry, (SoCG 2005), 1–9.

      53.  
    53. G. Tardos, G. Tóth, Crossing stars in topological graphs, SIAM Journal on Discrete Mathematics 21 (2007) (3), 737–749.
      Preliminary version appeared in Discrete and Computational Geometry, Japanese Conference, Revised Selected Papers, Lecture Notes in Computer Science 3742, Springer Verlag, Berlin, 2005, 184–197.

      54.  
    54. N. Alon, I. Newman, A. Shen, G. Tardos, N. Vereshchagin, Partitioning multidimensional sets in a small number of “uniform” parts, European Journal of Combinatorics 28 (2007) (1), 134–144.

      55.  
    55. J. Cooper, B. Doerr, J. Spencer, G. Tardos, Deterministic random walks on the integers, European Journal of Combinatorics 28 (2007) (8), 2072–2090.
      Preliminary version appeared as Deterministic random walks, in Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO'06), 185–197. Also available at arXiv:math.CO/0602300.

      56.  
    56. J. Solymosi, G. Tardos, On the number of k-rich transformations, in Proceedings of the 23th Annual Symposium on Computational Geometry, (SoCG 2007), ACM, New York, 2007, 227–231.

      57.  
    57. G. Tardos, G. Tóth, Multiple coverings of the plane with triangles, Discrete and Computational Geometry 38 (2007) (2), 443–450.

      58.  
    58. G. Simonyi, G. Tardos, Colorful subgraphs in Kneser-like graphs, European Journal of Combinatorics 28 (2007) (8), 2188–2200. Also available at arXiv:math.CO/0512019.

      59.  
    59. E. Ackerman, G. Tardos, On the maximum number of edges in quasi-planar graphs, Journal of Combinatorial Theory Ser. A 114 (2007) (3), 563–571.

      60.  
    60. G. Tardos, Optimal probabilistic fingerprint codes, Journal of the ACM 55 (2008) (2), Art. 10, 24pp.
      Preliminary version appeared in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, (STOC 2003), 116–125.

      61.  
    61. N. Linial, J. Matoušek, O. Sheffet, G. Tardos, Graph colouring with no large monochromatic components, Combinatorics, Probability and Computing 17 (2008) (4), 577–589.
      Preliminary version appeared in Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'07), Electronic Notes in Discrete Mathematics, 29 (2007), 115–122. Also available at arXiv:math.CO/0703362.

      62.  
    62. J. Pach, G. Tardos, G. Tóth, Indecomposable coverings, Canadian Mathematical Bulletin, 52 (2009) (3), 451–463.
      Preliminary version appeared in Discrete Geometry, Combinatorics and Graph Theory, Lecture Notes in Computer Science 4381, Springer, Berlin, 2007, 135–148.

      63.  
    63. G. Simonyi, G. Tardos, S. Vrećica, Local chromatic number and distinguishing the strength of topological obstructions, Trans. Amer. Math. Soc. 361 (2009) (2), 889–908. Also available at arxiv:math.CO/0502452.

      64.  
    64. X. Chen, J. Pach, M. Szegedy, G. Tardos, Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles, Random Structures and Algorithms 34 (2009) (1), 11–23.
      Preliminary version appeared in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), 94–101.

      65.  
    65. E. Amiri, G. Tardos, High rate fingerprinting codes and the fingerprinting capacity, in: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 336–345.

      66.  
    66. J. Pach, G. Tardos, Conflict-free colorings of graphs and hypergraphs, Combinatorics, Probability and Computing 18 (2009) (5), 819–834.

      67.  
    67. J. Pach, J. Solymosi, G. Tardos, Crossing numbers of imbalanced graphs, Journal of Graph Theory 64 (2010) (1), 12–21.

      68.  
    68. J. Pach, G. Tardos, Coloring axis-parallel rectangles, Journal of Combinatorial Theory, Ser. A 117 (2010) (6), 776–782.
      Preliminary version appeared in Computational Geometry and Graph Theory, KyotoCGGT 2007, Lecture Notes in Computer Science 4535, Springer, Berlin, 2008, 178–185.

      69.  
    69. R. A. Moser, G. Tardos, A constructive proof of the general Lovász local lemma, Journal of the ACM 57 (2010) (2) Art. 11, 15pp. Also available at arXiv:0903.0544.

      70.  
    70. G. Tardos, Capacity of collusion secure fingerprinting—a tradeoff between rate and efficiency, in: Information Hiding 2010, Lecture Notes in Computer Science 6387, Springer, Berlin, 2010, 81–85.

      71.  
    71. G. Simonyi, G. Tardos, On directed local chromatic number, shift graphs, and Borsuk-like graphs, Journal of Graph Theory 66 (2011) (1), 65–82.

      72.  
    72. H. Gebauer, T. Szabó, G. Tardos, The local lemma is tight for SAT, in: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 664–674.

      73.  
    73. H. Johwari, M. Sağlam, G. Tardos, Tight bounds for Lp samplers, finding duplicates, and related problems, in: Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2011), 49–58.

      74.  
    74. L. Csirmaz, G. Tardos, On-line secet sharing, Designs, Codes and Cryptography 63 (2012) (1), 127–147.

      75.  
    75. G. Tardos, Construction of locally plane graphs with many edges, in: Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics series, 29 (J. Pach, ed.), Springer, 2012, 541–562.

      76.  
    76. J. Pach, J. Solymosi, G. Tardos, Remarks on the Ramsey theory for trees, Combinatorica 32 (2012) (4), 473–482.

      77.  
    77. J. Pach, G. Tardos, Piercing quasi-rectangles—On a problem of Danzer and Rogers, Journal of Combinatorial Theory A 119 (2012) (7), 1391–1397.

      78.  
    78. B. Mohar, G. Simonyi, G. Tardos, Local chromatic number of quadrangulations of surfaces, Combinatorica, to appear.

      79.  
    79. J. Pach, G. Tardos, Tight lower bounds for the size of epsilon-nets, Journal of the AMS, to appear.
      Preliminary version appeared in Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG 2011), Paris, France, 2011, 458–463.

      80.  
    80. P. L. Erdős, C. Tardif, G. Tardos, On infinite-finite duality pairs of directed graphs, Order, to appear.

      81.  
    81. L. Csirmaz, G. Tardos, Optimal information rate of secret sharing schemes on trees, IEEE Transactions on Information Theory, to appear.

      82.  
    82. P. L. Erdős, C. Tardif, G. Tardos, Caterpillar dualities and regular languages, SIAM Journal on Discrete Mathematics, to appear.

      83.  
    83. M. Sağlam, G. Tardos, On the communication complexity of sparse set disjointness and exists-equal problems, preprint. Also available at arXiv:1304.1217.
      84.  Back to the home page of Gábor Tardos