Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Graphisomorphism:
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