Mihir Bellare, Oded Goldreich, Madhu Sudan

This paper continues the investigation of the connection between proof

systems and approximation. The emphasis is on proving ``tight''

non-approximability results via consideration of measures like the

``free bit complexity'' and the ``amortized free bit complexity'' of

proof systems.

The first part of the paper presents a collection of new ... more >>>

Luca Trevisan

We prove an extremal combinatorial result regarding

the fraction of satisfiable clauses in boolean CNF

formulae enjoying a locally checkable property, thus

solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint

satisfaction ...
more >>>

Edward Hirsch

During the past three years there was an explosion of algorithms

solving MAX-SAT and MAX-2-SAT in worst-case time of the order

c^K, where c<2 is a constant, and K is the number of clauses

in the input formula. Such bounds w.r.t. the number of variables

instead of the number of ...
more >>>

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

The maximum 2-satisfiability problem (MAX-2-SAT) is:

given a Boolean formula in $2$-CNF, find a truth

assignment that satisfies the maximum possible number

of its clauses. MAX-2-SAT is MAXSNP-complete.

Recently, this problem received much attention in the

contexts of approximation (polynomial-time) algorithms

...
more >>>

Suguru Tamaki, Yuichi Yoshida

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>>

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of

depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom.

As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in ...
more >>>