Correlation bounds and #SAT algorithms for small linear-size circuits

详细信息    查看全文

• 作者：Ruiwen Chen^a ; ^{ruiwen.chen@cs.ox.ac.uk} ; Valentine Kabanets^b ; ^{kabanets@cs.sfu.ca}
• 关键词：Boolean circuit ; Random restriction ; Satisfiability algorithm ; Correlation bound
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：22 November 2016
• 年：2016
• 卷：654
• 期：Complete
• 页码：2-10
• 全文大小：345 K
• 卷排序：654

文摘

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic satisfiability counting algorithms for small linear-size circuits. Let B2B2 be the full binary basis, and let U2=B2∖{⊕,≡}U2=B2∖{⊕,≡}. We prove that, for circuits over U2U2 of size 3n−nϵ3n−nϵ for any constant ϵ>0.5ϵ>0.5, the correlation with Parity is at most 2−nΩ(1)2−nΩ(1), and there is a #SAT algorithm (which counts the number of satisfying assignments) running in time 2n−nΩ(1)2n−nΩ(1); for circuit size 3n−ϵn3n−ϵn for ϵ>0ϵ>0, the correlation with Parity is at most 2−Ω(n)2−Ω(n), and there is a #SAT algorithm running in time 2n−Ω(n)2n−Ω(n). Similar correlation bounds and algorithms are also proved for circuits over B2B2 of size almost 2.5n.