All reports by Author Paolo Liberatore:

__
TR22-062
| 2nd May 2022
__

Paolo Liberatore#### Superredundancy: A tool for Boolean formula minimization complexity analysis

__
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

Paolo Liberatore

A superredundant clause is a clause that is redundant in the resolution closure of a formula. The converse concept of superirredundancy ensures membership of the clause in all minimal CNF formulae that are equivalent to the given one. This allows for building formulae where some clauses are fixed when minimizing ... more >>>

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