Pengxiang Wang' REU 2022 Web Page

About Me:

Name: Pengxiang Wang
Home Institution: University of Michigan
Email Address: tcs "dot" wang "at" yahoo.com
Project: Metacomplexity and Non-interactive Zero Knowledge Proofs
Mentor: Professor Eric Allender

About My Project:

I will investigate various metacomplexity classes and see how they relate to ordinary complexity classes.

Research Log

Week 1:

I moved into Rutgers Silvers Apartment with other DIMACS REU students. I met many other ambitious students. I met with Professor Allender and discus several problems that interests me.

Week 2:

Earlier in the week I worked on various problems (not the main one Professor Allender intended) that interests me, I was able to get some good insights but shifted away to the main problem (which is relating NISZKL with other variants of NISZK).

Week 3:

I am able to make a lot of progress on the bridging NISZKNL and NISZKL.

Week 4:

The Approach we had didn't work because there was a misunderstanding of the protocol that we are working with. We are trying to fix it up.

Week 5:

Professor Allender proposed a new approach to perform the encoding and it seems to do a better job.

Week 6:

I was able to show the appropriate upper and lower bound in order to show that NISZKNL=NISZKL. Professor Allender also suggested me to look into the case of PM (problems logspace reducible to Perfect Matching) instead of NL. It turns out to be quite trivial because a encoding similar to that of NL exists for PM as well

Week 7:

We started looking at other classes that might be in SREN (set of complexity class with statistically randomized encoding in NC0) such as Lco-C=L ∩ C=L, PM, and pModL. We also started to look into the closure properties (under turing/ctt/dtt) of classes such as SREN, SZKL and NISZKL.

Week 8:

This was a hepatic week, my teammates and I had to compile the slides for presentation and I need to get ready for the Prague trip. I did my final presentation on Thursday and left US for Czech Republic on Friday.

Week 9:

We attended CSGT 2022 in Prague, this is the first time that I attend a conference and I was super excited! I met a lot of new people and learn about different aspects of Graph Theory (which I have a limited knowledge of). I was surprised to see with a former DIMACS REU participants presenting in this conference too!

Week 10:

We attended a few seminars at Charles University.

Post Program:

Manuscript for our paper: Robustness for Space-Bounded Statistical Zero Knowledge.


This project has been made possible by NSF grants CNS-215018 and CCF-1852215. I would also especially like to thank Lazaros Gallos, Larry Frolov, and Jan Soukup who coordinate this program. I would like to thank Professor Allender's PhD student Harsha Tirumala for his help throughout the program. I would like to thank my partners Jacob Gray and Saachi Mutreja for their support. Finally I would like to express my utmost gratitude to Professor Allender for his mentorship, I have learn so much from him this summer!