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

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Clique-width is a graph parameter that measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic with second-order

quantification on vertex sets, that includes NP-hard problems) can be

solved efficiently for graphs of certified small clique-width. It is

widely ...
more >>>