School of Mathematics

In math, one often studies random aspects of deterministic systems and structures. In CS, one often tries to efficiently create structures and systems with specific random-like properties. Recent work has shown many connections between these two...

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.