(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