Search

We investigate the algebraic complexity of tensor calculus. We consider a generalization of iterated matrix product to tensors and show that the resulting formulas exactly capture V P, the class of polynomial families efficiently computable by arithmetic circuits. This gives a natural and robust characterization of this complexity class that despite its naturalness is not very well understood so far. [ABSTRACT FROM AUTHOR]

We explore the complexity of counting solutions to conjunctive queries, a basic class of queries from database theory. We introduce a parameter, called the quantified star size of a query ϕ, which measures how the free variables are spread in ϕ. As usual in database theory, we associate a hypergraph to a query ϕ. We show that for classes of queries for which these associated hypergraphs admit good decompositions, e.g., bounded width generalized hypertree decompositions, bounded quantified star size exactly characterizes the subclasses of hypergraphs for which counting the number of solutions is tractable. In the case of bounded arity, this allows us to fully characterize the classes of hypergraphs for which counting the solutions is tractable. Finally, we also analyze the complexity of computing the quantified star size of a conjunctive query. [ABSTRACT FROM AUTHOR]