Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Daniel Král:

TR04-051 | 10th June 2004
Zdenek Dvorák, Daniel Král, Ondrej Pangrác

Locally consistent constraint satisfaction problems

An instance of a constraint satisfaction problem is $l$-consistent
if any $l$ constraints of it can be simultaneously satisfied.
For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ... more >>>

TR03-061 | 29th August 2003
Jan Kára, Daniel Král

Free Binary Decision Diagrams for Computation of EAR_n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined
for n x n Boolean matrices: EAR_n(M)=1 iff the matrix ... more >>>

TR03-050 | 16th June 2003
Daniel Král

Locally satisfiable formulas

A CNF formula is k-satisfiable if each k clauses of it can be satisfied
simultaneously. Let \pi_k be the largest real number such that for each
k-satisfiable formula with variables x_i, there are probabilities p_i
with the following property: If each variable x_i is chosen randomly and
independently to be ... more >>>

TR00-013 | 14th February 2000
Daniel Král

Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

Ordered binary decision diagrams (OBDDs) and parity ordered binary
decision diagrams have proved their importance as data structures
representing Boolean functions. In addition to parity OBDDs we study
their generalization which we call parity AOBDDs, give the algebraic
characterization theorem and compare their minimal size to the size
more >>>

ISSN 1433-8092 | Imprint