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

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

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