Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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)
\left(1+3\frac{\log n}{n}+\frac{c}{n}\right)
In this note,
we announce a modest ... more >>>

TR10-095 | 11th June 2010
Masaki Yamamoto

A combinatorial analysis for the critical clause tree

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

TR07-029 | 20th January 2007
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem

Revisions: 1

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

ISSN 1433-8092 | Imprint