Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PATRICK SCHARPFENECKER:
All reports by Author Patrick Scharpfenecker:

TR16-024 | 22nd February 2016
Patrick Scharpfenecker, Jacobo Toran

Solution-Graphs of Boolean Formulas and Isomorphism

The solution graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures ... 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 >>>


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




ISSN 1433-8092 | Imprint