Rahul Ilango

Rahul Ilango

Computer Science PhD Student

Massachusetts Institute of Technology

About Me

I am a second-year PhD student studying Theoretical Computer Science at MIT advised by Ryan Williams. Before this, I was an undergraduate at Rutgers University, where I was lucky enough to discuss research and learn from Eric Allender and Michael Saks. I also participated twice in the DIMACS REU program.

Most of my research is in the field of Computational Complexity Theory, which quantifies the amount of resources — like time and hardware — needed to solve computational tasks, like finding the fastest route from point A to point B on a map.

my first initial + ilango @mit.edu (plus not included)

My Research Focus

The Minimum Circuit Size Problem (MCSP) and its Connections.

Learn More About MCSP in my TCS+ Talk

My research so far has focused on understanding the complexity of a problem called MCSP. While MCSP has been studied since at least the 1950s, it remains quite mysterious, evading the kind of understanding we have for thousands of other problems in complexity theory. Even so, researchers have discovered fascinating connections between MCSP and other areas in Theoretical Computer Science.

For example, MCSP could be a "universal attack on cryptography": if you found a fast algorithm for MCSP, you could use it to break any type of cryptography. Thus, we expect (but do not know) that MCSP is not an easy problem to solve. My research is working towards proving MCSP is hard, which is a necessary step towards attaining provably secure cryptography.


(reverse chronological order)

Constant Depth Formula and Partial Function Versions of MCSP are Hard

Rahul Ilango

FOCS ‘20 · Best Student Paper Award ·
Full Vesion PDF

Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas

Rahul Ilango

CCC ‘20 · Best Student Paper Award · Invited for TOC Special Issue for CCC'20
Draft Journal PDF Conference PDF Talk

NP-Hardness of Circuit Minimization for Multi-Output Functions

Rahul Ilango, Bruno Loff, and Igor Oliveira

CCC ‘20
PDF TCS+ Talk Loff’s HSE Talk CCC Talk Mention on Scott A.’s Blog

Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC0[p]

Rahul Ilango

ITCS ‘20 · Best Student Paper Award

AC0[p] Lower Bounds Against MCSP via the Coin Problem

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal


The Non-hardness of Approximating Circuit Size

Eric Allender, Rahul Ilango, and Neekon Vafa

CSR ‘19 · to appear in Theory of Computing Systems Special Issue for CSR ‘19

Unique Rectification in d-Complete Posets: Towards the K-Theory of Kac-Moody Flag Varieties

Rahul Ilango, Oliver Pechenik and Michael Zlatin

Electronic Journal of Combinatorics · Formal Power Series and Algebraic Combinatorics Conference (FPSAC ‘19)

Fun Stuff

Warning: not related to research!

  • A desk I recently made for my mom :)
  • A recipe I like when I find time to cook
  • A tool I made that has helped thousands of Rutgers students plan their degrees
  • Some things I co-authored a while ago that are not math papers