Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with counting classes:
TR97-036 | 1st August 1997
Meena Mahajan, V. Vinay

Determinant: Combinatorics, Algorithms, and Complexity

We prove a new combinatorial characterization of the
determinant. The characterization yields a simple
combinatorial algorithm for computing the
determinant. Hitherto, all (known) algorithms for
determinant have been based on linear algebra. Our
combinatorial algorithm requires no division and works over
arbitrary commutative rings. It also lends itself to
more >>>

TR02-036 | 30th May 2002
Stephen A. Fenner

PP-lowness and a simple definition of AWPP

We show that the counting classes AWPP and APP [Li 1993] are more robust
than previously thought. Our results identify asufficient condition for
a language to be low for PP, and we show that this condition is at least
as weak as other previously studied criteria. Our results imply that
more >>>

TR05-024 | 8th February 2005
Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>

TR07-087 | 11th July 2007
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Arithmetizing classes around NC^1 and L

The parallel complexity class NC^1 has many equivalent models such as
polynomial size formulae and bounded width branching
programs. Caussinus et al. \cite{CMTV} considered arithmetizations of
two of these classes, #NC^1 and #BWBP. We further this study to
include arithmetization of other classes. In particular, we show that
counting paths ... more >>>

TR09-009 | 18th December 2008
T.C. Vijayaraghavan

Checking Equality of Matroid Linear Representations and the Cycle Matching Problem

Revisions: 2

Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given ... more >>>

TR10-101 | 25th June 2010
Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

Counting Classes and the Fine Structure between NC$^1$ and L.

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

TR10-103 | 28th June 2010
Andreas Krebs, Nutan Limaye, Meena Mahajan

Counting paths in VPA is complete for \#NC$^1$

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>

ISSN 1433-8092 | Imprint