Local Restrictions from the Furst-Saxe-Sipser Paper

详细信息    查看全文

• 作者：Suguru Tamaki ; Osamu Watanabe
• 关键词：Local restriction ; Random restriction ; Computational complexity theory ; Algorithm design
• 刊名：Theory of Computing Systems
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：60
• 期：1
• 页码：20-32
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1433-0490
• 卷排序：60

文摘

In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13–27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.