Under the auspices of the Computational Complexity Foundation (CCF) REPORTS > DETAIL:

### Paper:

TR11-137 | 14th October 2011 16:09

#### Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits TR11-137
Authors: Vikraman Arvind, Yadu Vasudev
Publication: 17th October 2011 09:30
Downloads: 1955
Keywords:

Abstract:

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 that computes a $\frac{1}{2^{\log(n)^{O(1)}}}$-approximate isomorphism between two isomorphic boolean functions $f$ and $g$ that are given by depth $d$ circuits of $n^{O(1)}$ size, where $d$ is a constant independent of $n$. In contrast, the best known algorithm for computing an exact isomorphism between $n$-ary boolean functions has running time $2^{O(n)}$ \cite{Luks99} even for functions computed by $n^{O(1)}$ size DNF formulas. Our algorithm is based on a recent result for hypergraph isomorphism with bounded edge size \cite{BabaiC08} and the classical Linial Mansour-Nisan result on approximating small depth and size boolean circuits by small degree polynomials using Fourier analysis.

ISSN 1433-8092 | Imprint
{"ft_lang_label":"__label__en","ft_lang_prob":0.7922433,"math_prob":0.9994098,"size":1178,"snap":"2019-13-2019-22","text_gpt3_token_len":337,"char_repetition_ratio":0.112436116,"word_repetition_ratio":0.0,"special_character_ratio":0.27843803,"punctuation_ratio":0.0787037,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998666,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-05-26T05:51:18Z\",\"WARC-Record-ID\":\"<urn:uuid:274cd829-b818-4c38-92fe-9f9a95d08eb0>\",\"Content-Length\":\"20525\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:dd8ad6b2-fcba-414b-a48b-9b7d94ad0a41>\",\"WARC-Concurrent-To\":\"<urn:uuid:443e46d3-5c4d-4f2a-ae16-7ad16bad8e63>\",\"WARC-IP-Address\":\"132.77.150.87\",\"WARC-Target-URI\":\"https://eccc.weizmann.ac.il/report/2011/137/\",\"WARC-Payload-Digest\":\"sha1:XA4QL6TL7YWN7S7577LEK4J3ACJRX5E6\",\"WARC-Block-Digest\":\"sha1:4BG7V3A7DNCYCUP5M2RV35SD2BELGNCG\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-22/CC-MAIN-2019-22_segments_1558232258849.89_warc_CC-MAIN-20190526045109-20190526071109-00219.warc.gz\"}"}