László Babai's students

Mario Szegedy

coadvised with Janos Simon

(Posted December 2019, thirty years after Mario's thesis defense)
Neither Mario, nor I were able to find an original hard copy of Mario's dissertation. However, two nearly complete and almost identical versions have been found.

Mario Szegedy:

Significant portions of this work have not otherwise been published. An example is Theorem 2.4.7 which states that a polynomial that agrees with the MAJORITY function on a $1/2+\epsilon$ fraction of the inputs has degree $\Omega(\sqrt{n})$. This results appears in a 1993 paper by Smolensky; but Szegedy defended his thesis in 1989.

Return to László Babai's home page