General Information

Student: Michael Rudow
Office: CORE 450
School: University of Pennsylvania
E-mail: mhrudow@gmail.com
Project: The Minimum Circuit Size Problem: A Possible NP-Intermediate Problem

Project Description

The Minimum Circuit Size Problem has been studied for several decades. It is suspected that this problem is NP-Intermediate, although there is no known proof of this fact. The goal of this REU is to explore the computational power of a MCSP oracle. In doing so, its relation to other possibly NP-Intermediate problems might become more clear.

Weekly Log

Week 1:
My first week was spent familiarizing myself with the requisite information for the MCSP. This included completing background reading suggested by Professor Allender, exploring some of the open problems he recommended, and collaborating with the group of students from Charles University on some of the problems. Along with the Czech Group, I focused on the computational power available using P/poly and an oracle to the MCSP. I also considered how to determine if Graph Automorphism is solvable with no error in polynomial expected time with an oracle to MCSP. Overall, my goal for the week was to create a strong foundation on the necessary information before I begin narrowing the scope of my focus next week.
Week 2:
I spent this week exploring the background of Graph Isomorphism (GI) and Graph Automorphism (GA). In doing so, I am focusing specifically on trying to prove that Graph Automorphism is solvable in polynomial expected time with an oracle to MCSP. My approach involves modifying Professor Allender's proof that Graph Autmorphism is solvable in polynomial expected time with an oracle to MKTP. His technique involves using a gap in Kolmogorov complexity between graphs with and without a nontrivial graph isomorphism. Through using expander graphs, I hope to expand this gap; in doing so, perhaps the gap will be sufficiently large to extend Professor Allender's proof to using an oracle to the MCSP.
Week 3:
Finally a result! While doing background reading, I discovered the fact that the discrete log problem is known to be in BPP^MCSP. I spent this week trying to improve this bound, and I succeeded in showing that the discrete log problem is in ZPP^MCSP!
Week 4:
I spent my time working on three different areas this week. I have been writing a paper for my result from last week. I have also spent some time collaborating on another problem with the students from the Czech Republic. Finally, I have been thinking about how to use an MCSP oracle to break various cryptosystems. Specifically, I have attempted to apply a construction that Professor Allender has used to prove some results toward breaking the McEliece cryptosystem given an oracle to MCSP.
Week 5:
I encountered some obstacles to the attempt at breaking the McEliece cryptosytem this week. I spent some time exploring options to overcome these obstacles and considering if perhaps instead the cryptosystem is provably as secure against an oracle to MCSP as it is without such an oracle.
Week 6:
I followed through with my attempts to break the McEliece cryptosystem and determined that doing so in that manner would be NP-Hard. I then explored the Linear Divisibility problem given an MCSP oracle. We also had a field trip to IBM where we had the opportunity to listen to several great speakers.
Week 7:
This week I finished a paper and submitted it for publication! I also prepared and presented a presentation with Karel and Veronika for our work so far this summer. I also spent more time exploring the Linear Divisibility Problem.
Week 8:
I am excited to be posting this weekly update from Prague! This week has been a fantastic experience and next week will be even more amazing. We have attended several lectures on combinatorics from various Professors at Charles University. Specifically, we learned about interval graphs and their relationship with Hamiltonian cycles, an algorithm for a constant approximation for largest independent sets of planar graphs, deletion contraction recurrences and their uses with combinatorial reciprocity, and the spectacular properties of random graphs. In our spare time, we have experienced Czech culture and explored Prague and the surrounding area.
Week 9:
This week I had the opportunity to attend my first international conference! It has been a great experience listening to so many fantastic speakers. We also continued to explore the wonders of Prague; one of my favorite parts of my time here in Prague was visiting Charles Bridge and Prague Castle at night. Overall, this REU with DIMACS has been an awesome experience.

Additional Information