|
|
||
Tyson Williams
|
Theoretical Computer Science Department of Computer Science 1210 West Dayton Street Madison, WI 53706 Curriculum Vitae ProfilesarXiv dblp Google Scholar MathSciNet (using ezproxy) Scopus |
|
Welcome
Hello. I completed a PhD student in theoretical computer science at the University of Wisconsin-Madison in 2015. I am grateful that I was advised by Jin-Yi Cai. I went into industry after graduating. You can follow me around the internet by starting with my about.me page.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 #P-hard. 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 well-known 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 Jin-Yi 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 Jin-Yi Cai and Heng Guo
FOCS 2014
Paper: arXiv or conference (camera-ready, official)
Talk by myself at FOCS
-
Holographic Algorithms Beyond Matchgates
Joint work with Jin-Yi Cai and Heng Guo
ICALP 2014
Paper: arXiv or conference (camera-ready, official)
-
The Complexity of Planar Boolean #CSP with Complex Weights
Joint work with Heng Guo
ICALP 2013
Paper: arXiv or conference (camera-ready, official)
-
A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Joint work with Jin-Yi Cai and Heng Guo
STOC 2013
Paper: arXiv or conference
Talk by Jin-Yi Cai at IAS
-
Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
Joint work with Jin-Yi Cai and Michael Kowalczyk
ITCS 2012
Paper: arXiv or conference
Thesis
Advances in the Computational Complexity of Holant Problems
This site has seen
