Fine-grained reductions from approximate counting to decision
In this paper, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witnesses with minimal overhead.) This mirrors a found...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Udgivet: |
Association for Computing Machinery
2018
|