Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression
作者： Takayuki Sakai , Kazuhisa Seto , Suguru Tamaki , Junichi Teruyama
DOI: 10.1016/J.JCSS.2019.04.004
关键词:
摘要: Abstract A Boolean function f : { 0 , 1 } n → is weighted symmetric if there exist a g Z and integers w … such that ( x ) = + ∑ i holds. In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, OR, NOT gates limited number gates. Our run in time super-polynomially faster than 2 even when super-polynomial maximum weight nearly exponential. As special case, obtain an algorithm runs poly t ⋅ − / O instances variables clauses. Through analysis our algorithms, show average-case lower bounds compression worst-case majority votes circuits.
sci-hub.se 参考文章(66)
Ramamohan Paturi, Francis Zane, Circuits, cnfs, and satisfiability University of California, San Diego. ,(1998)
Eli Ben-Sasson, Emanuele Viola, Short PCPs with Projection Queries Automata, Languages, and Programming. pp. 163- 173 ,(2014) , 10.1007/978-3-662-43948-7_14
Kazuyuki Amano, Atsushi Saito, A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP Language and Automata Theory and Applications. pp. 461- 472 ,(2015) , 10.1007/978-3-319-15579-1_36
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Some Meet-in-the-Middle Circuit Lower Bounds Lecture Notes in Computer Science. pp. 334- 345 ,(2004) , 10.1007/978-3-540-28629-5_24
Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, Hans Ulrich Simon, Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science. pp. 171- 182 ,(2001) , 10.1007/3-540-45294-X_15
Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen, Lower Bounds for Circuits with Few Modular and Symmetric Gates Automata, Languages and Programming. pp. 994- 1005 ,(2005) , 10.1007/11523468_80
Fengming Wang, Nexp does not have non-uniform quasipolynomial-size ACC circuits of o(log log n) depth theory and applications of models of computation. pp. 164- 170 ,(2011) , 10.1007/978-3-642-20877-5_17
Parikshit Gopalan, Rocco A Servedio, None, Learning and lower bounds for AC 0 with threshold gates international workshop and international workshop on approximation randomization and combinatorial optimization algorithms and techniques. pp. 588- 601 ,(2010) , 10.1007/978-3-642-15369-3_44
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, The Complexity of Satisfiability of Small Depth Circuits Parameterized and Exact Computation. pp. 75- 85 ,(2009) , 10.1007/978-3-642-11269-0_6
Rahul Santhanam, Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds Bulletin of The European Association for Theoretical Computer Science. ,vol. 106, pp. 31- 52 ,(2012)