# Noah Singer's REU 2021 Web Page

Student: Noah Singer (personal site)
School: Harvard University
Email: noah.singer (at) college.harvard.edu
Project: The Minimum Circuit Size Problem
Mentor: Eric Allender
Student collaborators: Vishal Ramesh, Sasha Sami

### Project Description

The Minimum Circuit Size Problem (MCSP) is a computational problem in NP that is widely believed to be hard to compute, although many researchers suspect that it is NOT NP-complete. However, there is currently only weak evidence to support this suspicion. This REU project will endeavor to find stronger evidence, of the form "If MCSP is NP-complete, then something weird happens". Another possible direction involves clarifying the relative complexity of MCSP and other candidate NP-Intermediate problems. The PI has recently proved some new lower bounds on the complexity of MCSP and related problems, and it should be possible to build on this recent progress. The PI has previously supervised research with REU students on this topic which has led to publications, and there is more work to be done, which should be accessible to an REU student.

### Weekly Reports

#### Week 1

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), local reductions (i.e., those s.t. individual output bits can be computed in very small time and/or space), and projections, which are circuits consisting only of $$\mathsf{Not}$$ gates along with constants. Surprisingly, most natural $$\mathbf{NP}$$-complete problems are even $$\mathbf{NP}$$-complete under projections (e.g., $$\mathsf{SAT}$$), whereas [1] shows that MCSP cannot even be $$\mathsf{NP}$$-complete under reductions which can calculate an individual output bit in $$O(n^{1/2-\epsilon})$$ time.

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.

#### Week 2

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.

#### Week 3

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.

#### Week 4

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.

#### Week 5

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].

#### Week 6

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:

1. A reduction from depth-$$d$$ formula complexity to depth-$$d$$ $$\mathsf{Or}$$-top formula complexity.
2. A reduction from depth-$$d$$ $$\mathsf{Or}$$-top formula complexity to depth-$$(d-1)$$ $$\mathsf{Or}$$-top formula complexity (for $$d \geq 2$$).
3. A reduction from depth-$$2$$ $$\mathsf{Or}$$-top formula complexity to some $$\mathsf{NP}$$-complete problem.
The formula class in (3) is the same as simply CNFs.

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.

#### Week 7

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.

#### Week 8

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.

#### Week 9

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.

### References

1. 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.
2. 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.
3. 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).
4. 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.
5. 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.
6. 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.
7. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Vol. 27. Algorithms and Combinatorics 13. Springer, 2012.
8. Ingo Wegener. The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science. John Wiley & Sons, Ltd., and B. G. Teubner, Stuttgart, 1987.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.

### Acknowledgements

I wish to thank the DIMACS REU program for hosting me this summer, supported by NSF grant CCF-1852215.