All reports by Author Kazuhisa Seto:

__
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

__
TR12-071
| 29th May 2012
__

Kazuhisa Seto, Suguru Tamaki#### A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

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 >>>

Kazuhisa Seto, Suguru Tamaki

We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis.

For formulas of size at most $cn$, our algorithm runs in time $2^{(1-\mu_c)n}$ for some constant $\mu_c>0$.

As a byproduct of the running time analysis of our algorithm,

we get strong ...
more >>>