This week we began our investigations into the complexities of MCSP and MKTP
(a version of MCSP which models computation via Turing machines instead of
circuits)
and discussed potential research directions. I read papers [1-3] below and
participated in several joint meetings with Prof. Allender, Sasha, Vishal,
and Harsha (one of Prof. Allender's graduate students who will also be
part of the team this summer). Personally I focused on trying to assemble
a coherent picture of the "landscape" of the complexity of MCSP. Most results we are
studying are of the form "Problem \(P\) does/does not reduce to MCSP variant \(V\)
under \(\mathcal{C}\) type of reductions", and we have little understanding
of the "robustness" of these results when we slightly vary the definitions.
Notions of reductions we've discussed include \(\mathbf{AC}^0\) (both
uniform and non-uniform variants), \(\mathbf{NC}^0\) (we typically get hardness
for \(\mathbf{NC}^0\) reductions "for free" from hardness for \(\mathbf{AC}^0\)
reductions),
We have decided to (at least initially) focus on last year's REU paper [3], which shows that MKTP is hard for a complexity class called \(\mathsf{NISZK_L}\) (non-interactive statistical zero-knowledge proofs with log-space verifiers) under uniform projections. This is a result which is not yet known to hold for MCSP and we are thinking about why. Also, we are preparing for our introductory presentation next week.
On Tuesday we gave our introductory presentation to the rest of the REU students. It was pretty amazing to see the variety of different projects people are working on (lots of biology!).
Getting back to complexity, this week we continued studying last year's REU paper [3] and tried to identify the limitations which prevent us from extending the results to MCSP. [3] uses ideas from an earlier paper [4] which bound the KT complexity of independent samples drawn from a distribution in terms of its entropy. Roughly, they show that if \(t\) is a large polynomial, with high probability the KT complexity of \(t\) samples from a random variable \(X\) is close to \(tH(X)\), and this distance is a smaller polynomial than \(t\). This allows the construction of a simple projection from the "entropy approximation" promise problem --- distinguishing between circuits whose entropy on a uniform input is \(k\) vs. \(k+1\) --- which is complete for \(\mathsf{NISZK}\). Unfortunately, the analysis for KT complexity relies on the fact that we have very tight bounds for the KT complexity of the "hardest" string \(x \in \{0,1\}^n\) (it is \(\approx n\)), and we lack such tight bounds for the circuit complexity of the largest string.
Given this, we read another paper [5] which manages to prove \(\mathsf{AC}^0[p]\) lower bounds against MCSP --- a result which was previously known for MKTP. We are thinking about how this result circumvented the issues with lack of tight bounds for circuit complexity.
This week we continued to examine Golovnev et al.'s paper [5] which shows that MCSP is hard for \(\mathsf{AC}^0[p]\) circuits. The "meat" of this paper was via a reduction through the coin problem --- the distributional problem of distinguishing strings of unbiased coin flips from strings of slightly biased coin flips. This problem is known to be hard for \(\mathsf{AC}^0[p]\), and so the paper simply constructs a reduction from the coin problem to MCSP, which ultimately uses the fact that random functions are substantially more complex than random biased functions.
We began discussing whether it may be possible to make further use of this reduction to build a simple \(m\)-reduction from other problems of interest (e.g., \(\mathsf{Majority}\) or \(\mathsf{Parity}\)) to MCSP. There is a known reduction from \(\mathsf{Majority}\) to the coin problem due to Shaltiel and Viola [6] (it is cited in [5]), but this reduction is not necessarily an \(m\)-reduction.
This week began with a continued examination of the idea to extend the Shaltiel and Viola reduction [6] to give an \(m\)-reduction from some problem of interest to MCSP. However, we are lacking a crucial ingredient: a "gadget" that lets us take the \(\mathsf{And}\) or \(\mathsf{Or}\) of two MCSP instances (even simple ones, with constant thresholds, created by projection, etc.). We considered instead trying to build a reduction to the minimum formula size problem (MFSP), on the theory that we could construct such gadgets. (Formulas are circuits in which every gate has fan-out 1, so they cannot reuse computations. This makes it easier to reason about the complexity of various combinations of functions.)
Along these lines, we first looked at a passage in Jukna's book [§1.4, 7] which discusses the best known bounds for the formula sizes of the hardest \(n\)-bit Boolean function. These are even weaker than those which are known for circuit size, and so the reduction of [4] does not seem to go through directly. (If it did, it would supersede any attempt to directly show that \(\mathsf{TC}^0\) problems reduce to MFSP.) Next, I looked at a passage in Wegener's book [§10.2, 8] which discusses the formula complexity of combinations of functions. Indeed, given Boolean functions \(f,g : \{0,1\}^n \to \{0,1\}\), it is easy to show that \(L(f \vee g) = L(f) + L(g) \pm 1\), where \(L(\cdot)\) denotes formula size and \(f \vee g\) is the \(2n\)-bit function mapping \(x,y\) to \(f(x) \vee g(y)\). However, this "gadget" does not suffice for our purposes, since it increases the size of truth tables quadratically, which means that it could only be applied a constant number of times.
Given this issue, we decided to focus on a different problem; specifically, we will study the recent papers of Fu [9] and Ilango [10] which prove hardness, or barriers towards proving hardness, for some seemingly related variants of circuit minimization.
This week, I studied Ilango's paper [10] in more detail, attempting to understand the techniques he uses to show that the depth-\(d\) formula size problem is \(\mathsf{NP}\)-complete under quasipolynomial-time randomized reductions. The heart of his reduction is a depth reduction for computing the variant of the problem where the top gate is an \(\mathsf{OR}\). I attempted to understand how simply this reduction could be implemented (in particular, can it be implemented as a quasipolynomial-size, nonuniform (or randomized?) \(\mathsf{AC}^0\) reduction with oracle gates?). The current construction uses some \(\mathsf{Majority}\) operations but we have some ideas as to how to work around this.
I also had some insights this week with regard to our earlier discussions on showing hardness of MCSP for \(\mathsf{Majority}\). Using the framework of Golovnev et al. [5] for analyzing the circuit complexity of random strings, I believe that I was able to construct an \(m\)-projection from \(\mathsf{Majority}\) to MCSP. It has both a "randomized" and "nonuniform" mode. One error in the argument for nonuniformity came up during our Thursday group meeting, but it appears to be fixable by slightly adjusting some of the concentration bounds that we use. Sasha and I also had several discussions over email which helped clarify the construction.
I have further ideas which may enable projections from \(\mathsf{Parity}\), or even maybe all of \(\mathsf{TC}^0\), to MCSP. I plan to explore these ideas over the weekend/next week, in addition to continuing to study the Ilango paper [10].
Eric was traveling this week and so our discussions were solely conducted over email. This week I mostly continued focusing on the papers of Ilango [10] and Fu [9], while still thinking through the projection I constructed last week.
A formula is \(\mathsf{Or}\)-top if the final output gate is an \(\mathsf{Or}\). The reduction in the Ilango paper [10] consists of several parts:
In order for us to understand how simply Ilango's reduction can be implemented, we have to separately analyze each of these three components. (2) is the "technical heart" of the paper; (1) is relatively simple and follows from the existence of explicit functions with large gaps between depth-\(d\) and depth-\((d-1)\) formula complexity; and (3) is based on earlier work using PCPs. I hope to "drill down" next week into understanding the details of how each might be implemented.
Eric was again out of town this week, so we had our first video meeting on Friday.
Unfortunately, in the middle of the week, I realized that my earlier idea for a \(\mathsf{Parity}\) to \(\mathsf{MCSP}\) reduction was wrong. I planned to combine several randomized projections from \(\mathsf{Wt}_i\) (the indicator function for whether a Boolean string has Hamming weight exactly \(i\)) to \(\mathsf{MCSP}\) via \(\mathsf{Xor}\) gates. Each projection would be designed to yield strings of independently sampled bits, where the bias of the bits is slightly different in the \(\mathbf{Yes}\) and \(\mathbf{No}\) cases. However, I forgot that the loss in distinguishability given the \(\mathsf{Xor}\) of random bits is multiplicative; hence the gap in bias between the \(\mathbf{Yes}\) and \(\mathbf{NO}\) cases for \(\mathsf{Parity}\) would be too small to be detected using \(\mathsf{MCSP}\) (or indeed any function — we'd require an exponential number of samples to notice a difference when the gap in biases is exponentially small!). However, we still have the reduction from \(\mathsf{Majority}\) to \(\mathsf{MCSP}\).
Given this, in our meeting with Eric on Friday we discussed mostly the Ilango and Fu papers [9,10]. I read the relevant sections of [9] in depth on Wednesday and Thursday, and we discussed in our meeting with Eric why we may be able to show that depth-\(d\) formula complexity cannot be hard for \(\mathsf{NP}\) (indeed, even \(\mathsf{ZPP}\)) under quasipolynomial-size \(\mathsf{AC}^0\) reductions unless \(\mathsf{ZPP}=\mathsf{EXP}\); indeed, it turns out that in padding arguments, it typically is okay to relax from polynomial to quasipolynomial functions.
On Friday we also discussed aspects of the plan to implement Ilango's reduction [10] as a uniform, quasipoly-size \(\mathsf{AC}^0\) reducion. As I wrote above in Week 6, Ilango's reduction has three parts. Parts 1 and 2 seem very plausibly implementable in \(\mathsf{AC}^0\), although some work will be required to derandomize Part 2. Part 3, on the other hand, seems trickier. Recall that Part 3 is the \(\mathsf{NP}\)-hardness-of-approximation result for minimizing DNF formula complexity. Ilango [10] uses a hardness result due to Khot and Saket [11]; their reduction seems likely too sophisticated for our purposes, as it involves PCPs. But to make the proof work we only need hardness of \(O(1)\)-approximation, while [11] proves hardness of \(O(n^{1-\epsilon})\)-approximation for every \(\epsilon>0\). Hence we will read another hardness-of-approximation result for DNF minimization due to Allender, Hellerstein, McCabe, Pitassi, and Saks [12] which seems to use much simpler tools.
This week we looked at the Allender et al. paper [12] which proves hardness of approximation for DNF minimization. One key ingredient in this paper is an (approximation-preserving) reduction to DNF minimization from partial DNF minimization (i.e., finding the smallest DNF formula consistent with a partially-specified truth table). This reduction uses \(\mathsf{Parity}\) as a gadget to guarantee the presence of certain clauses in a minimal DNF, but we believe it may be possible to use some other gadget.
We also discussed another possible problem, on trying to better understand the class \(\mathsf{NISZK}_{\mathsf{L}}\). Eric conjectures that it is equal to \(\mathsf{NISZK}_{\mathsf{NC}^0\), which seems plausible, since we know that entropy approximation for \(\mathsf{NC}^0\) circuits is a complete problem. However, the natural protocol for this problem (see e.g., [3]) requires 2-universal hash functions, which do not appear implementable in \(\mathsf{NC}^0\).
Finally, on Tuesday there was also a very interesting graduate school panel which we got to attend.
This week I mostly spent working on our final writeup for the REU, which is due Friday, as well as our final presentation. Unfortunately, in the course of writing up our work, we discovered several issues that we hadn't caught earlier in the summer in our proofs. Firstly, our \(\mathsf{Majority}\) to \(\mathsf{MCSP}\) reduction relied on some assumptions about the monotonicity of expected circuit complexity of \(p\)-biased random functions (as a function of \(p\)); we contacted Rahul Ilango about this issue, who confirmed to us that this problem is actually still open. Moreover, in the course of writing up our version of Fu [9]'s proof that \(\mathsf{NP}\) hardness or MCSP and variants under adaptive reductions implies new/likely very difficult lower bounds, Sasha discovered that we don't actually seem to be able to extend to the constant-depth formula case. Finally, Eric now thinks that pieces of the Ilango reduction [10] cannot be derandomized. Regardless, our goal is to carefully write-up everything we have and note where we rely on unproven assumptions.