General Information
| Student: | Azucena Garvia |
|---|---|
| Office: | CoRE 442 |
| School: | University of Edinburgh |
| E-mail: | s1608700@sms.ed.ac.uk |
| Project: | The Minimum Circuit Size Problem: A possible NP-intermediate problem |
Project Description
The Minimum Circuit Size Problem (MCSP) is a problem in complexity theory which is thought to be NP-intermediate: it is in NP and it is neither believed to be in P nor to be NP-complete. This is important since existence of an NP-intermediate problem would imply that P is not equal to NP. The goal of this research is to prove results regarding the non-hardness of MCSP.
Weekly Log
- Week 1:
- This first week I met my research partner Amulya and we talked to our mentor Professor Allender who gave us a few papers to read in order to gain some background knowledge on the problem. We concentrated on understanding the main idea of the papers and we tried to gain intuition on how the results were obtained. However, this turned out to be very hard since we were both new to the problem. In addition, we worked creating the slides for a short presentation that we will give next week explaining our project to the rest of the REU.
- Week 2:
- Most of the week was spent reading more research papers; we've noticed that we've gotten a lot more comfortable with the material. At the end of the week, we started working on our first problem: a reduction that Professor Allender wants us to make more simple. We met with him on Friday to show him our ideas and ask him some questions. This was our last meeting before he left to go to a conference in Russia. We will see him next at the end of the month and in the meantime we'll communicate by email.
- Week 3:
- Professor Allender gave us another reduction to work on this week. Both of the reductions have to do with MKPT, this is a problem dealing with Kolmogorov complexity which is related to MCSP. We worked on these two problems all week, familiarizing ourselves with the MKTP problem and reading relevant research papers. By the end of the week we wrote up our solutions and sent them to Professor Allender. In addition, on Wednesday we had our first Bridge Workshop, on the Hadamard maximum determinant problem.
- Week 4:
- On Monday we visited Nokia Bell Labs; we listened to talks from some of the researchers on their work and then we got to go into the anechoic chamber, which held the record for worlds quietest room for some decades. We spent the rest of the week exploring different problems, since Professor Allender gave us positive feedback on both the reductions we sent him. Finally, by the end of the week we decided which problem we're going to focus on; this time it is not a reduction between two languages, but rather proving that such a reduction cannot exist.
- Week 5:
- This week we kept thinking about the problem that Professor Allender proposed to us last week of disproving a possible reduction via projections. We came up with a couple of things that we thought could lead to contradictions but when we spoke to Professor Allender he made us see that projections are more powerful than we thought and he pointed us in a better direction. In addition, he said that one of our reductions from last week was an interesting result and he's asked us to write it up!
- Week 6:
- Professor Allender gave us a few papers to read that disprove certain reductions, in order to give us insight on possible contradictions that we could find with our projection. He has also given us a new problem to think about which relates entropy with Kolmogorov complexity, so we spent some time familiarizing ourselves with the subject and reading some related papers. We've also started to draft our technical write up.
- Week 7:
- This week we thought that we had found a way to disprove the reduction we were working on, but when we spoke to Professor Allender we realized there was a mistake in our reasoning. We will continue to think about that problem but he also gave us something else to work on; this new problem is to turn a specific truth table reduction into a many one reduction. We started out by reading relevant research papers and trying to simplify their approach but this turned out to be harder than we thought so at the end of the week we worked on coming up with a new strategy for this reduction.
- Week 8:
- The Computational Complexity Conference was at Rutgers this year and we were lucky enough to attend. The first couple of days we went to introductory talks and workshops and at the end of the week we saw the conference lectures. It was a really valuable experience to meet and talk to researchers whose papers we had read and used in our work. This week we also finished writing up our results and sent our first draft to Professor Allender.
- Week 9:
- We arrived in Prague on Sunday morning. There are lectures organized for us this week but there is also a Topology workshop going on that we will attend. Next week is the Midsummer Combinatorial Workshop.
Additional Information
- My Mentor
- My Research Partner