Monotone arithmetic complexity of graph homomorphism polynomials

DOI10.1007/s00453-023-01108-0MaRDI QIDQ6077890

C. S. Rahul, Balagopal Komarath, Anurag Pandey

Publication date: 27 September 2023

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

treewidthgraph algorithmsgraph homomorphismspathwidthalgebraic complexityalgebraic branching programsmonotone complexityalgebraic circuitstreedepthfine-grained complexityalgebraic formulashomomorphism polynomialsfixed-parameter algorithms and complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Finding and counting small induced subgraphs efficiently
• Lower bounds for monotone counting circuits
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• The complexity of counting homomorphisms seen from the other side
• The complexity of partial derivatives
• A lower bound on the number of additions in monotone computations
• Counting \(H-\)colorings of partial \(k-\)trees
• Some complete and intermediate polynomials in algebraic complexity theory
• Variants of homomorphism polynomials complete for algebraic complexity classes
• Generalized quasirandom graphs
• Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
• Counting and Detecting Small Subgraphs via Equations
• Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Homomorphisms are a good basis for counting small subgraphs
• LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
• Separating monotone VP and VNP
• Finding Four-Node Subgraphs in Triangle Time
• Detecting and Counting Small Pattern Graphs
• On the $AC^0$ Complexity of Subgraph Isomorphism
• Strongly Exponential Separation between Monotone VP and Monotone VNP
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• Quasi-random graphs
• Monotone circuit lower bounds from robust sunflowers
• Lower bounds for monotone arithmetic circuits via communication complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Monotone arithmetic complexity of graph homomorphism polynomials