Zero knowledge and circuit minimization

被引：20

作者：

Allender, Eric ^{[1
]}

Das, Bireswar ^{[2
]}

机构：

[1] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08854 USA

[2] IIT Gandhinagar, Ahmadabad, Gujarat, India

来源：

INFORMATION AND COMPUTATION | 2017年 / 256卷

关键词：

Graph Isomorphism; Minimum Circuit Size Problem; NP-intermediate problem; Statistical Zero Knowledge; PROOF SYSTEMS; COMPLEXITY; LANGUAGES; NP;

D O I：

10.1016/j.ic.2017.04.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. DThis 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. (C) 2017 Elsevier Inc. All rights reserved.

引用

页码：2 / 8

页数：7

共 30 条

[21] Kobler Johannes, 1993, GRAPH ISOMORPHISM PR
[22] Krajiek Jan., 2011, FORCING RANDOM VARIA
[23] Levin L., 2003, COMMUNICATION
[24] Levin L. A., 1973, Problems of Information Transmission, V9, P265
[25] Natural proofs
Razborov, AA
Rudich, S
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 55 (01) : 24 - 35
[26] IP = PSPACE
SHAMIR, A
[J]. JOURNAL OF THE ACM, 1992, 39 (04) : 869 - 877
[27] TRAKHTENBROT BA, 1984, IEEE ANN HIST COMPUT, V6, P384
[28] Vadhan Salil, 2017, STUDY STAT ZERO KNOW
[29] Vadhan Salil P., 2008, LECT NOTES COMPUT SC, V4948, P501
[30] VARIYAM VN, 2005, INT J FOUND COMPUT S, V16, P1297

← 1 2 3 →