Department of Computer Science
Zero Knowledge and Circuit Minimization
- Publication Type: Conference Publications
- Publication Date: 2014-08-01
- Conference Location: Milan
- Link to Content 1: Zero Knowledge and Circuit Minimization
- Abstract:
We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RPMCSP.This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these problems share, as candidate NP-intermediate problems.
We are committed to fostering a safe environment while upholding the principles of academic freedom and free expression of our community.
We're Hiring
Undergraduate
Graduate
Research
Upcoming Events
| 06 May 2026; - 03:30PM - 04:30PM Towards Universal and Interactive Medical Image Segmentation |
| 12 May 2026; - 02:30PM - 04:30PM Enhancing Consistency Models for Multi-Agent Trajectory Prediction |
| 15 May 2026; - 01:00PM - 03:00PM Towards Compliant Human Trajectory Prediction: From Environment-Aware Generation to Multi-Agent Joint Alignment |
