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

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

Shiteng Chen, Periklis Papakonstantinou

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$.

In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of ... more >>>

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

Zeev Dvir, Alexander Golovnev, Omri Weinstein

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

Joshua Cook

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>

Rahul Ilango

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

While ... more >>>