{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:13:45Z","timestamp":1781345625145,"version":"3.54.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T00:00:00Z","timestamp":1520812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006475","name":"Bergen Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council through ERC","award":["715744 (PaPaAlg), 267959 and 306992 (PARAPPROX)"],"award-info":[{"award-number":["715744 (PaPaAlg), 267959 and 306992 (PARAPPROX)"]}]},{"name":"University of Bergen through project \u201cBeHard\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>M<\/jats:italic>\n            =(\n            <jats:italic>E<\/jats:italic>\n            ,\n            <jats:italic>I<\/jats:italic>\n            ) be a matroid of rank\n            <jats:italic>n<\/jats:italic>\n            . A\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:italic>truncation<\/jats:italic>\n            of\n            <jats:italic>M<\/jats:italic>\n            is a matroid\n            <jats:italic>M<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            =(\n            <jats:italic>E<\/jats:italic>\n            ,\n            <jats:italic>I<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            ) such that for any\n            <jats:italic>A<\/jats:italic>\n            \u2286\n            <jats:italic>E<\/jats:italic>\n            ,\n            <jats:italic>A<\/jats:italic>\n            \u2208 \u2208\n            <jats:italic>I<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            if and only if |\n            <jats:italic>A<\/jats:italic>\n            |\u2264\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>A<\/jats:italic>\n            \u2208\n            <jats:italic>I<\/jats:italic>\n            . Given a linear representation,\n            <jats:italic>A<\/jats:italic>\n            , of\n            <jats:italic>M<\/jats:italic>\n            , we consider the problem of finding a linear representation,\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            , of the\n            <jats:italic>k<\/jats:italic>\n            -truncation of\n            <jats:italic>M<\/jats:italic>\n            . A common way to compute\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            is to multiply the matrix\n            <jats:italic>A<\/jats:italic>\n            with a random\n            <jats:italic>k<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrix, yielding a simple randomized algorithm. Thus, a natural question is whether we can compute\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>deterministically<\/jats:italic>\n            . In this article, we settle this question for matrices over any field in which the field operations can be done efficiently. This includes any finite field and the field of rational numbers (Q).\n          <\/jats:p>\n          <jats:p>\n            Our algorithms are based on the properties of the classical Wronskian determinant, and the folded Wronskian determinant, which was recently introduced by Guruswami and Kopparty [23, 24] and Forbes and Shpilka [14]. Our main conceptual contribution in this article is to show that the Wronskian determinant can also be used to obtain a representation of the truncation of a linear matroid in deterministic polynomial time. An important application of our result is a deterministic algorithm to compute representative sets over linear matroids, which derandomizes a result of Fomin et al. [11, 12]. This result derandomizes several parameterized algorithms, including an algorithm for \u2113-M\n            <jats:sc>atroid<\/jats:sc>\n            P\n            <jats:sc>arity<\/jats:sc>\n            to which several problems, such as \u2113-M\n            <jats:sc>atroid<\/jats:sc>\n            I\n            <jats:sc>ntersection<\/jats:sc>\n            , can be reduced.\n          <\/jats:p>","DOI":"10.1145\/3170444","type":"journal-article","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T12:49:54Z","timestamp":1520858994000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Deterministic Truncation of Linear Matroids"],"prefix":"10.1145","volume":"14","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences and University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,3,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12166"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_17"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01904851"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4169\/000298910x515785"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9667-x"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.40"},{"key":"e_1_2_1_8_1","volume-title":"Golovach","author":"Fomin Fedor V.","year":"2013","unstructured":"Fedor V. Fomin and Petr A . Golovach . 2013 . Long circuits and large euler subgraphs. In Proceedings of ESA\u2019 13, Vol. 8125 . 493--504. Fedor V. Fomin and Petr A. Golovach. 2013. Long circuits and large euler subgraphs. In Proceedings of ESA\u201913, Vol. 8125. 493--504."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.07.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_37"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634084"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213995"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80025-5"},{"key":"e_1_2_1_16_1","volume-title":"Deterministic Extraction From Weak Random Sources","author":"Gabizon Ariel","unstructured":"Ariel Gabizon . 2011. Deterministic Extraction From Weak Random Sources . Springer . Ariel Gabizon. 2011. Deterministic Extraction From Weak Random Sources. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2259-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01170848"},{"key":"e_1_2_1_20_1","volume-title":"Algebraic Functions and Projective Curves","author":"Goldschmidt David","unstructured":"David Goldschmidt . 2003. Algebraic Functions and Projective Curves . Vol. 215 . Springer . David Goldschmidt. 2003. Algebraic Functions and Projective Curves. Vol. 215. Springer."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of FSTTCS\u201913","author":"Goyal Prachi","year":"2013","unstructured":"Prachi Goyal , Neeldhara Misra , and Fahad Panolan . 2013 . Faster deterministic algorithms for r-dimensional matching using representative sets . In Proceedings of FSTTCS\u201913 . 237--248. Prachi Goyal, Neeldhara Misra, and Fahad Panolan. 2013. Faster deterministic algorithms for r-dimensional matching using representative sets. In Proceedings of FSTTCS\u201913. 237--248."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of FSTTCS\u201915","author":"Goyal Prachi","year":"2015","unstructured":"Prachi Goyal , Pranabendu Misra , Fahad Panolan , Geevarghese Philip , and Saket Saurabh . 2015 . Finding even subgraphs even faster . In Proceedings of FSTTCS\u201915 . 434--447. Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. 2015. Finding even subgraphs even faster. In Proceedings of FSTTCS\u201915. 434--447."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.71"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3169-1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095124"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Daniel Lokshtanov Pranabendu Misra Fahad Panolan and Saket Saurabh. 2014. Deterministic truncation of linear matroids. arXiv:1404.4506.  Daniel Lokshtanov Pranabendu Misra Fahad Panolan and Saket Saurabh. 2014. Deterministic truncation of linear matroids. arXiv:1404.4506.","DOI":"10.1007\/978-3-662-47672-7_75"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_75"},{"key":"e_1_2_1_30_1","volume-title":"Combinatorial Surveys","author":"Lov\u00e1sz L.","unstructured":"L. Lov\u00e1sz . 1977. Flats in matroids and geometric graphs . In Combinatorial Surveys . Academic Press , London, UK , 45--86. L. Lov\u00e1sz. 1977. Flats in matroids and geometric graphs. In Combinatorial Surveys. Academic Press, London, UK, 45--86."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"e_1_2_1_32_1","volume-title":"A Treatise on the Theory of Determinants","author":"Muir Thomas","unstructured":"Thomas Muir . 1882. A Treatise on the Theory of Determinants . Dover Publications . Thomas Muir. 1882. A Treatise on the Theory of Determinants. Dover Publications."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(02)00139-6"},{"key":"e_1_2_1_34_1","volume-title":"Matrices and Matroids for Systems Analysis","author":"Murota Kazuo","unstructured":"Kazuo Murota . 2000. Matrices and Matroids for Systems Analysis . Vol. 20 . Springer . Kazuo Murota. 2000. Matrices and Matroids for Systems Analysis. Vol. 20. Springer."},{"key":"e_1_2_1_35_1","volume-title":"Matroid Theory","author":"Oxley James G","unstructured":"James G Oxley . 2006. Matroid Theory . Vol. 3 . Oxford University Press . James G Oxley. 2006. Matroid Theory. Vol. 3. Oxford University Press."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_65"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21944"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100293"},{"key":"e_1_2_1_39_1","first-page":"1196","article-title":"On primitive elements in finite fields and on elliptic curves","volume":"181","author":"Shparlinski Igor Evgen\u2019evich","year":"1990","unstructured":"Igor Evgen\u2019evich Shparlinski . 1990 . On primitive elements in finite fields and on elliptic curves . Mat. Sb. 181 , 9, 1196 -- 1206 . Igor Evgen\u2019evich Shparlinski. 1990. On primitive elements in finite fields and on elliptic curves. Mat. Sb. 181, 9, 1196--1206.","journal-title":"Mat. Sb."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3170444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:57Z","timestamp":1750213617000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,12]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3170444"],"URL":"https:\/\/doi.org\/10.1145\/3170444","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,12]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}