All reports by Author Masaki Yamamoto:

__
TR11-086
| 2nd June 2011
__

Masaki Yamamoto#### A tighter lower bound on the circuit size of the hardest Boolean functions

__
TR10-095
| 11th June 2010
__

Masaki Yamamoto#### A combinatorial analysis for the critical clause tree

__
TR07-029
| 20th January 2007
__

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

Revisions: 1

Masaki Yamamoto

In [IPL2005],

Frandsen and Miltersen improved bounds on the circuit size $L(n)$ of the hardest Boolean function on $n$ input bits:

for some constant $c>0$:

\[

\left(1+\frac{\log n}{n}-\frac{c}{n}\right)

\frac{2^n}{n}

\leq

L(n)

\leq

\left(1+3\frac{\log n}{n}+\frac{c}{n}\right)

\frac{2^n}{n}.

\]

In this note,

we announce a modest ...
more >>>

Masaki Yamamoto

In [FOCS1998],

Paturi, Pudl\'ak, Saks, and Zane proposed a simple randomized algorithm

for finding a satisfying assignment of a $k$-CNF formula.

The main lemma of the paper is as follows:

Given a satisfiable $k$-CNF formula that

has a $d$-isolated satisfying assignment $z$,

the randomized algorithm finds $z$

with probability at ...
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 >>>