Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #5 to TR11-023 | 13th April 2015 17:30

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

RSS-Feed




Revision #5
Authors: Oded Goldreich, Or Meir
Accepted on: 13th April 2015 17:30
Downloads: 365
Keywords: 


Abstract:

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.
Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the conjecture $NP\not\subset P/poly$ and a uniform complexity
characterization of the class $IP\cap P/poly$.
These (and similar) results offer a perspective on the attempt
to prove circuit lower bounds for complexity classes such as NP, PSPACE, EXP, and NEXP.


Revision #4 to TR11-023 | 7th April 2014 20:13

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





Revision #4
Authors: Oded Goldreich, Or Meir
Accepted on: 7th April 2014 20:13
Downloads: 519
Keywords: 


Abstract:

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 $\NP$ and $\MA$ were introduced in passing by Fortnow, Santhanam, and Williams (CCC 2009), who also showed that those classes are related to questions on circuit complexity.

In this paper 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 $\mathcal{IP}$, $\mathcal{PCP}$, and $\mathcal{ZK}$, and present few preliminary results regarding those versions.


Revision #3 to TR11-023 | 5th April 2014 02:20

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





Revision #3
Authors: Oded Goldreich, Or Meir
Accepted on: 5th April 2014 02:20
Downloads: 317
Keywords: 


Abstract:

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.
Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the conjecture $NP\not\subset P/poly$ and a uniform complexity
characterization of the class $IP\cap P/poly$.
These (and similar) results offer a perspective on the attempt
to prove circuit lower bounds for complexity classes such as NP, PSPACE, EXP, and NEXP.


Revision #2 to TR11-023 | 24th February 2011 18:08

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





Revision #2
Authors: Oded Goldreich, Or Meir
Accepted on: 24th February 2011 18:08
Downloads: 1176
Keywords: 


Abstract:

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 NP and MA were introduced in passing
by Fortnow, Santhanam, and Williams (CCC 2009), who also showed
that those classes are related to questions on circuit complexity.

In this note 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 IP, PCP,
and ZK, and present few preliminary results regarding those versions.



Changes to previous version:

As pointed out by Thilo Mie, Definition 4.1 (OPCP) is correct so as
to explicitly upperbound the proof length (by a polynomial).


Revision #1 to TR11-023 | 23rd February 2011 14:35

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





Revision #1
Authors: Oded Goldreich, Or Meir
Accepted on: 23rd February 2011 14:35
Downloads: 1006
Keywords: 


Abstract:

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 NP and MA were introduced in passing
by Fortnow, Santhanam, and Williams (CCC 2009), who also showed
that those classes are related to questions on circuit complexity.
Their definition followed a work of Chakaravarthy and Roy (STACS 2006),
who defined an input-oblivious version of ${\cal S}_2$.

In this note 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 \etal,
and discussing their connection to circuit complexity.
We then extend the study to input-oblivious versions of IP, PCP,
and ZK, and present few preliminary results regarding those versions.



Changes to previous version:

The paper was revised in light of the comment posted on Feb 16.


Paper:

TR11-023 | 16th February 2011 16:15

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





TR11-023
Authors: Oded Goldreich, Or Meir
Publication: 16th February 2011 16:16
Downloads: 1257
Keywords: 


Abstract:

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.
Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the conjecture $NP\not\subset P/poly$ and a uniform complexity
characterization of the class $IP\cap P/poly$.
These (and similar) results offer a perspective on the attempt
to prove circuit lower bounds for complexity classes such as NP, PSPACE, EXP, and NEXP.


Comment(s):

Comment #1 to TR11-023 | 16th February 2011 18:24

The classes ONP and OMA were defined and studied before by FSW

Authors: Oded Goldreich
Accepted on: 16th February 2011 18:24
Keywords: 


Comment:

Andy Drucker has just brought to our attention that the classes ONP
and OMA were defined and studied in the prior work of Lance Fortnow,
Rahul Santhanam, and Ryan Williams "Fixed-Polynomial Size Circuit Bounds"
(IEEE Conference on Computational Complexity, pages 19-26, 2009).
Their paper contains many of our observations, most importantly
the main part of our Thm 1.1 appears in Sec II.B.
Our paper also defines input-oblivious versions (of IP, PCP and ZK) that were not considered in the prior work of Fortnow, Santhanam, and Williams, and contains several observations not made there.


Comment #2 to TR11-023 | 7th April 2014 09:00

Revision 3 is a wrong one

Authors: Oded Goldreich
Accepted on: 7th April 2014 09:00
Keywords: 


Comment:

Please ignore this revision (as well as the old abstract) for the time being. The correct revision will be posted shortly; it is a slight improvement over the 2nd revision.




ISSN 1433-8092 | Imprint