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

Profiles


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

Welcome

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.

Publications

(... with abstracts)
  1. 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)

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

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

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

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