DIMACS
DIMACS REU 2020

General Information

me
Student: John Gouwar
School: Grinnell College
E-mail: gouwarjo(at)grinnell(dot)edu
Project: The Minimum Circuit Size Problem: A Potential 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 was mostly spent getting up to speed on the nature of MCSP, and its related problem, MKTP. This involved reading papers relating MCSP/MKTP to other poetial NP-Intermediate problems, especially the Graph Isomorphism problem, and reading papers proving hardness results (or lack thereof) for MCSP/MKTP. These papers also served as jumping off points for understanding where there were gaps in my knowledge, and for researching complexity classes that I had not learned about in my theory of computation course. We, that is Caleb, Dr. Allender, and I, also discussed what our goals for this summer would be. Also, I watched a seminar on a variant of MCSP given by Rahul Ilango. This seminar provided a both a good history and a good conceptual background on the state of the problem. Finally, Caleb and I worked on our initial presentation to the rest of the REU students about our project.
Week 2:
First, Caleb and I presented an introductory presentation about circuit complexity, MCSP, and hardness. Then, following up on the introductory reading from last week, I spent this week working through the more minute details of the reductions the papers presented for similar problems to gain inspiration for solving our own problems and generating our own reductions. I also spent more time getting aquainted with the complexity class that Caleb and I will be working to prove hardness results for, NISZK (Non-interactive statistical zero knowledge). There appears to be a connection between the relative hardness of a known complete problem for NISZK and MKTP. Working though the papers is certainly getting easier as I become more acquainted with the field, and being able to talk through the ideas and details of the papers with Caleb and Dr. Allender has been incredibly helpful. Finally, Caleb, Dr. Allender, and I met on Friday to discuss the path working through our first reduction and hardness result.
Week 3:
I spent this week building off of a future steps section of one of Dr. Allender's old papers work on isomorphism problems by reducing a known hard problem for NISZK to MKTP. This mostly involved me working through the reductions and lemmas in that paper and seeing from which techniques I could borrow, modify, or gain inspiration. Given that MKTP can be understood as a problem about the potential randomness of a string, the reduction itself also needed to be randomized. With some gentle prodding from Dr. Allender, I was able to complete the reduction (modulo some pesky constants, which is my first goal for next week). This summer is my first experience with probablistic computation, and thus I had never done a randomized reduction before. I consider this reduction my first major accomplishment of the summer, and hope to solve the pesky constant problem next week.
Week 4:
The constants from last week stemmed from a claim that was made without proof in the future steps portion of the paper I mentioned last week. Therefore, I spent this week working on a formal proof of that claim. With some helpful words from Dr. Allender's collaborators on the paper, I was able to prove it for an arbitrary bound on the size of the error; however, if this bound is too small, I will not be able to effectively use it in my reduction at all, and if it is too large then it will introduce too much uncertainty into my reduction. Yet, once I figure out these bounds, I will have all of the tools necessary to prove my first substantial hardness result for the summer. Therefore, my goals for next week are to establish those bounds and make another attempt at the reduction. I will also be attending the remote Symposium on Theory of Computing next week.
Week 5:
This week I attended the online Symposium on Theory of Computing. I went to talks on topics ranging from Cryptography, to Complexity Theory, to Graph Theory, and Quantum Computing. This conference certainly opened my eyes to what is going on at the forefront of world of theoretical computer science. There was even a workshop on MCSP that Dr. Allender spoke at. As for my research, I worked to establish the bounds I wrote about last week. Therefore, I believe that I have compeletely proven my first substantial hardness result about MKTP for the summer. Dr. Allender's ultimate goal for the summer was for Caleb and I to link our two results into a hardness result for MKTP under a very restrictive class of reductions. Thus, Caleb and I met at the end of the week to see what it would take to link our results, and we surmised that it would not be too hard. Therefore, we will most likely spend the majority of next week working to combine our individual results.
Week 6:
We found a few errors in my reduction from last week, so I spent most of the week working through the blocks that lead to those errors. Dr. Allender, Caleb, and I also discussed what it would take to make our reductions even more restrictive. From what we could surmise, it seems that our reductions ended up being more restrictive than we were intending to begin with, so we would simply need to elucidate why our reduction was appropritately restrictive to get a stronger result. My latest reduction had another more structural error that we did not catch until the end of this week, but Dr. Allender and I discussed how to fix the error by defining our own restricted view of an encoding. My work next week will focus on finalizing this definition and applying to my reduction.
Week 7:
Incorporating the new definition into my reduction turned out to be much trickier than I originally anticipated. Thus, I ended up having to rework the entire approach I was taking to the proof. I have made a fair amount of progress with this approach, but I still have a few issues that I have to work out regarding the error in the reduction. I attended three seminars this week, including an incredibly informative graduate school panel.
Week 8:
I mostly spent this week getting everything in order for the final paper and presentation. The only thing left on my reduction is tightening up the error probabilities, we know that they are correct from some quick calculations, but formalizing the ideas behind the calculations has turned out to be trickier than we originally thought. I never expected content from Real Analysis about how fast (1-1/n)^n converges would be useful afterwards, but boy was I mistaken. The paper is coming along nicely and Caleb and I are definitely ready to present our result, we think it's pretty interesting.

Presentations

Additional Information

Acknowledgements

This research is done through the DIMACS REU with support from Rutgers University and funding through NSF Grant CCF-1836666.