My UW  UW Search
Computer Science Home Page
Theory of Computing
People
Courses
Seminars
Student Lunch & Reading Group
Qualifying Exam
Tyson Williams
Courses
Fun Links
Publications
Talks
Teaching
Useful Links
UWM Answers
Videos



Tyson Williams
Welcome
Hello.
I completed a Ph.D. student in theoretical computer science at the University of WisconsinMadison in 2015.
I was grateful to be advised by JinYi Cai.
I now work at Blocher Consulting.
Research Interests
I am interested in the complexity of counting problems defined over graphs,
especially those in the Holant framework,
where there are holographic algorithms.
A central goal in this area is to prove dichotomy theorems,
which state that every problem in some large class is either efficiently computable or #Phard.
Such results tend to give a unified explanation for the tractability of certain problems
and a reasonable basis for the conjecture that the remaining problems are intractable.
More generally,
I am interested in the computational complexity of counting problems defined by the evaluation of various graph polynomials,
the most wellknown being the Tutte polynomial.
I also consider how the computational complexity changes when these counting problems are defined over restricted graph classes, such as planar, regular, or bipartite graphs.
Publications
(... with abstracts)

A Holant Dichotomy: Is the FKT Algorithm Universal?
Joint work with JinYi Cai, Zhiguo Fu, and Heng Guo
To appear at FOCS 2015
Paper: arXiv

The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems
Joint work with JinYi Cai and Heng Guo
FOCS 2014
Paper: arXiv or conference (cameraready, official)
Talk by myself at FOCS

Holographic Algorithms Beyond Matchgates
Joint work with JinYi Cai and Heng Guo
ICALP 2014
Paper: arXiv or conference (cameraready, official)

The Complexity of Planar Boolean #CSP with Complex Weights
Joint work with Heng Guo
ICALP 2013
Paper: arXiv or conference (cameraready, official)

A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Joint work with JinYi Cai and Heng Guo
STOC 2013
Paper: arXiv or conference
Talk by JinYi Cai at IAS

Gadgets and AntiGadgets Leading to a Complexity Dichotomy
Joint work with JinYi Cai and Michael Kowalczyk
ITCS 2012
Paper: arXiv or conference
Thesis
Advances in the Computational Complexity of Holant Problems


