| Presentation | 2016-10-21 An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits. Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A Boolean function $f: bits{n} to bit$ is {em weighted symmetric}if there exist a function $g: mathbb{Z} to bit$ and integers $w_0, w_1, ldots, w_n$ such that $f(x_1,ldots,x_n) = g(w_0+sum_{i=1}^n w_i x_i)$ holds. In this paper, we present algorithms for the circuit satisfiability problem of depth-2 circuits that consist of one weighted symmetric gate at top and a number of AND gates at bottom. Our algorithm runs in time super-polynomially faster than $2^n$ even when the number of gates is super-polynomial and the maximum weight of symmetric gates is nearly exponential. With an additional trick, we give an algorithm for the maximum satisfiability problem that runs in time $poly(n^t) cdot 2^{n-n^{1/O(t)}}$ for instances with $n$ variables, $O(n^t)$ clauses and {em arbitrary} weights. To the best of our knowledge, this is the first moderately exponential time algorithm even for Max $2$SAT instances with arbitrary weights. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Satisfiability / Circuit Complexity / Constant Depth Circuit / Symmetric Gate |
| Paper # | COMP2016-27 |
| Date of Issue | 2016-10-14 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2016/10/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Tohoku University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroo Itoh(Univ. of Electro-Comm.) |
| Vice Chair | Yuushi Uno(Osaka Pref. Univ.) |
| Secretary | Yuushi Uno(Seikei Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | ENG-JTITLE |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits. |
| Sub Title (in English) | |
| Keyword(1) | Satisfiability |
| Keyword(2) | Circuit Complexity |
| Keyword(3) | Constant Depth Circuit |
| Keyword(4) | Symmetric Gate |
| 1st Author's Name | Kazuhisa Seto |
| 1st Author's Affiliation | Seikei University(Seikei Univ.) |
| 2nd Author's Name | Suguru Tamaki |
| 2nd Author's Affiliation | Kyoto University(Kyoto Univ.) |
| 3rd Author's Name | Junichi Teruyama |
| 3rd Author's Affiliation | National Institute of Informatics(NII) |
| Date | 2016-10-21 |
| Paper # | COMP2016-27 |
| Volume (vol) | vol.116 |
| Number (no) | COMP-262 |
| Page | pp.pp.29-34(COMP), |
| #Pages | 6 |
| Date of Issue | 2016-10-14 (COMP) |