University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Computational complexity of counting and closure properties of sets of tensors

Computational complexity of counting and closure properties of sets of tensors

Add to your list(s) Download to your calendar using vCal

  • UserMiriam Backens, University of Birmingham
  • ClockWednesday 06 July 2022, 14:00-15:00
  • HouseSS03.

If you have a question about this talk, please contact Jamie Vicary.

This talk has been canceled/deleted

Computational counting problems arise in many areas of physics, combinatorics, engineering or computer science. They are often formalised in the counting constraint satisfaction framework (#CSP, a generalisation of #SAT), or in the more general holant framework (effectively a tensor network contraction). In computational complexity, both problems are parameterised by sets of constraint functions or tensors. Replacing those sets by certain closures—called functional clones or holant clones, respectively—does not affect the computational complexity, so studying these closures is useful in classifying complexity. I will discuss the definition and certain known properties of holant clones used in exact complexity, as well as some partial progress and challenges in extending the results to approximation complexity.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.

 

© 2006-2022 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity