Name
Abstract | ||
|---|---|---|
We make a step towards characterizing the boolean functions to which isomorphism can be efficiently tested. Specifically, we prove that isomorphism to any boolean function on $\{0, 1\}^n$ with a polynomial number of distinct permutations can be tested with a number of queries that is independent of~$n$. We also show some partial results in the converse direction, and discuss related problems: testing isomorphism up to linear transformations, and testing isomorphism against a uniform (hyper)graph that is given in advance. Our results regarding the latter topic generalize a theorem of Fischer (SICOMP 2005), and in the process we also provide a simpler proof of his original result which avoids the use of Szemer\'edi's regularity lemma. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/CCC.2012.28 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
junto-symmetric functions,latter topic,testing isomorphism,distinct permutation,hypergraph isomorphism,partial result,original result,converse direction,regularity lemma,linear transformation,boolean function,polynomial number,boolean functions,computational complexity,testing,polynomials,graph theory,linear transformations,indexes,property testing,tin | Discrete mathematics,Symmetric function,Combinatorics,Graph isomorphism,Hypergraph,Induced subgraph isomorphism problem,Isomorphism,Isomorphism extension theorem,Order isomorphism,Subgraph isomorphism problem,Mathematics | Conference |
ISSN | Citations | PageRank |
1093-0159 | 9 | 0.67 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sourav Chakraborty | 1 | 381 | 49.27 |
| eldar fischer | 2 | 815 | 63.82 |
| David Gacia-Soriano | 3 | 9 | 0.67 |
| Arie Matsliah | 4 | 249 | 24.98 |