View source for Fenwick tree

{{ Infobox scientist
| name              = Gábor Tardos
| image             = Gábor Tardos.jpg
| image_size        = 
| caption           = 
| birth_date        = {{birth date and age|1964|07|11|df=y}}
| birth_place       = [[Budapest]]
| death_date        = 
| death_place       = 
| nationality       = Hungarian
| fields            = [[Mathematics]]
| workplaces        = [[Simon Fraser University]]
| alma_mater        = [[Hungarian Academy of Sciences]]
| doctoral_advisor  = [[László Babai]]
| doctoral_students = 
| known_for         = 
| awards            = [[Paul Erdős Prize|Erdős Prize]] (2000)<br>[[EMS Prize]] (1992)
}}
'''Gábor Tardos''' (born 11 July 1964) is a [[Hungarian people|Hungarian]][[ mathematician]], 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]].<ref>[http://blog.computationalcomplexity.org/2009/02/baseball-families-and-math-families.html Baseball Families and Math Families], William Gasarch, February 12, 2009.</ref>

==Mathematical results==
Tardos started with a result in [[universal algebra]]: he exhibited a maximal [[clone (algebra)|clone]] of monotone operations which is not finitely  generated. He obtained partial results concerning the [[Hanna Neumann conjecture]]. With his student, [[Adam Marcus (mathematician)|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 <math>\mathcal{H}</math> is a finite set system consisting of the unions of intervals on two disjoint lines, then <math>\tau(\mathcal{H})\leq 2\nu(\mathcal{H})</math> holds, where <math>\tau(\mathcal{H})</math> is the least number of points covering all elements of <math>\mathcal{H}</math> and <math>\nu(\mathcal{H})</math> is the size of the largest disjoint subsystem of <math>\mathcal{H}</math>. 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 [[Paul Erdős Prize|Erdős Prize]] from the [[Hungarian Academy of Sciences]] in 2000. He received a Lendület Grant from the Hungarian Academy of Sciences (2009).<ref>[http://www.mta.hu/index.php?id=634&no_cache=1&backPid=390&tt_news=11051&cHash=10423ab5d6 Lendületben az MTA]</ref> specifically devised to keep outstanding researchers in Hungary.

==Selected publications==
*{{Citation |first=G. |last=Tardos |authormask=3 |title=Optimal probabilistic fingerprint codes |journal=[[Journal of the ACM]] |volume=55 |year=2008 | doi =10.1145/780542.780561 }}.
*{{Citation |first=G. |last=Tardos |authormask=3 |title=Transversals of 2-intervals, a topological approach |journal=[[Combinatorica]] |volume=15 |year=1995 |pages=123–134 }}.
*{{Citation |first=G. |last=Tardos |authormask=3 |first2=S. |last2=Ben-David |first3=A. |last3=Borodin |authorlink4=Richard Karp |first4=R. |last4=Karp |authorlink5=Avi Wigderson |first5=A. |last5=Wigderson |title=On the power of randomization in on-line algorithms |journal=[[Algorithmica]] |volume=11 |year=1994 |pages=2–14 }}.
*{{Citation |first=G. |last=Tardos |authormask=3 |title=A maximal clone of monotone operations which is not finitely  generated |journal=[[Order (journal)|Order]] |volume=3 |year=1986 |pages=211–218 }}.

==References==
{{Reflist}}

==External links==
*{{MathGenealogy |id=99198}}

{{Authority control|VIAF=2784220}}
{{Persondata <!-- Metadata: see [[Wikipedia:Persondata]]. -->
| NAME              = Tardos, Gabor
| ALTERNATIVE NAMES =
| SHORT DESCRIPTION = Hungarian mathematician
| DATE OF BIRTH     = 11 July 1964
| PLACE OF BIRTH    = [[Budapest]]
| DATE OF DEATH     =
| PLACE OF DEATH    =
}}
{{DEFAULTSORT:Tardos, Gabor}}
[[Category:1964 births]]
[[Category:Living people]]
[[Category:Hungarian mathematicians]]
[[Category:Hungarian computer scientists]]
[[Category:Combinatorialists]]
[[Category:20th-century mathematicians]]
[[Category:21st-century mathematicians]]
[[Category:Simon Fraser University faculty]]
[[Category:Canada Research Chairs]]
[[Category:International Mathematical Olympiad participants]]