10 citations · 11 across the 10 of their papers we have counts for
4 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…
Approximate #Knapsack Computations to Count Semi-Fair Allocations
Theofilos Triommatis, Aris Pagourtzis
In this paper, we study the problem of counting the number of different knapsack solutions with a prescribed cardinality. We present an FPTAS for this problem, based on dynamic pro…
Parameterized Fine-Grained Reductions
Elli Anastasiadi, Antonis Antonopoulos, Aris Pagourtzis +1
During recent years the field of fine-grained complexity has bloomed to produce a plethora of results, with both applied and theoretical impact on the computer science community. T…