License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.82
URN: urn:nbn:de:0030-drops-64905
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6490/
Sakai, Takayuki ;
Seto, Kazuhisa ;
Tamaki, Suguru ;
Teruyama, Junichi
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
Abstract
A Boolean function f:{0,1}^n -> {0,1} is weighted symmetric if there exist a function g: Z -> {0,1} and integers w_0, w_1, ..., w_n such that f(x_1, ...,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 bounded depth circuits with AND, OR, NOT gates and a limited number of weighted symmetric gates. Our algorithms run 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)*2^{n-n^{1/O(t)}} for instances with n variables, O(n^t) clauses and arbitrary weights. To the best of our knowledge, this is the first moderately exponential time algorithm even for Max 2SAT instances with arbitrary weights.
Through the analysis of our algorithms, we obtain average-case lower bounds and compression algorithms for such circuits and worst-case lower bounds for majority votes of such circuits, where all the lower bounds are against the generalized Andreev function. Our average-case lower bounds might be of independent interest in the sense that previous ones for similar circuits with arbitrary symmetric gates rely on communication complexity lower bounds while ours are based on the restriction method.
BibTeX - Entry
@InProceedings{sakai_et_al:LIPIcs:2016:6490,
author = {Takayuki Sakai and Kazuhisa Seto and Suguru Tamaki and Junichi Teruyama},
title = {{Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {82:1--82:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6490},
URN = {urn:nbn:de:0030-drops-64905},
doi = {10.4230/LIPIcs.MFCS.2016.82},
annote = {Keywords: exponential time algorithm, circuit complexity, circuit minimization, maximum satisfiability}
}
|
Keywords: |
|
exponential time algorithm, circuit complexity, circuit minimization, maximum satisfiability |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
