Nisha Rathode (Editor)

Gábor Tardos

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Nationality
  
Hungarian

Fields
  
Mathematics


Role
  
Mathematician

Name
  
Gabor Tardos

Awards
  
Alfred Renyi Prize

Gabor Tardos wwwrenyihutardostardoskjpg

Born
  
11 July 1964 (age 59) Budapest (
1964-07-11
)

Institutions
  
Alfred Renyi Mathematical Institute

Doctoral advisor
  
Laszlo Babai and Peter Pal Palfy

Institution
  
Alfred Renyi Institute of Mathematics

Notable awards
  
Paul Erdos Prize, Alfred Renyi Prize, European Mathematical Society

Similar People
  
Laszlo Babai, Charles Rackoff, Silvio Micali, Shafi Goldwasser

Alma mater
  
Eotvos Lorand University

Extremal theory of ordered graphs – Gábor Tardos – ICM2018


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

Contents

Mathematical results

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 H is a finite set system consisting of the unions of intervals on two disjoint lines, then τ ( H ) ≤ 2 ν ( H ) holds, where τ ( H ) is the least number of points covering all elements of H and ν ( H ) is the size of the largest disjoint subsystem of H . Tardos worked out a method for optimal probabilistic fingerprint codes. Although the mathematical content is hard, the algorithm is easy to implement.

Awards

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). specifically devised to keep outstanding researchers in Hungary.

Selected publications

  • ——— (2008), "Optimal probabilistic fingerprint codes", Journal of the ACM, 55, doi:10.1145/780542.780561 .
  • ——— (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: 211–218, doi:10.1007/bf00400284 .

    • References

    Gábor Tardos Wikipedia
    (Text) CC BY-SA