Variants of the Determinant Polynomial and the VP-Completeness

Nutan Limaye; Prasad Chaugule; Shourya Pandey

doi:10.1007/978-3-030-79416-3_3

Variants of the Determinant Polynomial and the VP-Completeness

Nutan Limaye
, Prasad Chaugule
, Shourya Pandey

Indian Institute of Technology Bombay

Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review

Abstract

The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call StackDetn(X) and CountDetn(X) and show that they are VP and VNP complete respectively under p-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely clow sequences, by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).

Original language	English
Book series	Lecture Notes in Computer Science
Volume	12730
Pages (from-to)	31-55
Number of pages	25
DOIs	https://doi.org/10.1007/978-3-030-79416-3_3
Publication status	Published - 18 Jul 2021
Externally published	Yes
Event	International Computer Science Symposium in Russia - Sochi, Russian Federation Duration: 28 Jun 2021 → 2 Jul 2021 Conference number: 2021

Conference

Conference	International Computer Science Symposium in Russia
Number	2021
Country/Territory	Russian Federation
City	Sochi
Period	28/06/2021 → 02/07/2021

Keywords

Algebraic Circuits
VP-Completeness
Determinant family

Access to Document

10.1007/978-3-030-79416-3_3Licence: Unspecified

Cite this

@inproceedings{ea622232e4994830ab83c48f570fa1b8,

title = "Variants of the Determinant Polynomial and the VP-Completeness",

abstract = "The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call StackDetn(X) and CountDetn(X) and show that they are VP and VNP complete respectively under p-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely clow sequences, by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).",

keywords = "Algebraic Circuits, VP-Completeness, Determinant family",

author = "Nutan Limaye and Prasad Chaugule and Shourya Pandey",

note = "Doesn't seem to count as OA? (jcg: 14/02/2022) ; International Computer Science Symposium in Russia, CSR ; Conference date: 28-06-2021 Through 02-07-2021",

year = "2021",

month = jul,

day = "18",

doi = "10.1007/978-3-030-79416-3\_3",

language = "English",

volume = "12730",

pages = "31--55",

journal = "Lecture Notes in Computer Science",

issn = "1611-3349",

publisher = "Springer",

}

TY - GEN

T1 - Variants of the Determinant Polynomial and the VP-Completeness

AU - Limaye, Nutan

AU - Chaugule, Prasad

AU - Pandey, Shourya

N1 - Conference code: 2021

PY - 2021/7/18

Y1 - 2021/7/18

N2 - The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call StackDetn(X) and CountDetn(X) and show that they are VP and VNP complete respectively under p-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely clow sequences, by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).

AB - The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call StackDetn(X) and CountDetn(X) and show that they are VP and VNP complete respectively under p-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely clow sequences, by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).

KW - Algebraic Circuits

KW - VP-Completeness

KW - Determinant family

U2 - 10.1007/978-3-030-79416-3_3

DO - 10.1007/978-3-030-79416-3_3

M3 - Conference article

SN - 1611-3349

VL - 12730

SP - 31

EP - 55

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - International Computer Science Symposium in Russia

Y2 - 28 June 2021 through 2 July 2021

ER -

Variants of the Determinant Polynomial and the VP-Completeness

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this