Publications of Gábor Tardos


  You can download most of these papers in postscript form. I seem to have lost the electronic versions of the rest, 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), 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), 397-398.

      4.  
    4. G. Tardos, Finitely generated pseudosimple algebras, Algebra Universalis 26 (1989), 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), 385-392.

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

      9.  
    9. P. Berman, H. Karloff, G. Tardos, A competitive three-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), 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), 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, 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's method, Inventiones Mathematicae, 123 (1996) 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 Conference on the Structure in Complexity Theory, (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, 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. Mix Barrington, A lower bound on the mod 6 degree of the OR function,  Comput. Complex. 7 (1998), 99-108.
      Preliminary version appeared in  Proceedings of the 3rd Israeli 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) (9), 667-683.
      Preliminary version appeared 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 12th 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), 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), 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), 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, On a generalization of the Erdős-Szekeres theorem, Combinatorics, Probability and Computing, 10 (2001), 557-565.

      31.  
    31. I. Bárány, G. Harcos, J. Pach, G. Tardos, Covering lattice points by subspaces,  Periodica Mathematica Hungarica 43 (2001) (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), 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. Tóth, The k most frequent distances in the plane, Discrete and Computational Geometry, 28 (2002) (1), 639-648.

      37.  
    37. K. Böröczky, Jr., G. Tardos, The longest segment in the complement of a packing, Mathematika, 49 (2002) , 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), 281-297.

      40.  
    40. V. Grolmusz, G. Tardos,  A note on non-deterministic communication complexity with few witnesses, Theory of Computing Systems, 36 (2003), 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), 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. T. Szabó, G. Tardos, Extremal problems for transversals in graphs with bounded degree, Combinatorica 26 (2006) (3), 333-351.

      46.  
    46. 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.

      47.  
    47. 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.

      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), 527-552.
      Preliminary version appeared in Proceedings of the 20th Annual Symposium on Computational Geometry, (SoCG 2004), 68-75.

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

      50.  
    50. 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.

      51.  
    51. G. Tardos, Construction of locally plane graphs, manuscript (2004).

      52.  
    52. 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

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

      54.  
    54. 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 J. Pach, G. Tardos, Forbidden patterns and unit distances in Proceedings of the 21th Annual Symposium on Computational Geometry, (SoCG 2005), 1-9.

      55.  
    55. 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.

      56.  
    56. J. Cooper, B. Doerr, J. Spencer, G. Tardos, Deterministic random walks on the integers, European Journal of Combinatorics 28 (2007), 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.

      57.  
    57. J. Pach, G. Tardos, G. Tóth, Indecomposable coverings, Canadian Mathematical Bulletin, 52 (2009), 451-463.
      Preliminary version appeared in Discrete geometry, combinatorics and graph theory, 135-148, Lecture Notes in Computer Science 4381, Springer, Berlin, 2007.

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

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

      60.  
    60. 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.

      61.  
    61. G. Simonyi, G. Tardos, S. Vrecica, Local chromatic number and distinguishing the strength of topological obstructions, Trans. Amer. Math. Soc. 361 (2009), 889-908. Also available at arxiv:math.CO/0502452.

      62.  
    62. 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.

      63.  
    63. N. Linial, J. Matousek, O. Sheffet, G. Tardos, Graph colouring with no large monochromatic components, Combinatorics, Probability and Computing 17 (2008) (4), 577-589. Also available at arXiv:math.CO/0703362.

      64.  
    64. J. Pach, J. Solymosi, G. Tardos, Crossing numbers of imbalanced graphs, Journal of Graph Theory, to appear.

      65.  
    65. J. Pach, G. Tardos, Coloring axis parallel rectangles, Journal of Combinatorial Theory, Ser. A, to appear.

      66.  
    66. 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).

      67.  
    67. R. Moser, G. Tardos, A constructive proof of the general Lovász Local Lemma, Journal of the ACM, to appear. Also available at arXiv:0903.0544.

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

      69.  
    69. G. Simonyi, G. Tardos, On directed local chromatic number, shift graphs, and Borshuk-like graphs, Journal of Graph Theory, to appear.
       

       Back to the home page of Gábor Tardos