All reports by Author Suguru Tamaki:

__
TR16-100
| 27th June 2016
__

Suguru Tamaki#### A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

__
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

__
TR16-022
| 22nd February 2016
__

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki#### Circuit size lower bounds and #SAT upper bounds through a general framework

Revisions: 2

__
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

__
TR14-066
| 17th April 2014
__

Suguru Tamaki, Yuichi Yoshida#### Robust Approximation of Temporal CSP

__
TR12-071
| 29th May 2012
__

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

__
TR09-074
| 10th September 2009
__

Suguru Tamaki, Yuichi Yoshida#### A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness

__
TR08-011
| 21st November 2007
__

Kazuo Iwama, Suguru Tamaki#### The Complexity of the Hajos Calculus for Planar Graphs

__
TR07-029
| 20th January 2007
__

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto#### A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem

Revisions: 1

__
TR03-053
| 8th July 2003
__

Kazuo Iwama, Suguru Tamaki#### Improved Upper Bounds for 3-SAT

Suguru Tamaki

We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time ... more >>>

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

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... 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 >>>

Suguru Tamaki, Yuichi Yoshida

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... 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 >>>

Suguru Tamaki, Yuichi Yoshida

Long Code testing is a fundamental problem in the area of property

testing and hardness of approximation.

Long Code is a function of the form $f(x)=x_i$ for some index $i$.

In the Long Code testing, the problem is, given oracle access to a

collection of Boolean functions, to decide whether ...
more >>>

Kazuo Iwama, Suguru Tamaki

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajĀLos calculus is polynomially bounded.

more >>>Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou

studied in [Gopalan et al., ICALP2006] connectivity properties of the

solution-space of Boolean formulas, and investigated complexity issues

on connectivity problems in Schaefer's framework [Schaefer, STOC1978].

A set S of logical relations is Schaefer if all relations in ...
more >>>

Kazuo Iwama, Suguru Tamaki

This paper presents a new upper bound for the

$k$-satisfiability problem. For small $k$'s, especially for $k=3$,

there have been a lot of algorithms which run significantly faster

than the trivial $2^n$ bound. The following list summarizes those

algorithms where a constant $c$ means that the algorithm runs in time

more >>>