2 citations · 2 across the 6 of their papers we have counts for
5 papers · 1 filter
On the power of counting the total number of computation paths of NPTMs
Eleni Bakali, Aggeliki Chalki, Sotiris Kanellopoulos +2
In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of accepting paths of an NPTM. In th…
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…
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…
Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds
Eleni Bakali
We consider the class of counting problems,i.e. functions in P, which are self reducible, and have easy decision version, i.e. for every input it is easy to decide if the value…