Some complete and intermediate polynomials in algebraic complexity theory (Q1635814): Difference between revisions

Latest revision as of 05:04, 28 December 2024

scientific article; zbMATH DE number 6605932

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Language	Label	Description	Also known as
English	Some complete and intermediate polynomials in algebraic complexity theory	scientific article; zbMATH DE number 6605932	Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Statements

instance of

scholarly article

0 references

title

Some complete and intermediate polynomials in algebraic complexity theory (English)

0 references

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory (English)

0 references

0 references

0 references

Theory of Computing Systems

0 references

Computer Science – Theory and Applications

0 references

publication date

1 June 2018

0 references

25 July 2016

0 references

full work available at URL

https://arxiv.org/abs/1603.04606

0 references

zbMATH Keywords

completeness

0 references

VP

0 references

VNP-intermediate

0 references

VBP

0 references

homomorphisms

0 references

monotone projections

0 references

lower bounds

0 references

extension complexity

0 references

tree decomposition

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

The monotone circuit complexity of Boolean functions

0 references

On the extension complexity of combinatorial polytopes

0 references

Completeness and reduction in algebraic complexity theory

0 references

Q3836529

0 references

Cook's versus Valiant's hypothesis

0 references

The arithmetic complexity of tensor contractions

0 references

Parameterized Algorithms

0 references

A Dichotomy Theorem for Homomorphism Polynomials

0 references

Counting \(H-\)colorings of partial \(k-\)trees

0 references

Homomorphism Polynomials Complete for VP

0 references

Paths, Trees, and Flowers

0 references

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

0 references

Q4198056

0 references

Unifying known lower bounds via geometric complexity theory

0 references

Some Exact Complexity Results for Straight-Line Computations over Semirings

0 references

Turing machines that take advice

0 references

On the Structure of Polynomial Time Reducibility

0 references

Characterizing Valiant's algebraic complexity classes

0 references

Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

0 references

Q3002820

0 references

Q3758729

0 references

Lower bounds on monotone complexity of the logical permanent

0 references

The Matching Polytope has Exponential Extension Complexity

0 references

Fast Parallel Computation of Polynomials Using Few Processors

0 references

The complexity of partial derivatives

0 references

Conjunctive query containment revisited

0 references

The complexity of counting homomorphisms seen from the other side

0 references

Q2808529

0 references

Q4521549

0 references

Dichotomy Theorems for Homomorphism Polynomials of Graph Classes

0 references

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

0 references

Feasible arithmetic computations: Valiant's hypothesis

0 references

Q4602399

0 references

The complexity of homomorphism and constraint satisfaction problems seen from the other side

0 references

On the complexity of H-coloring

0 references

Treewidth. Computations and approximations

0 references

Some complete and intermediate polynomials in algebraic complexity theory

0 references

Arithmetic Circuits: A survey of recent results and open questions

0 references

Identifiers

zbMATH Open document ID

1393.68079

0 references

1385.68018

0 references

DOI

10.1007/978-3-319-34171-2_18

0 references

10.1007/S00224-016-9740-Y

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1635814

@@ Property / DOI @@
-.1007/s00224-016-9740-y
@@ Property / DOI: 10.1007/s00224-016-9740-y / rank @@
-Normal rank
@@ Property / DOI @@
+.1007/S00224-016-9740-Y
@@ Property / DOI: 10.1007/S00224-016-9740-Y / rank @@
+Normal rank
@@ Property / cites work @@
+The monotone circuit complexity of Boolean functions
+Normal rank
@@ Property / cites work @@
+On the extension complexity of combinatorial polytopes
+Normal rank
@@ Property / cites work @@
+Completeness and reduction in algebraic complexity theory
+Normal rank
@@ Property / cites work @@
+Q3836529
@@ Property / cites work: Q3836529 / rank @@
+Normal rank
@@ Property / cites work @@
+Cook's versus Valiant's hypothesis
@@ Property / cites work: Cook's versus Valiant's hypothesis / rank @@
+Normal rank
@@ Property / cites work @@
+The arithmetic complexity of tensor contractions
@@ Property / cites work: The arithmetic complexity of tensor contractions / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms
@@ Property / cites work: Parameterized Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+A Dichotomy Theorem for Homomorphism Polynomials
@@ Property / cites work: A Dichotomy Theorem for Homomorphism Polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Counting \(H-\)colorings of partial \(k-\)trees
@@ Property / cites work: Counting \(H-\)colorings of partial \(k-\)trees / rank @@
+Normal rank
@@ Property / cites work @@
+Homomorphism Polynomials Complete for VP
@@ Property / cites work: Homomorphism Polynomials Complete for VP / rank @@
+Normal rank
@@ Property / cites work @@
+Paths, Trees, and Flowers
@@ Property / cites work: Paths, Trees, and Flowers / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential Lower Bounds for Polytopes in Combinatorial Optimization
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Unifying known lower bounds via geometric complexity theory
+Normal rank
@@ Property / cites work @@
+Some Exact Complexity Results for Straight-Line Computations over Semirings
+Normal rank
@@ Property / cites work @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+On the Structure of Polynomial Time Reducibility
@@ Property / cites work: On the Structure of Polynomial Time Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+Characterizing Valiant's algebraic complexity classes
+Normal rank
@@ Property / cites work @@
+Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+Q3002820
@@ Property / cites work: Q3002820 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on monotone complexity of the logical permanent
+Normal rank
@@ Property / cites work @@
+The Matching Polytope has Exponential Extension Complexity
+Normal rank
@@ Property / cites work @@
+Fast Parallel Computation of Polynomials Using Few Processors
+Normal rank
@@ Property / cites work @@
+The complexity of partial derivatives
@@ Property / cites work: The complexity of partial derivatives / rank @@
+Normal rank
@@ Property / cites work @@
+Conjunctive query containment revisited
@@ Property / cites work: Conjunctive query containment revisited / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of counting homomorphisms seen from the other side
+Normal rank
@@ Property / cites work @@
+Q2808529
@@ Property / cites work: Q2808529 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4521549
@@ Property / cites work: Q4521549 / rank @@
+Normal rank
@@ Property / cites work @@
+Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
+Normal rank
@@ Property / cites work @@
+The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
+Normal rank
@@ Property / cites work @@
+Feasible arithmetic computations: Valiant's hypothesis
+Normal rank
@@ Property / cites work @@
+Q4602399
@@ Property / cites work: Q4602399 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of homomorphism and constraint satisfaction problems seen from the other side
+Normal rank
@@ Property / cites work @@
+On the complexity of H-coloring
@@ Property / cites work: On the complexity of H-coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Treewidth. Computations and approximations
@@ Property / cites work: Treewidth. Computations and approximations / rank @@
+Normal rank
@@ Property / cites work @@
+Some complete and intermediate polynomials in algebraic complexity theory
+Normal rank
@@ Property / cites work @@
+Arithmetic Circuits: A survey of recent results and open questions
+Normal rank