All reports by Author Takayuki Sakai:

__
TR16-099
| 13th June 2016
__

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama#### Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

__
TR15-136
| 28th July 2015
__

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama#### A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

A Boolean function $f: \{0,1\}^n \to \{0,1\}$ is weighted symmetric if there exist a function $g: \mathbb{Z} \to \{0,1\}$ 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 bounded depth circuits with AND, ... more >>>

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of

depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom.

As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in ...
more >>>