All reports by Author Paolo Liberatore:

__
TR02-067
| 5th October 2002
__

Marco Cadoli, Francesco Donini, Paolo Liberatore, Marco Schaerf#### k-Approximating Circuits

__
TR99-038
| 27th August 1999
__

Peter Jonsson, Paolo Liberatore#### On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

Marco Cadoli, Francesco Donini, Paolo Liberatore, Marco Schaerf

In this paper we study the problem of approximating a boolean

function using the Hamming distance as the approximation measure.

Namely, given a boolean function f, its k-approximation is the

function f^k returning true on the same points in which f does,

plus all points whose Hamming distance from the ...
more >>>

Peter Jonsson, Paolo Liberatore

We study the computational complexity of an optimization

version of the constraint satisfaction problem: given a set $F$ of

constraint functions, an instance consists of a set of variables $V$

related by constraints chosen from $F$ and a natural number $k$. The

problem is to decide whether there exists a ...
more >>>