School of Mathematics

Let $CC_{o(n)} \left[ m \right]$ be the class of circuits that have size $o(n)$ and in which all gates are $MOD_m$ gates.

--We show that $CC[m]$ circuits cannot compute $MOD_q$ in sub-linear size when $m, q \ge 1$ are co-prime integers. No non...

The "P vs. NP" problem is a central outstanding problem of computer science and mathematics. In this talk, Professor Wigderson attempts to describe its technical, scientific, and philosophical content, its status, and the implications of its two...

The series of lectures commemorating the 75th anniversary of the Institute, organized by the School of Mathematics, featured some of the world's leading mathematicians, all of whom have been Members or Visitors of the Institute.