Marco Benini

Category Archives: Theoretical Computer Science

Visiting JAIST

Currently, I’m in the Japanese Advanced Institute of Science and Technology, kindly hosted by Prof. H. Ishihara and Dr. T. Nemoto, as part of the CORCON research project. In this … Continue reading

May 28, 2014 · Leave a comment

A few notes on balanced trees

In the last project of the course “Algoritmi and Strutture Dati”, there was a problem requiring to find all the points containing some objects in a square of given width … Continue reading

May 3, 2011 · Leave a comment

An exact formula for satisfiability

Let be an instance of SAT. As in a previous post, let denote the i-th clause. Moreover, let . We know that . Evidently, is the set of assignments falsifying … Continue reading

April 1, 2011 · 1 Comment

A quick satisfiability check

As it is well-known, Boolean Satisfiability, SAT for short, is NP-complete. Suppose is a formula where is a literal, i.e., the variable , or , or (when the variable does … Continue reading

April 1, 2011 · 1 Comment