Rahul Ilango

According to our database, Rahul Ilango authored at least 23 papers between 2018 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions.

Rahul Ilango, Alex Lombardi

Electron. Colloquium Comput. Complex., 2025

Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness.

Rahul Ilango

Electron. Colloquium Comput. Complex., 2025

Communication Complexity is NP-hard.

Shuichi Hirahara, Rahul Ilango, Bruno Loff

Electron. Colloquium Comput. Complex., 2025

2024

Beating Brute Force for Compression Problems.

Shuichi Hirahara, Rahul Ilango, R. Ryan Williams

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Separating Computational and Statistical Differential Privacy (Under Plausible Assumptions).

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

CoRR, 2023

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic.

Rahul Ilango, Jiatu Li, R. Ryan Williams

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

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

Yizhi Huang, Rahul Ilango, Hanlin Ren

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

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

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

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

Rahul Ilango

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Towards Separating Computational and Statistical Differential Privacy.

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

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Robustness of average-case meta-complexity via pseudorandomness.

Rahul Ilango, Hanlin Ren, Rahul Santhanam

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity.

Rahul Ilango, Hanlin Ren, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2021

The Minimum Formula Size Problem is (ETH) Hard.

Rahul Ilango

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Hardness of Constant-Round Communication Complexity.

Shuichi Hirahara, Rahul Ilango, Bruno Loff

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p].

Rahul Ilango

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Constant Depth Formula and Partial Function Versions of MCSP are Hard.

Rahul Ilango

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

NP-Hardness of Circuit Minimization for Multi-Output Functions.

Rahul Ilango, Bruno Loff, Igor C. Oliveira

Proceedings of the 35th Computational Complexity Conference, 2020

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

Rahul Ilango

Proceedings of the 35th Computational Complexity Conference, 2020

2019

$AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP.

Rahul Ilango

Electron. Colloquium Comput. Complex., 2019

AC0[p] Lower Bounds against MCSP via the Coin Problem.

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

Electron. Colloquium Comput. Complex., 2019

AC⁰[p] Lower Bounds Against MCSP via the Coin Problem.

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

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

The Non-hardness of Approximating Circuit Size.

Eric Allender, Rahul Ilango, Neekon Vafa

Proceedings of the Computer Science - Theory and Applications, 2019

2018

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

Rahul Ilango, Oliver Pechenik, Michael Zlatin

Electron. J. Comb., 2018