Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Succinct:
TR15-100 | 16th June 2015
Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

Succinct Encodings of Graph Isomorphism

It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>

TR15-101 | 15th June 2015
Patrick Scharpfenecker

On the structure of Solution-Graphs for Boolean Formulas

Revisions: 2

In this work we extend the study of solution graphs and prove that for boolean formulas in a class called CPSS, all connected components are partial cubes of small dimension, a statement which was proved only for some cases in [Schwerdtfeger 2013]. In contrast, we show that general Schaefer formulas ... more >>>

ISSN 1433-8092 | Imprint