PhD Seminar • Software Engineering — Combining SAT Solvers with Computer Algebra Systems to Verify Combinatorial ConjecturesExport this event to calendar

Thursday, April 5, 2018 — 12:00 PM EDT

Edward Zulkoski, PhD candidate
David R. Cheriton School of Computer Science

We present a method and an associated system, called MathCheck, that embeds the functionality of a computer algebra system (CAS) within the inner loop of a conflict-driven clause-learning SAT solver. Such a SAT+CAS system combines the efficient search routines of modern SAT solvers with the expressive power of CAS, thus complementing both. The key insight behind the power of the SAT+CAS combination is that the CAS system can help cut down the search-space of the SAT solver, by providing learned clauses that encode theory-specific lemmas, as it searches for a counter example to the input conjecture. In addition, the combination enables a more efficient encoding of problems than a pure Boolean representation. 

As case studies, we study two open mathematical conjectures from graph theory regarding properties of hypercubes. The first conjecture states that any matching of any d-dimensional hypercube can be extended to a Hamiltonian cycle; the second states that given an edge-antipodal coloring of a hypercube there always exists a monochromatic path between two antipodal vertices. Previous results have shown the conjectures true up to certain low-dimensional hypercubes. We extend these two conjectures to higher-dimensional hypercubes.

Location 
DC - William G. Davis Computer Research Centre
3323
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2020 (190)
    1. December (1)
    2. November (2)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (217)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)