Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

Ruiwen Chen

Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

Ruiwen Chen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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-δ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

Access to Document

Chen_MFCSAccepted author manuscript, 401 KB

Cite this

@inproceedings{ad97e570f96e49d8b6209c8af37b2cf3,

title = "Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases",

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.",

author = "Ruiwen Chen",

note = "Date of Acceptance: 03/06/2015",

year = "2015",

language = "English",

booktitle = "MFCS 2015",

}

TY - GEN

T1 - Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

AU - Chen, Ruiwen

N1 - Date of Acceptance: 03/06/2015

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

M3 - Conference contribution

BT - MFCS 2015

ER -

Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

Abstract

Access to Document

Fingerprint

Cite this