Oded Goldreich, Muli Safra

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))

is very complicated.

One source of difficulty is the technically involved

analysis of low-degree tests.

Here, we refer to the difficulty of obtaining strong results

regarding low-degree tests; namely, results of the type obtained and

used by ...
more >>>

Bernd Borchert, Dietrich Kuske, Frank Stephan

Pin & Weil [PW95] characterized the automata of existentially

first-order definable languages. We will use this result for the following

characterization of the complexity class NP. Assume that the

Polynomial-Time Hierarchy does not collapse. Then a regular language

L characterizes NP as an unbalanced polynomial-time leaf language

if and ...
more >>>

Mihir Bellare, Oded Goldreich, Erez Petrank

A Uniform Generation procedure for $NP$ is an

algorithm which given any input in a fixed NP-language, outputs a uniformly

distributed NP-witness for membership of the input in the language.

We present a Uniform Generation procedure for $NP$ that runs in probabilistic

polynomial-time with an NP-oracle. This improves upon ...
more >>>

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

This paper strengthens the low-error PCP characterization of NP, coming

closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for

membership in any NP language can be verified with a constant

number of accesses, and with an error probability exponentially

small in the ...
more >>>

Oded Goldreich, Luca Trevisan

Property testing is a relaxation of decision problems

in which it is required to distinguish {\sc yes}-instances

(i.e., objects having a predetermined property) from instances

that are far from any {\sc yes}-instance.

We presents three theorems regarding testing graph

properties in the adjacency matrix representation. ...
more >>>

Pavel Pudlak

We consider some problems about pairs of disjoint $NP$ sets.

The theory of these sets with a natural concept of reducibility

is, on the one hand, closely related to the theory of proof

systems for propositional calculus, and, on the other, it

resembles the theory of NP completeness. Furthermore, such

more >>>

Oded Goldreich

The notion of promise problems was introduced and initially studied

by Even, Selman and Yacobi

(Information and Control, Vol.~61, pages 159-173, 1984).

In this article we survey some of the applications that this

notion has found in the twenty years that elapsed.

These include the notion ...
more >>>

Oded Goldreich

We highlight a common theme in four relatively recent works

that establish remarkable results by an iterative approach.

Starting from a trivial construct,

each of these works applies an ingeniously designed

sequence of iterations that yields the desired result,

which is highly non-trivial. Furthermore, in each iteration,

more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>

<ul>

<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>

<li>1-tt-reducibility and m-reducibility differ on NP.</li>

<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ...
more >>>

Parikshit Gopalan, Venkatesan Guruswami

We study the average-case hardness of the class NP against

deterministic polynomial time algorithms. We prove that there exists

some constant $\mu > 0$ such that if there is some language in NP

for which no deterministic polynomial time algorithm can decide L

correctly on a $1- (log n)^{-\mu}$ fraction ...
more >>>

Cristopher Moore, Alexander Russell

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

Agrawal Manindra, Osamu Watanabe

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.

It states that all sets complete for NP under polynomial-time many-one

reductions are P-isomorphic to each other. From previous research

it has been widely believed that all NP-complete sets are reducible

each other by one-to-one and length-increasing polynomial-time

reductions, but ...
more >>>

Dmitry Gavinsky, Alexander A. Sherstov

We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic

complexity $O(\log n)$ and Merlin-Arthur

complexity $n^{\Omega(1)}$.

The problem was open for $k\geq3$.

Abuzer Yakaryilmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on space-bounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems ... more >>>

Yijia Chen, Joerg Flum

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

Christian Glaßer, Maximilian Witek

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:

- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.

- For P, the delta-levels of ...
more >>>

Leroy Chew

Quantified Boolean Formulas (QBFs) extend propositional formulas with Boolean quantifiers. Working with QBF differs from propositional logic in its quantifier handling, but as propositional satisfiability (SAT) is a subproblem of QBF, all SAT hardness in solving and proof complexity transfers to QBF. This makes it difficult to analyse efforts dealing ... more >>>