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
MathSciNet (using ezproxy)
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. A Holant Dichotomy: Is the FKT Algorithm Universal?
    Joint work with Jin-Yi Cai, Zhiguo Fu, and Heng Guo
    In submission
    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
 
Computer Sciences | UW Home
This site has seen Hit Counter by Digits unique visitors.