Rahul Ilango
YOU?
Author Swipe
View article: Communication Complexity is NP-hard
Communication Complexity is NP-hard Open
In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the com…
View article: Beating Brute Force for Compression Problems
Beating Brute Force for Compression Problems Open
A compression problem is defined with respect to an efficient encoding function f; given a string x, our task is to find the shortest y such that f(y) = x. The obvious brute-force algorithm for solving this compression task on n-bit string…
View article: NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach Open
It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very…
View article: Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic Open
The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit C:{0,1}n→{0,1}m, where m>n. Although at least half of the strings of length m are correct answers, it is not clear how to determin…
View article: Towards Separating Computational and Statistical Differential Privacy
Towards Separating Computational and Statistical Differential Privacy Open
Computational differential privacy (CDP) is a natural relaxation of the standard notion of (statistical) differential privacy (SDP) proposed by Beimel, Nissim, and Omri (CRYPTO 2008) and Mironov, Pandey, Reingold, and Vadhan (CRYPTO 2009).…
View article: Robustness of average-case meta-complexity via pseudorandomness
Robustness of average-case meta-complexity via pseudorandomness Open
We show broad equivalences in the average-case complexity of many different meta-complexity problems, including Kolmogorov complexity, time-bounded Kolmogorov complexity, and the Minimum Circuit Size Problem. These results hold for a wide …
View article: Hardness of Constant-Round Communication Complexity
Hardness of Constant-Round Communication Complexity Open
How difficult is it to compute the communication complexity of a two-argument total Boolean function f:[N]×[N] → {0,1}, when it is given as an N×N binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographicall…
View article: NP-hardness of circuit minimization for multi-output functions
NP-hardness of circuit minimization for multi-output functions Open
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 C…
View article: Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas
Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas Open
A longstanding open question is whether there is an equivalence between the computational task of determining the minimum size of any circuit computing a given function and the task of producing a minimum-sized circuit for a given function…
View article: Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p] Open
The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function has a circuit of at most a given size. MCSP has been studied for over a half-century and has deep connections throughout theoretical computer science including t…
View article: AC^0[p] Lower Bounds Against MCSP via the Coin Problem
AC^0[p] Lower Bounds Against MCSP via the Coin Problem Open
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 a…
View article: Unique Rectification in $d$-Complete Posets: Towards the $K$-Theory of Kac-Moody Flag Varieties
Unique Rectification in $d$-Complete Posets: Towards the $K$-Theory of Kac-Moody Flag Varieties Open
The jeu-de-taquin-based Littlewood-Richardson rule of H. Thomas and A. Yong (2009) for minuscule varieties has been extended in two orthogonal directions, either enriching the cohomology theory or else expanding the family of varieties con…
View article: A Fixed-Depth Size-Hierarchy Theorem for AC$^0[\\oplus]$ via the Coin\n Problem
A Fixed-Depth Size-Hierarchy Theorem for AC$^0[\\oplus]$ via the Coin\n Problem Open
We prove the first Fixed-depth Size-hierarchy Theorem for uniform\nAC$^0[\\oplus]$ circuits; in particular, for fixed $d$, the class\n$\\mathcal{C}_{d,k}$ of uniform AC$^0[\\oplus]$ formulas of depth $d$ and size\n$n^k$ form an infinite hi…
View article: Unique rectification in $d$-complete posets: towards the $K$-theory of\n Kac-Moody flag varieties
Unique rectification in $d$-complete posets: towards the $K$-theory of\n Kac-Moody flag varieties Open
The jeu-de-taquin-based Littlewood-Richardson rule of H. Thomas and A. Yong\n(2009) for minuscule varieties has been extended in two orthogonal directions,\neither enriching the cohomology theory or else expanding the family of\nvarieties …