All reports by Author Phokion G. Kolaitis:

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

__
TR06-160
| 17th December 2006
__

Tomas Feder, Phokion G. Kolaitis#### Closures and dichotomies for quantified constraints

__
TR06-094
| 29th July 2006
__

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou#### The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

__
TR05-119
| 15th September 2005
__

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini#### Preferred representations of Boolean relations

__
TR00-082
| 17th August 2000
__

Lefteris Kirousis, Phokion G. Kolaitis#### The Complexity of Minimal Satisfiability Problems

Revisions: 2

Phokion G. Kolaitis, Swastik Kopparty

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

Tomas Feder, Phokion G. Kolaitis

Quantified constraint satisfaction is the generalization of

constraint satisfaction that allows for both universal and existential

quantifiers over constrained variables, instead

of just existential quantifiers.

We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes

a pattern of quantifier alternation ending in exists or the set of all possible

more >>>

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini

We introduce the notion of a plain basis for a co-clone in Post's lattice. Such a basis is a set of relations B such that every constraint C over a relation in the co-clone is logically equivalent to a conjunction of equalities and constraints over B and the same variables ... more >>>

Lefteris Kirousis, Phokion G. Kolaitis

A dichotomy theorem for a class of decision problems is

a result asserting that certain problems in the class

are solvable in polynomial time, while the rest are NP-complete.

The first remarkable such dichotomy theorem was proved by

T.J. Schaefer in 1978. It concerns the ...
more >>>