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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>