Viðburðir eftir árum


Structural and descriptive complexity of hard counting problems with easy decision version

  • 20.6.2022, 14:00 - 15:00, Háskólinn í Reykjavík

We invite you to join us on Monday, June 20, at 14:00, in room M104, to hear about counting problems.

Aggeliki Chalki from National Technical University of Athens will visit us and give a talk at the seminar series in Department of Computer Science.

The class #P contains the counting versions of NP problems. For counting problems in #P the output is the number of solutions to a computational problem in NP (or the number of accepting paths of a non-deterministic poly-time Turing machine). Efficient and exact counting is very rare, so the main research interest in this area is to classify counting problems with respect to their approximability and design approximation algorithms for those that can be approximated. In this quest, the class TotP is of key importance, since it contains self-reducible counting problems of #P, with an easy decision version, thus eligible to be approximal.

In this talk, after an introduction to counting, we are going to define and discuss the class TotP. In specific we will talk about its relationship with the class of counting problems that admit an FPRAS (fully polynomial randomized approximation scheme) and then, we will give a logical characterization of TotP. The latter was an open question in the area of descriptive complexity for counting classes.



Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á ru.is eða með því að senda tölvupóst á netfangið: personuvernd@ru.is
//
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our ru.is or send an e-mail: personuvernd@ru.is