| Popis: |
An esteemed 2016 paper set a new lower bound on the clause density required to strongly refute a k-XOR formula in polynomial time. This paper used the sum of squares algorithm in conjunction with an improved bound for the injective tensor norm to reach its result, which is limited to formulas with all clauses the same size. We consider how this technique could be expanded to formulas with mixed clause sizes. We specifically focus our efforts on what we view as the simplest combination of clause sizes: an XOR formula with clauses of sizes k and 2k with k even. While this thesis does not establish a new refutation bound for this mixed size formula, it does give a prospective structure for the proof, and shows how to expand the 2016 paper’s techniques to mixed size problems. Additionally, this thesis gives an overview of the 2016 paper for new researchers. |
