Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

Ruiwen Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We give a #SAT algorithm for boolean formulas over arbitrary finite bases. Let Bk be the basis composed of all boolean functions on at most k inputs. For Bk-formulas on n inputs of size cn, our algorithm runs in time 2n(1-δc,k) for δc,k = c-O(c2k2k). We also show the average-case hardness of computing affine extractors using linear-size Bk-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 languageEnglish
Title of host publicationMFCS 2015
Number of pages20
Publication statusPublished - 2015

Fingerprint Dive into the research topics of 'Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases'. Together they form a unique fingerprint.

Cite this