Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Isomorphism:
TR96-032 | 12th March 1996
Manindra Agrawal, Thomas Thierauf

The Boolean Isomorphism Problem

We investigate the computational complexity of the Boolean Isomorphism problem (BI):
on input of two Boolean formulas F and G decide whether there exists a permutation of
the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>

TR96-040 | 21st May 1996
Thomas Thierauf

The Isomorphismproblem for One-Time-Only Branching Programs

Revisions: 1 , Comments: 1

We investigate the computational complexity of the
isomorphism problem for one-time-only branching programs (BP1-Iso):
on input of two one-time-only branching programs B and B',
decide whether there exists a permutation of the variables of B'
such that it becomes equivalent to B.

Our main result is a two-round interactive ... more >>>

TR08-040 | 3rd April 2008
Sourav Chakraborty, Laszlo Babai

Property Testing of Equivalence under a Permutation Group Action

For a permutation group $G$ acting on the set $\Omega$
we say that two strings $x,y\,:\,\Omega\to\boole$
are {\em $G$-isomorphic} if they are equivalent under
the action of $G$, \ie, if for some $\pi\in G$ we have
$x(i^{\pi})=y(i)$ for all $i\in\Omega$.
Cyclic Shift, Graph Isomorphism ... more >>>

TR11-137 | 14th October 2011
Vikraman Arvind, Yadu Vasudev

Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits

Given two $n$-variable boolean functions $f$ and $g$, we study the problem of computing an $\varepsilon$-approximate isomorphism between them. I.e.\ a permutation $\pi$ of the $n$ variables such that $f(x_1,x_2,\ldots,x_n)$ and $g(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$ differ on at most an $\varepsilon$ fraction of all boolean inputs $\{0,1\}^n$. We give a randomized $2^{O(\sqrt{n}\log(n)^{O(1)})}$ algorithm ... more >>>

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

TR16-105 | 13th July 2016
Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>

TR21-122 | 24th August 2021
Sabyasachi Basu, Akash Kumar, C. Seshadhri

The complexity of testing all properties of planar graphs, and the role of isomorphism

Consider property testing on bounded degree graphs and let $\varepsilon > 0$ denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on $\varepsilon$. Recent advances in testing minor-freeness have proven that ... more >>>

ISSN 1433-8092 | Imprint