Source author record

Eleni Bakali

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Characterizations and approximability of hard counting classes below #P

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, is of key importance, as it contains self-reducible counting problems with easy decision version, thus eligible to be approximable. Indeed, most problems known so far to admit an fpras fall into this class. An open question raised recently by the community of descriptive complexity is to find a logical characterization of TotP and of robust subclasses of TotP. In this work we define two subclasses of TotP, in terms of descriptive complexity, both of which are robust in the sense that they have natural complete problems, which are defined in terms of satisfiability of Boolean formulae. We then explore the relationship between the class of approximable counting problems and TotP. We prove that TotP $\nsubseteq$ FPRAS if and only if NP $\neq$ RP and FPRAS $\nsubseteq$ TotP unless RP = P. To this end we introduce two ancillary classes that can both be seen as counting versions of RP. We further show that FPRAS lies between one of these classes and a counting version of BPP. Finally, we provide a complete picture of inclusions among all the classes defined or discussed in this paper with respect to different conjectures about the NP vs. RP vs. P questions.

preprint2016arXiv

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

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 of the function $f(x)$ is zero. For example, $\#$ independent-sets of all sizes, is such a problem, and one of the hardest of this class, since it is equivalent to $\#$ SAT under multiplicative approximation preserving reductions. Using these two powerful properties, self reducibility and easy decision, we prove that all problems/ functions $f$ in this class can be approximated in probabilistic polynomial time within an absolute exponential error $ε\cdot 2^{n'}, \forallε>0$ , which for many of those problems (when $n'=n+$ constant) implies additive approximation to the fraction $f(x)/2^n$ . (Where $n'$ is the amount of non-determinism of some associated NPTM). Moreover we show that for all these problems we can have multiplicative error to the value $f(x)$ , of any desired accuracy (i.e. a RAS), in time of order $2^{2n'/3}poly(n)$ , which is strictly smaller than exhaustive search. We also show that $f(x)<g(x)$ can be decided deterministically in time $g(x)poly(n), \forall g$ . Finally we show that the Circuit Acceptance Probability Problem, which is related to derandomization and circuit lower bounds, can be solved with high probability and in polynomial time, for the family of all circuits for which the problems of counting either satisfying or unsatisfying assignments belong to TotP (which is the Karp-closure of self reducible problems with easy decision version).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.