Deterministic Constrained Multilinear Detection

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Deterministic Constrained Multilinear Detection
Original language description
We extend the algebraic techniques of Brand and Pratt (ICALP'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'10) and Björklund, Kaski and Kowalik (STACS'13) As applications, we recover the state-of-the-art deterministic algorithms for the Graph Motif problem due to Pinter, Schachnai and Zehavi (MFCS'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,'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'21) from OASTERISK OPERATOR(64k) and OASTERISK OPERATOR(256k), respectively, to OASTERISK OPERATOR(4k).
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-292-1
ISSN
1868-8969
e-ISSN
1868-8969
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss-Dagstuhl - Leibniz Zentrum für Informatik
Place of publication
Wadern
Event location
Bordeaux, France
Event date
Aug 28, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)