Student: | John Gouwar |
---|---|

School: | Grinnell College |

E-mail: | gouwarjo(at)grinnell(dot)edu |

Project: | The Minimum Circuit Size Problem: A Potential NP-Intermediate Problem |

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.

- 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.

- My Mentor: Dr. Eric Allender
- My Research Partner: Caleb Robelle

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