General Information

---

Project Description

The Minimum Circuit Size Problem (MCSP) holds a special place in computational complexity theory. It is intimately related to questions such as derandomization, natural proofs, circuit lower bounds, and it is one of the few natural problems which we have evidence for being NP-intermediate. We hope to discover new insights regarding this problem.

---

Weekly Log

Week 1:

This week I met with my partner Neekon Vafa, and Professor Allender. Professor Allender provided us with several different research directions and papers to read. Most of the week was spent going over the papers and preparing a presentation to the other DIMACS students on our project. Some of the papers are quite dense, so we've been trying to just read the introductions, get an idea of the techniques used, and summarize the results. Unrelated to the project, I also began working on some maps and a powerpoint for the other DIMACS students so that they could get an idea of the Rutgers area.

Week 2:

On Monday, we made our presentation in front of our fellow DIMACS students. We tried not to make the talk too techinical, as our main goal was to have the other students understand what we were doing. The presentation went fairly well; the other students seemed to be able to follow. We presented two possible directions to pursue research-wise. After our presentation, we went to a conference at the IAS on opimization, complexity, and invariant theory. Our advisor was attending this conference all week, so we met with him there Monday and Tuesday. We didn't have quite enough background for the talks, so we ended up deciding not to go after Tuesday. Throughout the week, we were reading papers to try to find an achievable direction which we could do research on. It has been somewhat frustrating, but we think we have found some results that we can extend. We will have to see.

Week 3:

This week Neekon and I were still working background papers. We had some ideas for novel approaches, but, each time, we hit barriers that we were not sure how to surmount. We met with Professor Allender on Monday, Tuesday, and Thursday this week, and he suggested a couple of directions and ideas. We are still on the hunt for a plan of attack, so our main concentration is in reading papers. We have grown noticeably more adept with the material so far.

Week 4:

This week we turned our focus towards "Gap" MCSP, which is an approximation problem to MCSP. In a sense, by weakening the problem, we are hoping to find better impossibility results. And for a quick moment, we thought we succeeding -- in fact we did succeed. Sort of. We found an approach that worked, but at the end of the week we realized it was a result that was already proven. Not only was it already proved, but a much stronger version was already proved. However, the techinques we used to prove this were very different from theirs, so there is still some hope that our result could be interesting.

Week 5:

It turned out that, with just a little tweak, our result from last week could be improved into a very strong result. Neekon and I were ecstatic because this is our first real result. We then set to the task of properly writing it up and showing it Professor Allender. Along the way, we were able to find an even stronger improvement. We also explored several other avenues relating to the "Gap" problem. In particular, one of the papers we were reading has several results that could be extend, which we are exploring.

Week 6:

This week we had thought we found a very powerful way to extend our results. This lead to several very strong results about the non-hardness of MCSP. Unfortunately, near the end of the week, we found a bug in our proofs that invalidated several of our results. Luckily, our first result from last week is still valid. It was somewhat demoralizing. At the end of the week though, we did figure out a hardness of result that help advance our understanding of the problem.

Week 7:

This weekend I was able to find new way to salvedge some of our results from last week. We are pretty happy with it. It is actually a fairly clever proof, and it has some strong consequences. Most of this week was spent writing things up. We had our presentation on Thursday, which we worked on Tuesday and Wednesday. We think our presentation went fairly well. We got a lot of positive feedback. After that we started working on writing up our results for the final paper we have to submit to DIMACS. This is good because Allender thinks our results are publishable, and this should act as a good first draft.

---

Presentations

---

Additional Information

• My Mentors
  • Eric Allender