Counting Classes

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra)

Project Description

This project studies counting classes. The term ``counting classes'' has come to refer to a certain collection of classes--such as #P, SPP, probabilistic classes, parity-based classes, etc.--that are defined in terms of the number of accepting paths of nondeterministic machines.

Among the questions central to this project are:

  1. How powerful are counting classes?
  2. What are the properties of counting classes?
  3. How robust are the definitions of counting classes?

Bibliography

1
This is a list of selected journal (except when the work has not yet appeared in journal/book form) papers, from or related to this project, by University of Rochester authors. Essentially all the papers listed below can be found, in their full technical report versions, in the UR-CS Technical Report Archive's theory section. Here is Lane's complete publication list and links to essentially all his conference and journal papers (and also his arxiv.org technical reports) can be found via the ``EE'' (electronic edition) links at Lane's entry at the DBLP project.

2
R. Beigel, L. Hemachandra, and G. Wechsung.
Probabilistic polynomial time is closed under parity reductions.
Information Processing Letters, 37(2):91-94, 1991.

3
B. Borchert, L. Hemaspaandra, and J. Rothe.
Restrictive acceptance suffices for equivalence problems.
London Mathematical Society Journal of Computation and Mathematics, 3:86-95, 2000.

4
J. Cai and L. Hemachandra.
On the power of parity polynomial time.
Mathematical Systems Theory, 23(2):95-106, 1990.

5
J. Cai and L. Hemachandra.
A note on enumerative counting.
Information Processing Letters, 38(4):215-219, 1991.

6
D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener.
Simultaneous strong separations of probabilistic and unambiguous complexity classes.
Mathematical Systems Theory, 25(1):23-36, 1992.

7
P. Faliszewski and L. Hemaspaandra.
The consequences of eliminating NP solutions.
Computer Science Review.
To appear.

8
P. Faliszewski and L. Hemaspaandra.
The complexity of power-index comparison
In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management, pages 177-187. Springer-Verlag Lecture Notes in Computer Science, June 2008.
To appear.

9
S. Fischer, L. Hemaspaandra, and L. Torenvliet.
Witness-isomorphic reductions and local search.
In A. Sorbi, editor, Complexity, Logic, and Recursion Theory, pages 207-223. Marcel Dekker, Inc., 1997.

10
J. Goldsmith, L. Hemachandra, D. Joseph, and P. Young.
Near-testable sets.
SIAM Journal on Computing, 20(3):506-523, 1991.

11
J. Goldsmith, L. Hemachandra, and K. Kunen.
Polynomial-time compression.
Computational Complexity, 2(1):18-39, 1992.

12
L. Hemachandra and A. Hoene.
On sets with efficient implicit membership tests.
SIAM Journal on Computing, 20(6):1148-1156, 1991.

13
L. Hemachandra and M. Ogiwara.
Is #P closed under subtraction?
In G. Rozenberg and A. Salomaa, editors, Current Trends in Theoretical Computer Science: Essays and Tutorials, pages 523-536. World Scientific, 1993.

14
L. Hemachandra and S. Rudich.
On the complexity of ranking.
Journal of Computer and System Sciences, 41(2):251-271, 1990.

15
L. Hemaspaandra, H. Hempel, and G. Wechsung.
Self-specifying machines.
International Journal of Foundations of Computer Science, 10(3):263-276, 1999.

16
L. Hemaspaandra, C. Homan, and S. Kosub.
Cluster computing and the power of edge recognition.
Information and Computation, 205(8):1274-1293, 2007.

17
L. Hemaspaandra, C. Homan, S. Kosub, and K. Wagner.
The complexity of computing the size of an interval.
SIAM Journal on Computing, 36(5):1264-1300, 2006-2007.

18
L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman.
Computing solutions uniquely collapses the polynomial hierarchy.
SIAM Journal on Computing, 25(4):697-708, 1996.

19
L. Hemaspaandra and M. Ogihara.
Universally serializable computation.
Journal of Computer and System Sciences, 55(3):547-560, 1997.

20
L. Hemaspaandra, M. Ogihara, and G. Wechsung.
Reducing the number of solutions of NP functions.
Journal of Computer and System Sciences, 64(2):311-328, 2002.

21
L. Hemaspaandra, M. Ogihara, M. Zaki, and M. Zimand.
The complexity of finding top-Toda-equivalence-class members.
Theory of Computing Systems, 39(5):669-684, 2006.

22
L. Hemaspaandra and J. Rothe.
A second step towards complexity-theoretic analogs of Rice's Theorem.
Theoretical Computer Science, 244(1-2):205-217, 2000.

23
L. Hemaspaandra and M. Thakur.
Lower bounds and the hardness of counting properties.
Theoretical Computer Science, 326(1-3):1-28, 2004.

24
L. Hemaspaandra and H. Vollmer.
The Satanic notations: Counting classes beyond #P and other definitional adventures.
SIGACT News, 26(1):2-13, 1995.

25
L. Hemaspaandra, M. Zaki, and M. Zimand.
Polynomial-time semi-rankable sets.
In Journal of Computing and Information, 2(1), Special Issue: Proceedings of the 8th International Conference on Computing and Information, pages 50-67, 1996.
CD-ROM ISSN 1201-8511/V2/#1.

26
M. Ogiwara and L. Hemachandra.
A complexity theory for feasible closure properties.
Journal of Computer and System Sciences, 46(3):295-325, 1993.

27
H. Spakowski, M. Thakur, and R. Tripathi.
Quantum and classical complexity classes: Separations, collapses, and closure properties.
Information and Computation, 200(1):1-34, 2005.

28
M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind.
Manipulating quota value in weighted voting games.
In Proceedings of the 23rd AAAI Conference on Artificial Intelligence. AAAI Press, July 2008.
To appear.
$\begin{tabular}{l}
{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\hline
\end{tabular}$

(Last modified: June 5, 2008.)


Lane A. Hemaspaandra