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 [arXiv]
Joint work with JinYi Cai and Heng Guo
To appear at FOCS 2014

Holographic Algorithms Beyond Matchgates [arXiv]
Joint work with JinYi Cai and Heng Guo
To appear at ICALP 2014

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

A Complete Dichotomy Rises from the Capture of Vanishing Signatures [conference, arXiv]
Joint work with JinYi Cai and Heng Guo
STOC 2013

Gadgets and AntiGadgets Leading to a Complexity Dichotomy [conference, arXiv]
Joint work with JinYi Cai and Michael Kowalczyk
ITCS 2012


