Paper Info
Title
Efficient computation of approximate isomorphisms between Boolean functions.
Abstract
Arvind and Vasudev [2] have introduced the notion of an approximate isomorphism between two Boolean functions f and g. They furthermore designed two algorithms that construct an approximate isomorphism when given oracle access to f and g. The first of these algorithms is specialized to Boolean functions which are computable by constant-depth circuits. The second one applies to any pair of Boolean functions. It runs in exponential time and achieves optimality up to a factor of order n. In this paper, we present an improved analysis and come up with a variant of the second algorithm that runs in polynomial time and achieves optimality up to a factor of (approximately) 2.
Year
DOI
Venue
2016
10.1016/j.ipl.2015.11.009
Information Processing Letters
Keywords
Field
DocType
Randomized algorithms,Approximation algorithms,Analysis of algorithms,Boolean functions,Isomorphism problem
Karp–Lipton theorem,Maximum satisfiability problem,Boolean network,Discrete mathematics,Boolean circuit,Combinatorics,Boolean algebras canonically defined,Parity function,Boolean expression,Two-element Boolean algebra,Mathematics
Journal
Volume
Issue
ISSN
116
3
0020-0190
Citations 
PageRank 
References 
0
0.34
0
Authors
1
Name
Order
Citations
PageRank
Hans-Ulrich Simon1567104.52