Content

•  
   Dedication
•  
   Abstract
•  
   Zusammenfassung
•  
   Acknowledgments
•  
   Contents
•  
  1 Introduction
•  
   1.1 Part i: Counting solutions to conjunctive queries
•  
   1.1.1 Structural restrictions for tractable #CQ
•  
   1.2 Part ii: Understanding arithmetic circuit classes
•  
   1.2.1 Conjunctive queries and arithmetic circuits
•  
   1.2.2 Graph polynomials on bounded treewidth graphs
•  
   1.2.3 Modifying arithmetic branching programs
•  
   1.3 Part iii: Monomials in arithmetic circuits
•  
   1.4 Overview over the thesis
•  
   Counting Solutions to Conjunctive Queries
•  
  2 Preliminaries
•  
   2.1 Conjunctive queries
•  
   2.1.1 Model of computation and encoding of instances
•  
   2.1.2 Query problems
•  
   2.2 Parameterized complexity
•  
  2.3 Graph and hypergraph decompositions
•  
   2.3.1 Treewidth
•  
   2.3.2 Hypergraph decomposition techniques
•  
  3 The complexity of #CQ and quantified star size
•  
   3.1 The complexity of #CQ
•  
   3.2 Quantified star size
•  
   3.3 Formulation of main results
•  
   3.4 Digression: Unions of acyclic queries
•  
  4 Computing S-star size
•  
   4.1 Acyclic hypergraphs
•  
   4.2 General hypergraphs
•  
   4.2.1 Exact computation
•  
   4.2.2 Parameterized complexity
•  
   4.2.3 Approximation
•  
  5 Quantified star size is sufficient and necessary for efficient counting
•  
   5.1 Bounded quantified star size is necessary
•  
   5.2 The complexity of counting
•  
   5.3 A #P-intermediate class of counting problems
•  
   5.4 Fractional Hypertree width
•  
  6 Queries of Bounded Arity
•  
   6.1 A characterization by treewidth and S-star size
•  
   6.2 A characterization by elimination orders
•  
  7 Tractable conjunctive queries and cores
•  
   7.1 Warmup: An improved hardness result for #CQ on star-shaped queries
•  
   7.2 Homomorphisms between structures and cores
•  
   7.3 Tractable conjunctive queries and cores
•  
   8 Conclusion
•  
   Understanding Arithmetic Circuit Classes
•  
  9 Introduction and preliminaries
•  
   9.1 Introduction
•  
   9.2 Some background on arithmetic circuit complexity
•  
   9.3 Digression: Reduction notions in arithmetic circuit complexity
•  
   10 Constraint Satisfaction Problems, Conjunctive Queries and Arithmetic Circuit Classes
•  
   10.1 Polynomials defined by conjunctive queries
•  
   10.2 Main results
•  
  10.3 Characterizations of VNP
•  
   10.3.1 Instances of unrestricted structure
•  
   10.3.2 Acyclic instances with quantification
•  
   10.3.3 Unions and intersections of ACQ-instances
•  
   10.4 Lower bounds for instances of bounded width
•  
   10.5 Constructing circuits for conjunctive queries
•  
   10.5.1 The relation bounded case
•  
  11 Graph Polynomials on Bounded Treewidth Graphs
•  
   11.1 Introduction
•  
  11.2 Monadic second order logic, generating functions and universality
•  
   11.2.1 Monadic second order logic on graphs
•  
   11.2.2 Generating functions
•  
   11.2.3 Treewidth preserving reductions and universality
•  
   11.3 Cliques are not universal
•  
  11.4 VPE-universality for bounded treewidth
•  
   11.4.1 Formulation of the results and outline
•  
   11.4.2 Reduction: phiCC leBW phiPCC
•  
   11.4.3 phiCC and phiPCC on bounded degree graphs
•  
   11.4.4 The lower bound for phiIS
•  
   11.4.5 Reduction: phiIS leBW phiVC
•  
   11.4.6 Reduction: phiVC leBW phiDS
•  
   11.4.7 The upper bounds
•  
   11.5 Conclusion
•  
  12 Arithmetic Branching Programs with Memory
•  
   12.1 Introduction
•  
   12.2 Arithmetic branching programs
•  
   12.3 Stack branching programs
•  
   12.3.1 Definition
•  
   12.3.2 Characterizing VP
•  
   12.3.3 Stack branching programs with few stack symbol
•  
   12.3.4 Width reduction
•  
   12.3.5 Depth reduction
•  
  12.4 Random access memory
•  
   12.4.1 Definition
•  
   12.4.2 Characterizing VNP
•  
   Monomials in Arithmetic Circuits
•  
  13 Introduction and preliminaries
•  
   13.1 Introduction
•  
   13.2 Preliminaries
•  
  14 Monomials in Arithmetic Circuits
•  
   14.1 Zero monomial coefficient
•  
   14.2 Counting monomials
•  
   14.3 Multilinearity
•  
   14.4 Univariate circuits
•  
   14.5 Conclusion
•  
   Appendix
•  
  A The proofs for fractional hypertree width
•  
   A.1 Tractable counting
•  
   A.2 Computing independents sets
•  
   Bibliography
•  
   Index
•  
   Declaration