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.
Acknowledgements:
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!