Monotone bounded-depth complexity of homomorphism polynomials
From MaRDI portal
No records found.
Cites work
- A lower bound on the number of additions in monotone computations
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- A near-optimal depth-hierarchy theorem for small-depth multilinear circuits
- Algebraic complexity classes
- Arithmetic circuits: a survey of recent results and open questions
- Arithmetic circuits: the chasm at depth four gets wider
- Can you beat treewidth?
- Characterizing Valiant's algebraic complexity classes
- Circuit Definitions of Nondeterministic Complexity Classes
- Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
- Conditional lower bounds for sparse parameterized 2-CSP: a streamlined proof
- Fast Parallel Computation of Polynomials Using Few Processors
- Homomorphism polynomials complete for VP
- Homomorphisms are a good basis for counting small subgraphs
- scientific article; zbMATH DE number 4053662 (Why is no real title available?)
- scientific article; zbMATH DE number 3692645 (Why is no real title available?)
- scientific article; zbMATH DE number 1222605 (Why is no real title available?)
- scientific article; zbMATH DE number 6820278 (Why is no real title available?)
- Title not available (Why is no real title available?)
- Improved bounds for reduction to depth 4 and depth 3
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
- Low-depth arithmetic circuit lower bounds: bypassing set-multilinearization
- Lower bounds based on the exponential time hypothesis
- Monotone arithmetic complexity of graph homomorphism polynomials
- Monotone circuit lower bounds from robust sunflowers
- Monotonicity of the cops and robber game for bounded depth treewidth
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Negation can be exponentially powerful
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- On \(\epsilon\)-sensitive monotone computations
- On the complexity of k-SAT
- Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs
- Separating monotone VP and VNP
- Some complete and intermediate polynomials in algebraic complexity theory
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Strongly Exponential Separation between Monotone VP and Monotone VNP
- Structural parameterizations of vertex integrity
- Superpolynomial lower bounds against low-depth algebraic circuits
- The complexity of computing the permanent
- The complexity of counting homomorphisms seen from the other side
- Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes
This page was built for publication: Monotone bounded-depth complexity of homomorphism polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310180)
