## Abstract

We give a #SAT algorithm for boolean formulas over arbitrary finite bases. Let B

We also give improved algorithms and lower bounds for formulas over finite unate bases, i.e., bases of functions which are monotone increasing or decreasing in each of the input variables.

_{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-δc,k)}for δ_{c,k}= c^{-O(c2k2k)}. We also show the average-case hardness of computing affine extractors using linear-size B_{k}-formulas.We also give improved algorithms and lower bounds for formulas over finite unate bases, i.e., bases of functions which are monotone increasing or decreasing in each of the input variables.

Original language | English |
---|---|

Title of host publication | MFCS 2015 |

Number of pages | 20 |

Publication status | Published - 2015 |