activity
20162023
most citedSelf-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds

2 citations · 2 across the 6 of their papers we have counts for

collaborators
Showing 2023Show all

1 paper · 1 filter

cs.CC2023

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…