Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Paolo Liberatore:

TR02-067 | 5th October 2002
Marco Cadoli, Francesco Donini, Paolo Liberatore, Marco Schaerf

k-Approximating Circuits

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

TR99-038 | 27th August 1999
Peter Jonsson, Paolo Liberatore

On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

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

ISSN 1433-8092 | Imprint