Skip to main content

Aleksa Stankovic: Razborov-Smolensky Circuit Lower Bound

Time: Fri 2021-10-15 13.00 - 14.00

Location: KTH, 3418

Lecturer: Aleksa Stankovic (KTH)


In this talk we introduce circuits and discuss them as a computational model useful for showing impossibility of solving some problems efficiently. We discuss their relationship to the P!=NP problem, and also show one particular technique for showing lower bounds in this context by discussing an exponential lower bound for constant-depth circuits computing XOR function, which was introduced by Razborov and later simplified by Smolensky. We do not assume any previous knowledge of circuits or complexity theory and introduce all the necessary background. In particular, the proofs will rely on some basic properties of polynomials and polynomial spaces.