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}\)
(__n__on-__i__nteractive __s__tatistical __z__ero-__k__nowledge proofs with
__l__og-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:

- A reduction from depth-\(d\) formula complexity to depth-\(d\) \(\mathsf{Or}\)-top formula complexity.
- A reduction from depth-\(d\) \(\mathsf{Or}\)-top formula complexity to depth-\((d-1)\) \(\mathsf{Or}\)-top formula complexity (for \(d \geq 2\)).
- A reduction from depth-\(2\) \(\mathsf{Or}\)-top formula complexity to some \(\mathsf{NP}\)-complete problem.

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.

- Cody D. Murray and R. Ryan Williams. "On the (Non) NP-Hardness of Computing Circuit Complexity". In:
*Theory of Computing*13.4 (2017). Conference version in CCC 2015, pp. 1-22. - Eric Allender, Rahul Ilango, and Neekon Vafa. "The Non-Hardness of Approximating Circuit Size". In:
*Theory of Computing Systems*65.3 (2021). Ed. by René Bevern and Gregory Kucherov, pp. 559-578. - Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. "Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity".
*Electronic Colloquium on Computational Complexity*28 (2021). - Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. "Minimum Circuit Size, Graph Isomorphism, and Related Problems". In:
*SIAM Journal on Computing*47.4 (2018). Conference version in ITCS 2018, pp. 1339-1372. - Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. "\(\mathsf{AC}^0[p]\) Lower Bounds against MCSP via the Coin Problem". In:
*Proceedings of the 46th International Colloquium on Automata, Languages, and Programming*. ICALP 2019 (Patras, Greece, July 9-Dec. 9, 2019). Ed. by Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi. Vol. 132. LIPIcs. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2019, 66:1-66:15. - Ronen Shaltiel and Emanuele Viola. "Hardness Amplification Proofs Require Majority". In:
*SIAM Journal on Computing*39.7 (2010). Conference version in STOC 2008, pp. 3122-3154. - Stasys Jukna.
*Boolean Function Complexity: Advances and Frontiers*. Vol. 27. Algorithms and Combinatorics 13. Springer, 2012. - Ingo Wegener.
*The Complexity of Boolean Functions*. Wiley-Teubner Series in Computer Science. John Wiley & Sons, Ltd., and B. G. Teubner, Stuttgart, 1987. - Bin Fu. "Hardness of Sparse Sets and Minimal Circuit Size Problem". In:
*Computing and Combinatorics*. COCOON 2020 (Aug. 29-31, 2020). Ed. by Donghyun Kim, R. N. Uma, and Zhipeng Cai. Vol. 12273. LNCS. Springer, 2020, pp. 484-495. - Rahul Ilango. "Constant Depth Formula and Partial Function Versions of MCSP Are Hard". In:
*2020 IEEE 61st Annual Symposium on Foundations of Computer Science*. FOCS 2020 (Nov. 16-19, 2020). IEEE Computer Society, 2020, pp. 424-433. - Subhash Khot and Rishi Saket. "Hardness of Minimizing and Learning DNF Expressions". In:
*2008 49th Annual IEEE Symposium on Foundations of Computer Science*. FOCS 2008 (Philadelphia, PA, USA, Oct. 25-28, 2008). 2008, pp. 231-240. - Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael Saks. "Minimizing Disjunctive Normal Form Formulas and \(\mathsf{AC}^0\) Circuits given a Truth Table". In:
*SIAM Journal on Computing*38.1 (Jan. 2008), pp. 63-84. - Johan Håstad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. "An Average-Case Depth Hierarchy Theorem for Boolean Circuits". In:
*Journal of the ACM*64.5 (Oct. 2017), 35:1-35:27.