Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-099 | 12th June 2015 12:49

Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

RSS-Feed




TR15-099
Authors: Ruiwen Chen
Publication: 19th June 2015 12:39
Downloads: 497
Keywords: 


Abstract:

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.

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.



ISSN 1433-8092 | Imprint