<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T13:44:55Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/9110" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/9110</identifier><datestamp>2017-03-21T18:49:20Z</datestamp><setSpec>com_10012_9900</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9908</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="836f7e15-c9d6-4e8f-afbf-c2e1791e25e6" confidence="600">Newsham, Zackary</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-01-21T14:15:55Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2015-05-22T05:30:11Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-01-21</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2015</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/9110</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Despite enormous improvements in Boolean SATisfiability solver performance&#xd;
over the last decade, it is still unclear why specific input formula are slow&#xd;
to solve, when other similarly specified formula execute more quickly. This&#xd;
work explores the relationship between the community structure of a SAT&#xd;
formula and its execution time on several state-of-the-art solvers. We explore&#xd;
the analysis of this data from a number of directions; first, we explore the&#xd;
relationship between the well known clause-variable ratio result, and com-&#xd;
munity structure in randomly generated instances. Second, we perform a&#xd;
standard linear regression on data obtained from the 2013 SAT competition.&#xd;
Third, we present a visualisation tool and data repository for viewing the&#xd;
structure of a SAT formula. Fourth, we explore the effect of hardware con-&#xd;
straints on the solution time of instances across various machines. Finally,&#xd;
we explore survival analysis, a technique that is new to the field of Boolean&#xd;
SATisfiability. By collating the results from each of these experiments, we&#xd;
have determined that the community structure is critical in determining the&#xd;
solution time of a SAT formula, more important than the clause-variable&#xd;
ratio of the formula. While this work is not a complete explanation of the&#xd;
varying solution time of SAT formulae, it has provided us with significant&#xd;
insight for further research to answer the question: why different similarly&#xd;
specified formula have such different solution times?</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="embargoterms" lang="en">4 months</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">community</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">survival</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">SAT</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">solver</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">boolean satisfiability</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">linear regression</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">An Analysis of the Effect of Community Structure on SAT Solver Performance</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="comment" qualifier="hidden" lang="en">I&amp;apos;ve requested 4 months of restricted access as some of the work in the thesis will be submitted to various conferences between now and April.</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Applied Science</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>