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 am a sixth year Ph.D. student in theoretical computer science at the University of WisconsinMadison.
I am grateful to be advised by JinYi Cai.
My undergraduate education was at Iowa State University,
where I received BS degrees in computer science and computer engineering.
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)

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)

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


