# 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.