Name
Abstract | ||
|---|---|---|
We explore the connection between public-coin interactive proof systems with logspace verifiers and
NC\mathcal{N}\mathcal{C}using two different approaches. In the first approach, we describe an interactive proof system for accepting any language in
NC\mathcal{N}\mathcal{C}after a logspace reduction, where the verifier is logspace-bounded and the protocol requires polylog time. These results are proved by describing
NC\mathcal{N}\mathcal{C}computations as computations over arithmetic circuits using maximum and average gates, and then translating the arithmetic circuits into interactive proof systems in a natural way. In the second approach, we give a characterization of
NC\mathcal{N}\mathcal{C}in terms of interactive proof systems where the verifier is logspace-bounded and runs in polylog time. The equivalent interactive proof systems work with error-correcting encodings of inputs, using the polylogarithmically checkable codes introduced in the context of transparent proofs. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/BFb0015408 | ISAAC |
Keywords | Field | DocType |
logspace verifiers,error correction | Discrete mathematics,Arithmetic circuits,Combinatorics,Interactive proof system,Mathematical proof,Mathematics,Computation | Conference |
ISBN | Citations | PageRank |
3-540-60573-8 | 0 | 0.34 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Satyanarayana V. Lokam | 1 | 274 | 22.36 |
| Meena Mahajan | 2 | 688 | 56.90 |
| V. Vinay | 3 | 48 | 6.38 |