Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-099 | 12th June 2015 12:49

#### Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

TR15-099
Authors: Ruiwen Chen
Publication: 19th June 2015 12:39
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 hardness of computing affine extractors using linear-size $B_k$-formulas.