The University of Wisconsin-Madison
   

 
Computer Sciences Department

Tyson Williams Pronounce Tyson Williams


Theoretical Computer Science
Email Address of Tyson Williams

Department of Computer Science
1210 West Dayton Street
Madison, WI 53706

Curriculum Vitae

Profiles


arXiv
dblp
Google Scholar
MathSciNet (using ezproxy)
Scopus
Tyson Williams

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)
  1. 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

  2. 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

  3. Holographic Algorithms Beyond Matchgates
    Joint work with Jin-Yi Cai and Heng Guo
    ICALP 2014
    Paper: arXiv or conference (camera-ready, official)

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

  5. 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

  6. 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
 
Computer Sciences | UW Home
This site has seen Hit Counter by Digits unique visitors.