کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952417 | 1442031 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Correlation bounds and #SAT algorithms for small linear-size circuits
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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 B2 be the full binary basis, and let U2=B2â{â,â¡}. We prove that, for circuits over U2 of size 3nânϵ for any constant ϵ>0.5, the correlation with Parity is at most 2ânΩ(1), and there is a #SAT algorithm (which counts the number of satisfying assignments) running in time 2nânΩ(1); for circuit size 3nâϵn for ϵ>0, the correlation with Parity is at most 2âΩ(n), and there is a #SAT algorithm running in time 2nâΩ(n). Similar correlation bounds and algorithms are also proved for circuits over B2 of size almost 2.5n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 2-10
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 2-10
نویسندگان
Ruiwen Chen, Valentine Kabanets,