Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly ODED GOLDREICH and OR MEIR, Weizmann Institute of Science An input-oblivious proof system is a proof system in which the proof does not depend on the claim being proved. Input-oblivious versions of N P and MA were introduced in passing by Fortnow, Santhanam, and Williams, who also showed that those classes are related to questions on circuit complexity. In this article, we wish to highlight the notion of input-oblivious proof systems and initiate a more systematic study of them. We begin by describing in detail the results of Fortnow et al. and discussing their connection to circuit complexity. We then extend the study to input-oblivious versions of I P, PCP, and Z K, and present few preliminary results regarding those versions. Categories and Subject Descriptors: F.1.2 [Theory of Computation]: Computation by Abstract Devices-- Modes of computation General Terms: Theory Additional Key Words and Phrases: BPP, EXP, IP, MA, NE, NEXP, NP, PCP, P/poly, RP, E, ZK ACM Reference Format: Oded Goldreich and Or Meir. 2015. Input-oblivious proof systems and a uniform complexity perspective on P/poly. ACM Trans. Comput. Theory 7, 4, Article 16 (August 2015), 13 pages. DOI: http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Download PDF
13 pages

Loading next page...
 
/lp/association-for-computing-machinery/input-oblivious-proof-systems-and-a-uniform-complexity-perspective-on-MPdiALtnK4
Publisher
Association for Computing Machinery
Copyright
Copyright © 2015 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/2799645
Publisher site
See Article on Publisher Site

Abstract

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly ODED GOLDREICH and OR MEIR, Weizmann Institute of Science An input-oblivious proof system is a proof system in which the proof does not depend on the claim being proved. Input-oblivious versions of N P and MA were introduced in passing by Fortnow, Santhanam, and Williams, who also showed that those classes are related to questions on circuit complexity. In this article, we wish to highlight the notion of input-oblivious proof systems and initiate a more systematic study of them. We begin by describing in detail the results of Fortnow et al. and discussing their connection to circuit complexity. We then extend the study to input-oblivious versions of I P, PCP, and Z K, and present few preliminary results regarding those versions. Categories and Subject Descriptors: F.1.2 [Theory of Computation]: Computation by Abstract Devices-- Modes of computation General Terms: Theory Additional Key Words and Phrases: BPP, EXP, IP, MA, NE, NEXP, NP, PCP, P/poly, RP, E, ZK ACM Reference Format: Oded Goldreich and Or Meir. 2015. Input-oblivious proof systems and a uniform complexity perspective on P/poly. ACM Trans. Comput. Theory 7, 4, Article 16 (August 2015), 13 pages. DOI:

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Aug 31, 2015

There are no references for this article.