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

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

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

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

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

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

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

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed ... more >>>

In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):

1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ... more >>>

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified ... more >>>

In this work we study oblivious complexity classes. Among our results:
1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.
2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ... more >>>