CS Events

PhD Defense

Meta Complexity - Connections to One-way functions and Zero Knowledge protocols

 

Download as iCal file

Thursday, August 31, 2023, 01:00pm - 03:00pm

 

Abstract : The main theme of this thesis is the study of some connections between Meta Complexity problems and important complexity/ cryptographic objects such as One way functions (OWFs) and Zero knowledge protocols.  1. Meta-complexity and OWFs -  We present an NP-complete problem called Minimum Conditional Kolmogorov Time problem (McKTP) and provide an almost equivalence between the average case hardness of McKTP and the existence of OWFs. 2. Characterizations for SZK and NISZK - We present characterizations for Statistical Zero Knowledge (SZK) and its non-interactive variant (NISZK). We show that these classes correspond precisely to the set of promise problems that are randomly reducible to the set of Kolmogorov random strings.  3. Robustness for space bounded Zero knowledge protocols - We show that the space bounded zero knowledge classes (SZK, NISZK) are surprisingly robust to changing the power of the verifier and the simulator. 

 

Speaker: Harsha Srimath Tirumala

Location : CoRE 305 and Zoom

Committee

Professor Eric Allender (Chair)

Professor Mike Saks

Professor Sepehr Assadi

Professor Valentine Kabinets (Simon Fraser University)

 

Event Type: PhD Defense

Abstract: See above

Organization

Rutgers University

School of Arts & Sciences

Department of Computer Science

 

Contact  Professor Eric Allender

Meeting link :
https://rutgers.zoom.us/j/3776129695?pwd=RGlhUkcxOG5XOUhDYVdINks5eFVrZz09

Meeting ID: 377 612 9695
Password: 822973