Counting Vanishing Matrix-Vector Products

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10494667" target="_blank" >RIV/00216208:11320/24:10494667 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-981-97-0566-5_24" target="_blank" >https://doi.org/10.1007/978-981-97-0566-5_24</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-981-97-0566-5_24" target="_blank" >10.1007/978-981-97-0566-5_24</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Counting Vanishing Matrix-Vector Products

Popis výsledku v původním jazyce

Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let v is an element of Q(d) be a rational vector, (T-1, T-2... T-m) a list of d x d rational matrices, S is an element of Q(hxd) a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices T-i1, T-i2,..., T-ik from the list such that STik center dot center dot center dot T(i1)v = 0 is an element of Q(h). In this paper, we show that this problem is #W[2]-hard for parameter k. As a consequence, computing the k-th homotopy group of a d-dimensional 1-connected topological space for d &gt; 3 is #W[2]-hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show W[1]/W[2]-hardness. This is in contrast to the parameterized k-sum problem, which is only W[1]-hard (Abboud-Lewi-Williams, ESA&apos;14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized by the matrix dimensions and the order of the field.

Název v anglickém jazyce

Counting Vanishing Matrix-Vector Products

Popis výsledku anglicky

Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let v is an element of Q(d) be a rational vector, (T-1, T-2... T-m) a list of d x d rational matrices, S is an element of Q(hxd) a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices T-i1, T-i2,..., T-ik from the list such that STik center dot center dot center dot T(i1)v = 0 is an element of Q(h). In this paper, we show that this problem is #W[2]-hard for parameter k. As a consequence, computing the k-th homotopy group of a d-dimensional 1-connected topological space for d &gt; 3 is #W[2]-hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show W[1]/W[2]-hardness. This is in contrast to the parameterized k-sum problem, which is only W[1]-hard (Abboud-Lewi-Williams, ESA&apos;14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized by the matrix dimensions and the order of the field.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2024

ISBN

978-981-9705-65-8

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

335-349

Název nakladatele

SPRINGER-VERLAG SINGAPORE PTE LTD

Místo vydání

SINGAPORE

Místo konání akce

Kanazawa

Datum konání akce

18. 3. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001207267500024