(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
Ph. D. Thesis, Dept. Computer Science, University of Chicago,
December 1989.
Scanned copy, almost final version (PDF, 6.7M)
This version was produced directly from the original .tex files
and is therefore a much smaller file and an easier-to-read
document. While it does not have the cover page,
otherwise it is almost identical
with the scanned document.