General Information

---

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 Log

Week 1:

We met with our advisor Eric Allender and his graduate student Harsha, and discussed some open problems to investigate. Most of the week was spent reading papers on recent results involving MCSP and MKTP. I came across many new complexity classes like AC0[p] and SZK. We also began preparing for our introductory presentation next week.

Week 2:

I read a paper which proved AC0[p] lower bounds against MCSP, a result which was previously known for MKTP. In particular, it used a proof technique called a hybrid argument that is used to distinguish probability distributions. As practice, I attempted to derive a similar proof for MKTP. I also looked at a paper on MCSP and Graph Isomorphism that initially introduced lemmas used to prove hardness of MKTP against NISZK.

Week 3:

Continuing with the paper from last week that uses hybrid argument, we began to consider whether we could use produce an m-reduction from the Majority or Parity problem to MCSP. I read a paper by Shaltiel and Viola that gives a reduction from Majority to the coin problem, but it is not obvious to me that this could be adapted to an m-reduction.

Week 4:

To overcome this barrier, we instead considered producing a reduction from coin problem to the minimum formula size problem (MFSP). Formulas are a certain type of circuits that can be represented as a sort of tree. Essentially, the motivation was the make the problem easier. On the recommendation of our advisor, we briefly skimmed through sections of Wegener's book on boolean formula complexity. However, the tools there giving complexity in relation to the direct product of formulas was not strong enough for our purposes.

Week 5:

Noah suggested that it might be possible to adapt the coin problem argument to give a randomized projection from Majority to MCSP. Some errors were raised by Eric regarding non-uniformity. It appears that adjusting concentration bounds used in the proof mght fix this. I spent the rest of the week following this.

Week 6:

Eric was travelling this week, nevertheless our discussions were carried out over email. I focused on the papers of Ilango and Fu. The reduction in the Ilango paper consisted of three parts. 1 and 3 were relatively straightforward and followed from existing works. Part 2 involved setting up the recursion which I worked on for the rest of the week.

Week 8:

I looked at the hardness of approximation for min DNF by Allender et al. The reduction uses a Parity gadget, but Noah suggested that we could circumnavigate this. Apart from that, we discussed another problem involving the class NISZK_L. I had the chance to attend the graduate school panel which got me thinking about the admissions process.

Week 9:

We worked on our final presentation and paper that were due by the end of the week. This gave rise to some issues in the proofs we had been working on. One of our assumptions for the Majority to MCSP reduction was that expected circuit complexity for p-biased random functions is monotonic. This in fact is an open question, as confirmed by Rahul Ilango through email correspondence.

---

Additional Information

Final presentation: Simple reductions to circuit minimization

Final paper: Simple reductions to circuit minimization

• Mentor: Eric Allender
• Student collaborators:
  • Noah Singer
  • Sasha Sami

---

Acknowledgements

This work was carried out while the author was a participant in the 2021 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.