Rahul Ilango

44 papers A* 13A 4Misc 1Journal 26
YearRankTypeTitle / Venue / Authors
2025 J jnl
Communication Complexity is NP-hard.
CoRR
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2025 J jnl
Communication Complexity is NP-hard.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2025 A* conf
Cryptography Meets Worst-case Complexity: Optimal Security and More From iO and Worst-case Assumptions.
FOCS
Rahul Ilango, Alex Lombardi
2025 J jnl
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions.
Electron. Colloquium Comput. Complex.
Rahul Ilango, Alex Lombardi
2025 J jnl
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions.
IACR Cryptol. ePrint Arch.
Rahul Ilango, Alex Lombardi
2025 J jnl
Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness.
Electron. Colloquium Comput. Complex.
Rahul Ilango
2025 A* conf
Gödel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness.
FOCS
Rahul Ilango
2025 J jnl
Gödel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness.
IACR Cryptol. ePrint Arch.
Rahul Ilango
2025 J jnl
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.
SIAM J. Comput.
Yizhi Huang, Rahul Ilango, Hanlin Ren
2025 A* conf
NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions.
FOCS
Shuichi Hirahara, Rahul Ilango
2025 J jnl
The Oracle Derandomization Hypothesis is False (And More) Assuming No Natural Proofs.
Electron. Colloquium Comput. Complex.
Rahul Ilango
2024 A* conf
Beating Brute Force for Compression Problems.
STOC
Shuichi Hirahara, Rahul Ilango, R. Ryan Williams
2024 J jnl
Constant Depth Formula and Partial Function Versions of MCSP Are Hard.
SIAM J. Comput.
Rahul Ilango
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
IACR Cryptol. ePrint Arch.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 A* conf
A Duality between One-Way Functions and Average-Case Symmetry of Information.
STOC
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 J jnl
Beating Brute Force for Compression Problems.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Ryan Williams
2023 A* conf
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic.
STOC
Rahul Ilango, Jiatu Li, R. Ryan Williams
2023 J jnl
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic.
Electron. Colloquium Comput. Complex.
Rahul Ilango, Jiatu Li, Ryan Williams
2023 A* conf
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.
STOC
Yizhi Huang, Rahul Ilango, Hanlin Ren
2023 J jnl
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.
Electron. Colloquium Comput. Complex.
Yizhi Huang, Rahul Ilango, Hanlin Ren
2023 J jnl
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.
IACR Cryptol. ePrint Arch.
Yizhi Huang, Rahul Ilango, Hanlin Ren
2023 A* conf
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle.
FOCS
Rahul Ilango
2023 J jnl
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle.
Electron. Colloquium Comput. Complex.
Rahul Ilango
2023 J jnl
Separating Computational and Statistical Differential Privacy (Under Plausible Assumptions).
CoRR
Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2023 A* conf
Towards Separating Computational and Statistical Differential Privacy.
FOCS
Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022 A* conf
Robustness of average-case meta-complexity via pseudorandomness.
STOC
Rahul Ilango, Hanlin Ren, Rahul Santhanam
2021 A conf
Hardness of Constant-Round Communication Complexity.
CCC
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2021 J jnl
Hardness of Constant-round Communication Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2021 J jnl
Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity.
Electron. Colloquium Comput. Complex.
Rahul Ilango, Hanlin Ren, Rahul Santhanam
2021 A* conf
The Minimum Formula Size Problem is (ETH) Hard.
FOCS
Rahul Ilango
2021 J jnl
The Non-hardness of Approximating Circuit Size.
Theory Comput. Syst.
Eric Allender, Rahul Ilango, Neekon Vafa
2020 A conf
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p].
ITCS
Rahul Ilango
2020 A conf
Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas.
CCC
Rahul Ilango
2020 A* conf
Constant Depth Formula and Partial Function Versions of MCSP are Hard.
FOCS
Rahul Ilango
2020 J jnl
Constant Depth Formula and Partial Function Versions of MCSP are Hard.
Electron. Colloquium Comput. Complex.
Rahul Ilango
2020 A conf
NP-Hardness of Circuit Minimization for Multi-Output Functions.
CCC
Rahul Ilango, Bruno Loff, Igor C. Oliveira
2020 J jnl
NP-Hardness of Circuit Minimization for Multi-Output Functions.
Electron. Colloquium Comput. Complex.
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira
2019 J jnl
$AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP.
Electron. Colloquium Comput. Complex.
Rahul Ilango
2019 A* conf
AC
ICALP
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019 J jnl
AC0[p] Lower Bounds against MCSP via the Coin Problem.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019 Misc conf
The Non-hardness of Approximating Circuit Size.
CSR
Eric Allender, Rahul Ilango, Neekon Vafa
2018 J jnl
The Non-Hardness of Approximating Circuit Size.
Electron. Colloquium Comput. Complex.
Eric Allender, Rahul Ilango, Neekon Vafa
2018 J jnl
Unique Rectification in d-Complete Posets: Towards the K-Theory of Kac-Moody Flag Varieties.
Electron. J. Comb.
Rahul Ilango, Oliver Pechenik, Michael Zlatin