کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427065 | 686435 | 2016 | 4 صفحه PDF | دانلود رایگان |
• A new algorithm for the construction of approximate ismorphisms between Boolean functions.
• Improvement on an existing algorithm in several respects.
• Efficiency: it works in polynomial time.
• Performance: better performance guarantees as before.
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.
Journal: Information Processing Letters - Volume 116, Issue 3, March 2016, Pages 237–240