All reports by Author Rahul Ilango:

__
TR20-183
| 6th December 2020
__

Rahul Ilango#### Constant Depth Formula and Partial Function Versions of MCSP are Hard

__
TR20-021
| 21st February 2020
__

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira#### NP-Hardness of Circuit Minimization for Multi-Output Functions

__
TR19-021
| 19th February 2019
__

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

__
TR19-018
| 18th February 2019
__

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal#### AC0[p] Lower Bounds against MCSP via the Coin Problem

__
TR18-173
| 17th October 2018
__

Eric Allender, Rahul Ilango, Neekon Vafa#### The Non-Hardness of Approximating Circuit Size

Revisions: 1

Rahul Ilango

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

While ... more >>>

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

Rahul Ilango

The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... more >>>

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

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

Eric Allender, Rahul Ilango, Neekon Vafa

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME($n^{0.49}$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>