The University of Wisconsin-Madison

Computer Sciences Department

Tyson Williams Pronounce Tyson Williams

Ph.D. Student
Theoretical Computer Science
Office: 4397
Email Address of Tyson Williams

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

Curriculum Vitae


profile for Tyson Williams on Stack Exchange, a network of free, community-driven Q&A sites
Google scholar
Tyson Williams


Hello. I am a sixth year Ph.D. student in theoretical computer science at the University of Wisconsin-Madison. I am grateful to be advised by Jin-Yi 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 #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.


(... with abstracts)
  1. The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems [arXiv]
    Joint work with Jin-Yi Cai and Heng Guo
    To appear at FOCS 2014

  2. Holographic Algorithms Beyond Matchgates [conference (camera-ready, official), arXiv]
    Joint work with Jin-Yi Cai and Heng Guo
    ICALP 2014

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

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

  5. Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy [conference, arXiv]
    Joint work with Jin-Yi Cai and Michael Kowalczyk
    ITCS 2012
Computer Sciences | UW Home
This site has seen Hit Counter by Digits unique visitors.