Rahul Ilango

According to our database, Rahul Ilango authored at least 20 papers between 2018 and 2023.

Collaborative distances:

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

2023

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic.

Rahul Ilango, Jiatu Li, Ryan Williams

Electron. Colloquium Comput. Complex., 2023

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

Rahul Ilango

Electron. Colloquium Comput. Complex., 2023

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

Yizhi Huang, Rahul Ilango, Hanlin Ren

Electron. Colloquium Comput. Complex., 2023

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

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

Electron. Colloquium Comput. Complex., 2023

Beating Brute Force for Compression Problems.

Shuichi Hirahara, Rahul Ilango, Ryan Williams

Electron. Colloquium Comput. Complex., 2023

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

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

CoRR, 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

Hardness of Constant-round Communication Complexity.

Shuichi Hirahara, Rahul Ilango, Bruno Loff

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

2020

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

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2020

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

Rahul Ilango

Electron. Colloquium Comput. Complex., 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

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

2018

The Non-Hardness of Approximating Circuit Size.

Eric Allender, Rahul Ilango, Neekon Vafa

Electron. Colloquium Comput. Complex., 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