DIMACS
DIMACS REU 2019

General Information

me
Student: Amulya Musipatla
Office: CoRE 442
School: Carnegie Mellon University
E-mail: amusipat@andrew.cmu.edu
Project: The Minimum Circuit Size Problem: A possible NP-Intermediate Problem

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.

Weekly Log

Week 1:
This week I met my partner Azucena as well as our mentor Professor Allender. He introduced us to potential problems and areas we could work on, and referred us to a few papers that we could read. Most of our week was spent trying to understand these papers, which proved to be difficult. We mainly tried to focus on the introductions and the main ideas of the theorems so that we could get a general idea of the types of techniques used and get a better introduction to this problem and what people currently know about it. We also worked on our presentation to introduce our research to the other REU students.
Week 2:
On Monday we presented the powerpoint we made to the other REU students, and then we went to work on reading more papers. Since this was the last week that Professor Allender is here before he heads off to a conference, we met with him often to ask questions that we had about the papers we were reading. We found that it was easier to understand the concepts this week, and we were able to get through more proofs. We were still confused about some of the intuition that the authors had, and we met with Rahul Ilango, who worked with Professor Allender last summer. He explained the results he obtained with Neekon Vafa which helped us understand their intuition and process more, and we decided to try to jump into a problem that Professor Allender told us about.
Week 3:
Professor Allender left for a meeting in Russia this week, and before he left we talked about a potential reduction to explore. This week we continued to work on that and emailed him back and forth with our revisions. He also introduced us to a different problem, which led to us reading a lot of papers about the graph isomorphism problem and its relationship to the class DET. We struggled for a bit with understanding some of the steps in the paper, but walked through it all and by the end of the week we were able to come up with something that we thought was promising. We wrote up our ideas and sent it to Professor Allender on Friday.
Week 4:
On Monday we went to Nokia Bell Labs, which took up most of our day. There we listened to some presentations and got to visit the anechoic chamber. Professor Allender wasn't able to respond as often this week because of limited internet access, so we decided to try to learn more about MCSP and work on a potential problem that he had talked to us about earlier. Our difficulty here was that we weren't sure what would be difficult to prove and what would be easy, so we didn't know if our attempts really had any potential. He responded with more information once he was able to, and gave us another problem to work on that he thought was reasonable. We spent the rest of the week familiarizing ourselves with that, and we made some weird observations that could help us out if we could formalize them more.
Week 5:
We focused more on trying to disprove the projection to MCSP, but we found that it was hard to formalize the weird observations we were making. While they seemed unusual, reaching a contradiction was difficult. Professor Allender gave us more tips on this and we met with him at the end of the week. We talked about our ideas and our current approach, and while he agreed that there was a lot that was weird about it, projections are actually a lot more powerful than we initially thought. He told us more about uniformity and referred us to some more examples of it, and also talked to us about an idea that one of his colleagues had mentioned to him that he thought we could work on. He also asked us to write up one of our results that we came up with earlier in Week 3.
Week 6:
We continued to work on trying to disprove a projection, and to this extent we read papers about uniformity to understand that concept more, since Professor Allender stressed the importance of using it to make things easier for us. It seemed clearer to us how uniformity could work, and we worked on trying to apply ideas from a paper we had read earlier. We also started to try to familiarize ourselves with the problem he introduced last week about Kolmogorov complexity and its relation to the entropy of a distribution, which was very different from the previous problems we had talked about.
Week 7:
We had a graduate school panel on Monday of this week, where some professors (including Professor Allender) and some current graduate students spoke for a bit and then answered questions about the process. It was really helpful to hear a lot of their answers, and I feel like I have a slightly better idea of the process and what to focus on more. This week we worked on our reduction more. We tried out the naive approach that worked for MKTP first, expecting it to fail but hoping to get more intuition from that. It worked out how we expected it to, where we couldn't lower bound our worst case as nicely as we would want to. We thought about different ways to fix this, but we weren't able to come up with something feasible in AC0. In the between our approaches, we put together our final presentation in which we focused on our result for MKTP's hardness. We weren't very sure of how much detail to get into since we knew our audience had varied backgrounds in complexity, but I think that our presentation ended up being accessible to everyone while still presenting our main ideas and techniques.
Week 8:
This week was DIMACs week of complexity: there were workshops on the first two days, a complexity tutorial day, and the Computational Complexity Conference was held on campus on Thursday, Friday, and Saturday. Earlier in the week, we mainly focused on completing a rough draft of the technical writeup Professor Allender asked for, which we wanted to send to him by the end of the week for him to look over. We attended some of the lectures that we thought could be interesting from Monday to Wednesday. We also were able to attend the conference, which was a really cool experience! Some of the talks were a little difficult and probably required more background knowledge than I had, but there were a few that I could understand because of this summer. We also got to see a lot of professors whose papers we had read and studied extensively when working on our own research. We attended the conference on Thursday and Friday, and went for one talk on Saturday before our flight out to Prague!
Week 9:
We arrived in Prague on Saturday and got to check out the city before our week at Charles University. We had lectures arranged for us about the Erdos-Szekeres theorem, chordal graphs, zero knowledge proofs, and generating functions. There was also a topological workshop going on this week, and on Tuesday we attended some introductory talks. We addressed some of the feedback we received on our draft of our report before sending it to Lazaros.
Week 10:
This was our last week of the REU! The annual midsummer combinatorial workshop was going on this week, and we attended many of the talks that were given by researchers from around the world. It was a really cool experience and gave a glimpse into what problems combinatorialists were looking into!

Presentations

Additional Information

Acknowledgements

This work was carried out during the 2019 DIMACS REU program at Rutgers University, supported by NSF grant CCF-1852215.