General Information

---

Project Description

Consider the following problem known as the Minimum Circuit Size Problem (MCSP). Given a boolean function f:{0,1}^n -> {0,1} and a natural number s, can f be implemented by a circuit of size less than or equal to s? MCSP is known to be in NP but whether or not it is NP-complete is unclear. One can think of MCSP as measuring the complexity of describing a particular bitstring as a circuit. When viewed through this lense, MCSP is very similar to another problem known as the Minimum Time Bounded Kolmogorov Complexity (MKTP). This problem asks the following question: given a string x, find a Turing machine M that whose output is x such that |d|+t is minimized where d is the representation of M as a bit-string and t is the number of steps M takes to output x. We will try and show that MKTP is hard for NISZK_L under NC^0 many-one reductions.

---

Weekly Log

Week 1:

I started the week by looking at some papers on MCSP and related problems that were sent to my by Dr. Allender. This was my first time encountering topics in circuit complexity such as the AC, NC and TC hierarchies so I spent a bit of time familiarizing my self with them. My project partner (John Gouwar) and I attended an online talk given by previous DIMACS REU student Rahul Ilango on the multi-output MCSP. John and I met with Dr. Allender twice this week to ask any questions we had about topics we encountered in our reading. After our meetiing on Wednesday we started working on our initial project presentation which we will give to the group either this coming Monday or Tuesday.

Week 2:

On Monday John and I gave an introductory presentation on our project to the rest of the REU participants. The rest of the week was once again spent reading papers. In particular, I looked at papers having to do with the complexity classes SZK and NISZK. I learned quite a bit about showing completeness for problems in these classes which was helpful as our ultimate goal is a hardness result for a subclass of SZK. While looking at one of the papers I started to think about coming up with a proof to show that Entropy Approximation for NC^0 circuits (EA_NC^0) is in NISZK_L. This is one of the first steps in our project. Next week I plan to finish this proof and also show that EA_NC^0 is complete for NISZK_L under NC^0 many one reductions.

Week 3:

This week I started trying to prove completeness of EA_NC^0 for NISZK_L under AC^0 reductions. The first step was to show that it was in NISZK_L. I did this by following the work of [GSV99] who showed that EA for general distributions is complete for SZK. I then started trying to adapt their proof of completeness to prove my desired result. They establish completeness of EA by first showing that the problem Statistical Difference from Uniform (SDU) reduces to EA then by showing that SDU is complete for SZK. I was able to show that their reduction from SDU to EA worked when I restricted the distrubutions to those generated by NC^0 circuits. Unfortunately the proof of completeness for this restricted version of SDU proved to be more difficult so I haven't been able to complete it.

Week 4:

This week I continued to try and prove completeness of SDU for NC^0 circuits for NISZK_L under AC^0 reductions. When trying to adapt the proof from [GSV99] I ran into a problem. Since I was trying to show that any promise problem in NISZK_L reduced to SDU for only NC^0 circuits, I couldn't quite use the proof they gave since they were working with general distibutions. However, since the promise problems I was considering are in NISZK_L, they have simulators which are logspace computable. With (lots of) help from Dr. Allender I was able to show that I could construct an NC^0 circuit C which was a perfect randomized encoding of the simulator using a construction from [AIK06]. Then I could compare C to the uniform distribution as part of SDU. Unfortunately this is where things broke down for me. I don't quite know what I can say about the statistical distance from uniform of C.

Week 5:

This week I was able to finish prooving completeness of EA_NC^0 for NISZK_L under AC^0 reductions. It took me a little while to put it together since I had to combine techniques from different papers in the final proof. Now that we have completenes of EA_NC^0, once we can show that EA_NC^0 reduces to MKTP, we will have our desired result which is hardness of MKTP for NISZKL under AC^0 reductions (which actually gives us hardness under NC^0 reductions for free!).

Week 6:

Dr. Allender pointed out a unique property of the transformation we apply to construct perfect randomized encodings. It actually produces a specific kind of circuit known as a projection. IF we can show completeness under projections that would be a more powerfull result than completeness under NC^0 reductions. I'll try and show that we have completeness under projections over the next week.

Week 7:

After reading through an old paper of Dr. Allender's we have succesfully shown that MKTP is hard for NISZK_L under projections. This is a really restrictive kind of reduction which is a pretty neat result.

Week 8:

This week I started working on the final report and presentation. I've finished my proofs and I'm working on making them a bit neater for the report.

Week 9:

This week John and I gave our final presentation and submitted our final report on our project. It turns out the we actually proved hardness of MKTP for the complement of NISZK_L but Dr. Allender thinks we can still prove hardness for NISZK_L.

---

Presentations

Presentation 1

Final Presentation

---

Additional Information

• My Mentors
  • Eric Allender