4 papers
Characterizations and approximability of hard counting classes below #P
Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis
An important objective of research in counting complexity is to understand which counting problems are approximable. In this quest, the complexity class TotP, a hard subclass of #P…
Exact uniform sampling over catalan structures
Alexandros Angelopoulos, Eleni Bakali
We present a new framework for creating elegant algorithms for exact uniform sampling of important Catalan structures, such as triangulations of convex polygons, Dyck words, monoto…
On randomized counting versus randomised decision
Eleni Bakali
We study the question of which counting problems admit f.p.r.a.s., under a structural complexity perspective. Since problems in #P with NP-complete decision version do not admit f.…
Relating counting complexity to non-uniform probability measures
Eleni Bakali
A standard method for designing randomized algorithms to approximately count the number of solutions of a problem in P, is by constructing a rapidly mixing Markov chain converg…