Rahul Ilango

Rahul Ilango

Computer Science PhD Student

Massachusetts Institute of Technology

About Me

I am a fifth-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.

Highlights

Quanta Magazine

My work has been featured twice in Quanta Magazine:

2023 Machtey Award (FOCS ‘23 Best Student Paper)

My work “SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle” won the 2023 Machtey Award

NSF Graduate Research Fellow

I was awarded an NSF Graduate Research Fellowship to support my graduate studies and research.

2020 CCC Best Student Paper

My work “Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas” won the 2020 “Best Student Paper Award” at the Computational Complexity Conference

2020 Machtey Award (FOCS ‘20 Best Student Paper)

My work “Constant Depth Formula and Partial Function Versions of MCSP are Hard” won the 2020 Machtey Award

2020 ITCS Best Student Paper

My work “Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC0[p]” won the 2020 “Best Student Paper Award” at the Innovations in Theoretical Computer Science conference.

Publications

(reverse chronological order)

Beating Brute Force for Compression Problems

Shuichi Hirahara, Rahul Ilango, Ryan Williams

STOC ‘24
PDF

SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

Rahul Ilango

FOCS ‘23 · Best Student Paper Award
PDF

Towards Separating Computational and Statistical Differential Privacy

Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi

FOCS ‘23
PDF

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

Rahul Ilango, Jiatu Li, and Ryan Williams

STOC ‘23
PDF

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

Yizhi Huang, Rahul Ilango, Hanlin Ren

STOC ‘23
PDF

A Duality Between One-Way Functions and Average-Case Symmetry of Information

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor Carboni Oliveira

STOC ‘23
PDF

Robustness of Average-Case Meta-complexity via Pseudorandomness

Rahul Ilango, Hanlin Ren, and Rahul Santhanam

STOC ‘22
PDF

The Minimum Formula Size Problem is (ETH) Hard

Rahul Ilango

FOCS ‘21
PDF

Hardness of Constant-Round Communication Complexity

Shuichi Hirahara, Rahul Ilango, and Bruno Loff

CCC ‘21
PDF

Constant Depth Formula and Partial Function Versions of MCSP are Hard

Rahul Ilango

FOCS ‘20 · Best Student Paper Award ·
Draft Journal 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
PDF

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

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

ICALP ‘19
PDF

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
PDF

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)
PDF

Fun Stuff

not research related

  • A desk I made for my mom :)
  • Some music I co-wrote
  • An educational “game” I created introducing the four color theorem, P vs NP, and zero knowledge proofs
  • A recipe I really like
  • I helped thousands of Rutgers’ students make 4-year plans for their degrees via a (now-defunct) tool I made (ScarletScheduleDesigner)