Skip to Main Content
 

Global Search Box

 
 
 

ETD Abstract Container

Abstract Header

Mixed Size XOR Strong Refutation

Dowling, Brendan L
http://rave.ohiolink.edu/etdc/view?acc_num=case1600985815652235

Abstract Details

2020, Master of Sciences, Case Western Reserve University, EECS - Computer and Information Sciences.
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.
Harold Connamacher (Advisor)
Vincenzo Liberatore (Committee Member)
Shuai Xu (Committee Member)
119 p.
Computer Science; Mathematics
k-XOR; Strong Refutation; Spectral Methods; Injective Tensor Norm

Recommended Citations

Citations

  • Dowling, B. L. (2020). Mixed Size XOR Strong Refutation [Master's thesis, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1600985815652235

    APA Style (7th edition)

  • Dowling, Brendan. Mixed Size XOR Strong Refutation. 2020. Case Western Reserve University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1600985815652235.

    MLA Style (8th edition)

  • Dowling, Brendan. "Mixed Size XOR Strong Refutation." Master's thesis, Case Western Reserve University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=case1600985815652235

    Chicago Manual of Style (17th edition)

case1600985815652235
108
© 2020, some rights reserved.Creative Commons License Mixed Size XOR Strong Refutation by Brendan L Dowling is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.