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 unexpected happens." Another possible direction involves clarifying the relative complexity of MCSP and other candidate NP-Intermediate problems. The Minimum Kolmogorov Time-Bounded Complexity Problem (MKTP) is intimately related with MCSP, but there there are theorems known about one problem that are not known to be true of the other. A desired result in this area would be either extending known techniques from one to the other or proving a difference between these two problems.

---

Weekly Log

Week 1:

During the first part of the week, I met the other REU students along with my research partner Rahul Ilango. We met with our mentor Professor Eric Allender, who talked us through some possible research questions for our project. He introduced different directions, and Rahul and I spent a lot of our time this week reading through many relevant papers. The main goal for the next few days is to narrow down our research question to something specific enough so that we can get started working toward results. Finally, since we also have to present to the other REU students next Monday, we spent some time working on and rehearsing the powerpoint.

Week 2:

On Monday, Rahul and I gave a presentation to the other REU students about our project. From what I could tell, it went pretty well. It was nice to hear about all the other students' projects as well. For most of the week, our mentor Prof. Allender was at the Optimization, Complexity and Invariant Theory conference at the Institute for Advanced Study, and since it was closeby, Rahul and I decided to go for the first few days. While some of the talks were intriguing, we figured it would be a better use of our time to work on the project, as most of the topics at the conference did not have much to do with what we were working on. For the remainder of the week, we thought we had some directions for interesting results, but when trying to work them out, we ran into some issues. Over the next week we will probably try some other approaches and see what we can get.

Week 3:

Following the work of our previous week, Rahul and I dove deeper into adapting one of the ideas presented in a paper (that showed hardness of some form of MCSP) and tried to put something together. Unfortunately, after working through the details, we realized this approach wasn't going to work. Then we got started in another direction, and we thought we had an original result that looks at consequences of MCSP's hardness. On further investigation, however, it turns out this result was already shown a few years ago. With that in mind, we read through that paper in detail and found a few others on a very similar topic. We now have much more experience with the problem, so we hope we can extend the progress that others have made to get an interesting result.

Week 4:

Adding onto the previous week, we thought we could get some new results by focusing in on an approximate version of MCSP where some hardness theorems are still known but (we believe) haven't been fully explored. We tried to provide evidence that approximate versions of MCSP cannot always be hard, or if they are, then some interesting consequences follow. We thought we had a few interesting theorems, but at the end of the week, we learned that some of them have minor flaws, and one of the observations we thought we had actually follows from an earlier paper. Going into next week, we will likely try to patch these holes to get new, correct results.

Week 5:

On Monday, we tried strengthening our observation (that had already been proven by someone else), and it turns out a little tweak gives an original result! We were excited, and by trying things out even further, we even proved an extension of this result. We tentatively think that will be the limit of the technique we have, but perhaps we can use it in other contexts. On another front, we noticed that some results that have been proven seem to be easily modified to get stronger results. Overall, we were very happy with what we could do this week, and we have a few resulting questions that we hope to tackle next week.

Week 6:

For most of the week, we tried building on the results of last week. On Thursday, we thought we found a significant strengthening of what we had done previously. We were excited, but we unfortunately noticed on Friday that we had a flaw, and in fact we were making an assumption that renders some of our results (even from last week) invalid. Our original result from last week still holds though. For the rest of Friday, we tried to patch this bug, but in the process, we found some subtle structure that makes MCSP a little more powerful under limited reductions than we thought. We are unsure whether we'll follow this path further or explore new territory for the next three weeks.

Week 7:

In investigating the subtle properties of MCSP, we noticed that languages reducing to MCSP under some limited notion of reduction have an interesting property! Exploiting this idea, we recover a weaker version of a statement that we thought we had shown last week. Exploring these details further, we noticed our techniques generalize to Boolean functions that have certain combinatorial properties that turn out to be well-studied. To strengthen our results, we focused our attention to the properties themselves, but we didn't have much luck, and the literature isn't reassuring as many related properties are long-standing open questions. We also spent time working on our presentation, which we think went well. I enjoyed hearing about the other projects!

Week 8:

Looking more into this property of Boolean functions, we ran code to try to find examples of functions that would give us some insight as to what's going on. Since the search space of Boolean functions on, say, 6 variables is intractable, we were only able to look at a tiny fraction of all the functions, and unfortunately we weren't able to find examples with the properties we were looking for. We also spent a lot of time this week writing up the results we had because Rahul was leaving for Prague near the end of the week. We noticed a little flaw in one of our proofs. Fortunately, we think it can be fixed (even though it will make the proofs harder to follow). Rahul and I had our last meeting with our mentor Prof. Allender in which we talked through some ideas for mending the proof. Lastly, I bid farewell to Rahul and the other REU students heading to Prague.

---

Presentations

• First Pesentation

---

Additional Information

• My mentor is Prof. Eric Allender.