It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>

We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let $B_k$ be the basis composed of all boolean functions on at most $k$ inputs. For $B_k$-formulas on $n$ inputs of size $cn$, our algorithm runs in time $2^{n(1-\delta_{c,k})}$ for $\delta_{c,k} = c^{-O(c^2k2^k)}$. We also show the average-case ... more >>>

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized
query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree
of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. ... more >>>