Gábor Tardos

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Gábor Tardos
Gábor Tardos.jpg
Born (1964-07-11) 11 July 1964 (age 55)
Alma materEötvös Loránd University
AwardsErdős Prize (2000)
Alfréd Rényi Prize (1999)
EMS Prize (1992)
Scientific career
InstitutionsAlfréd Rényi Mathematical Institute, Simon Fraser University
Doctoral advisorLászló Babai and Péter Pál Pálfy

Gábor Tardos (born 11 July 1964) is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is the younger brother of Éva Tardos.[1]

Mathematical results[edit]

Tardos started with a result in universal algebra: he exhibited a maximal clone of monotone operations which is not finitely generated. He obtained partial results concerning the Hanna Neumann conjecture. With his student, Adam Marcus, he proved a combinatorial conjecture of Zoltán Füredi and Péter Hajnal which was known to imply the Stanley–Wilf conjecture. With topological methods he proved that if is a finite set system consisting of the unions of intervals on two disjoint lines, then holds, where is the least number of points covering all elements of and is the size of the largest disjoint subsystem of . Tardos worked out a method for optimal probabilistic fingerprint codes. Although the mathematical content is hard, the algorithm is easy to implement.


He received the European Mathematical Society prize for young researchers at the European Congress of Mathematics in 1992 and the Erdős Prize from the Hungarian Academy of Sciences in 2000. He received a Lendület Grant from the Hungarian Academy of Sciences (2009).[2] specifically devised to keep outstanding researchers in Hungary.

Selected publications[edit]

  • ——— (2008), "Optimal probabilistic fingerprint codes", Journal of the ACM, 55: 116, CiteSeerX, doi:10.1145/780542.780561, ISBN 978-1581136746.
  • ——— (1995), "Transversals of 2-intervals, a topological approach", Combinatorica, 15: 123–134, doi:10.1007/bf01294464.
  • ———; Ben-David, S.; Borodin, A.; Karp, R.; Wigderson, A. (1994), "On the power of randomization in on-line algorithms", Algorithmica, 11: 2–14, doi:10.1007/bf01294260.
  • ——— (1986), "A maximal clone of monotone operations which is not finitely generated", Order, 3 (3): 211–218, doi:10.1007/bf00400284.


External links[edit]