Sanjeev Khanna, Madhu Sudan

In 1978, Schaefer considered a subclass of languages in

NP and proved a ``dichotomy theorem'' for this class. The subclass

considered were problems expressible as ``constraint satisfaction

problems'', and the ``dichotomy theorem'' showed that every language in

this class is either in P, or is NP-hard. This result is in ...
more >>>

Harald Hempel, Gerd Wechsung

We define a general maximization operator max and a general minimization

operator min for complexity classes and study the inclusion structure of

the classes max.P, max.NP, max.coNP, min.P, min.NP, and min.coNP.

It turns out that Krentel's class OptP fits naturally into this frame-

work (it can be ...
more >>>

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

We show that every language in NP has a probablistic verifier

that checks membership proofs for it using

logarithmic number of random bits and by examining a

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Steffen Reith, Heribert Vollmer

We consider the problems of finding the lexicographically

minimal (or maximal) satisfying assignment of propositional

formulae for different restricted formula classes. It turns

out that for each class from our framework, the above problem

is either polynomial time solvable or complete for ...
more >>>

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

It is known that there exists a PCP characterization of NP

where the verifier makes 3 queries and has a {\em one-sided}

error that is bounded away from 1; and also that 2 queries

do not suffice for such a characterization. Thus PCPs with

3 ...
more >>>

Madhu Sudan, Luca Trevisan

The error probability of Probabilistically Checkable Proof (PCP)

systems can be made exponentially small in the number of queries

by using sequential repetition. In this paper we are interested

in determining the precise rate at which the error goes down in

an optimal protocol, and we make substantial progress toward ...
more >>>

Lars Engebretsen, Jonas Holmerin, Alexander Russell

An equation over a finite group G is an expression of form

w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted

variable, or a constant from G; such an equation is satisfiable

if there is a setting of the variables to values in G ...
more >>>

Stefan Droste, Thomas Jansen, Ingo Wegener

Randomized search heuristics like local search, simulated annealing or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics.

Here a framework called black-box ... more >>>

Till Tantau

This paper introduces logspace optimisation problems as

analogues of the well-studied polynomial-time optimisation

problems. Similarly to them, logspace

optimisation problems can have vastly different approximation

properties, even though the underlying existence and budget problems

have the same computational complexity. Numerous natural problems

are presented that exhibit such a varying ...
more >>>

Miki Hermann, Reinhard Pichler

Following the approach of Hemaspaandra and Vollmer, we can define

counting complexity classes #.C for any complexity class C of decision

problems. In particular, the classes #.Pi_{k}P with k >= 1

corresponding to all levels of the polynomial hierarchy have thus been

studied. However, for a large variety of counting ...
more >>>

Prabhu Manyem, Julien Ugon

We survey research that studies the connection between the computational complexity

of optimization problems on the one hand, and the duality gap between the primal and

dual optimization problems on the other. To our knowledge, this is the first survey that

connects the two very important areas. We further look ...
more >>>