Deterministic Constrained Multilinear Detection

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476146" target="_blank" >RIV/00216208:11320/23:10476146 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.MFCS.2023.25" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2023.25</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2023.25" target="_blank" >10.4230/LIPIcs.MFCS.2023.25</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Deterministic Constrained Multilinear Detection

Popis výsledku v původním jazyce

We extend the algebraic techniques of Brand and Pratt (ICALP&apos;21) for deterministic detection of k-multilinear monomials in a given polynomial with non-negative coefficients to the more general situation of detecting colored k-multilinear monomials that satisfy additional constraints on the multiplicities of the colors appearing in them. Our techniques can be viewed as a characteristic-zero generalization of the algebraic tools developed by Guillemot and Sikora (MFCS&apos;10) and Björklund, Kaski and Kowalik (STACS&apos;13) As applications, we recover the state-of-the-art deterministic algorithms for the Graph Motif problem due to Pinter, Schachnai and Zehavi (MFCS&apos;14), and give new deterministic algorithms for generalizations of certain questions on colored directed spanning trees or bipartite planar matchings running in deterministic time OASTERISK OPERATOR(4k), studied originally by Gutin, Reidl, Wahlström and Zehavi (J. Comp. Sys. Sci. 95,&apos;18). Finally, we give improved randomized algorithms for intersecting three and four matroids of rank k in characteristic zero, improving the record bounds of Brand and Pratt (ICALP&apos;21) from OASTERISK OPERATOR(64k) and OASTERISK OPERATOR(256k), respectively, to OASTERISK OPERATOR(4k).

Název v anglickém jazyce

Deterministic Constrained Multilinear Detection

Popis výsledku anglicky

We extend the algebraic techniques of Brand and Pratt (ICALP&apos;21) for deterministic detection of k-multilinear monomials in a given polynomial with non-negative coefficients to the more general situation of detecting colored k-multilinear monomials that satisfy additional constraints on the multiplicities of the colors appearing in them. Our techniques can be viewed as a characteristic-zero generalization of the algebraic tools developed by Guillemot and Sikora (MFCS&apos;10) and Björklund, Kaski and Kowalik (STACS&apos;13) As applications, we recover the state-of-the-art deterministic algorithms for the Graph Motif problem due to Pinter, Schachnai and Zehavi (MFCS&apos;14), and give new deterministic algorithms for generalizations of certain questions on colored directed spanning trees or bipartite planar matchings running in deterministic time OASTERISK OPERATOR(4k), studied originally by Gutin, Reidl, Wahlström and Zehavi (J. Comp. Sys. Sci. 95,&apos;18). Finally, we give improved randomized algorithms for intersecting three and four matroids of rank k in characteristic zero, improving the record bounds of Brand and Pratt (ICALP&apos;21) from OASTERISK OPERATOR(64k) and OASTERISK OPERATOR(256k), respectively, to OASTERISK OPERATOR(4k).

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í

2023

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

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-292-1

ISSN

1868-8969

e-ISSN

1868-8969

Počet stran výsledku

14

Strana od-do

1-14

Název nakladatele

Schloss-Dagstuhl - Leibniz Zentrum für Informatik

Místo vydání

Wadern

Místo konání akce

Bordeaux, France

Datum konání akce

28. 8. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—