{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:28:52Z","timestamp":1778128132798,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2018,9,18]],"date-time":"2018-09-18T00:00:00Z","timestamp":1537228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr?det","doi-asserted-by":"publisher","award":["VR 2016-03855"],"award-info":[{"award-number":["VR 2016-03855"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["338077"],"award-info":[{"award-number":["338077"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["National Science Foundation"],"award-info":[{"award-number":["National Science Foundation"]}]},{"name":"National Science Foundation","award":["CCF-1741615"],"award-info":[{"award-number":["CCF-1741615"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00453-018-0513-7","type":"journal-article","created":{"date-parts":[[2018,9,18]],"date-time":"2018-09-18T18:49:57Z","timestamp":1537296597000},"page":"4010-4028","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants"],"prefix":"10.1007","volume":"81","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,18]]},"reference":[{"issue":"4","key":"513_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0020-0190(96)00159-7","volume":"60","author":"ET Bax","year":"1996","unstructured":"Bax, E.T., Franklin, J.: A finite-difference sieve to count paths and cycles by length. Inf. Process. Lett. 60(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"513_CR2","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01171101","volume":"27","author":"AS Besicovitch","year":"1928","unstructured":"Besicovitch, A.S.: On Kakeya\u2019s problem and a similar one. Math. Z. 27(1), 312\u2013320 (1928)","journal-title":"Math. Z."},{"key":"513_CR3","unstructured":"Bj\u00f6rklund, A.: Below all subsets for some permutational counting problems. In: Proceedings of the 15th SWAT, vol. 17, pp. 1\u201311 (2016)"},{"key":"513_CR4","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.ipl.2017.04.015","volume":"125","author":"A Bj\u00f6rklund","year":"2017","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Lyckberg, I.: Computing the permanent modulo a prime power. Inf. Process. Lett. 125, 20\u201325 (2017)","journal-title":"Inf. Process. Lett."},{"key":"513_CR5","first-page":"391","volume":"2016","author":"A Bj\u00f6rklund","year":"2016","unstructured":"Bj\u00f6rklund, A., Kaski, P.: How proofs are prepared at Camelot: extended abstract. Proc. PODC 2016, 391\u2013400 (2016)","journal-title":"Proc. PODC"},{"key":"513_CR6","unstructured":"Bj\u00f6rklund, A., Kaski, P., Koutis, I.: Directed Hamiltonicity and out-branchings via generalized Laplacians. In: Proceedings of the 44th ICALP, vol. 91, pp. 1\u201314 (2017)"},{"key":"513_CR7","unstructured":"Chandrasekharan, S., Wiese, U.: Partition functions of strongly correlated electron systems as \u201cfermionants\u201d (2011). arXiv:1108.2461v1"},{"key":"513_CR8","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M.: Faster exponential-time algorithms in graphs of bounded average degree. In: Proceedings of the 40th ICALP, pp. 364\u2013375 (2013)","DOI":"10.1007\/978-3-642-39206-1_31"},{"issue":"077","key":"513_CR9","first-page":"1","volume":"16","author":"Z Dvir","year":"2009","unstructured":"Dvir, Z.: From randomness extraction to rotating needles. Electron. Colloq. Comput. Complex. 16(077), 1\u201319 (2009)","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"513_CR10","unstructured":"Dvir, Z.: Incidence theorems and their applications. (2012). arXiv:1208.5073"},{"issue":"3","key":"513_CR11","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1137\/140957123","volume":"45","author":"A Gupta","year":"2016","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Arithmetic circuits: a chasm at depth 3. SIAM J. Comput. 45(3), 1064\u20131079 (2016)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"513_CR12","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1137\/08073408X","volume":"40","author":"KS Kedlaya","year":"2011","unstructured":"Kedlaya, K.S., Umas, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767\u20131802 (2011)","journal-title":"SIAM J. Comput."},{"key":"513_CR13","volume-title":"The Art of Computer Programming, Volume 2: Seminumerical Algorithms","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston (1998)"},{"issue":"3","key":"513_CR14","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10801-011-0274-8","volume":"34","author":"S Kopparty","year":"2011","unstructured":"Kopparty, S., Lev, V.F., Saraf, S., Sudan, M.: Kakyea-type sets in finite vector spaces. J. Algebr. Combin. 34(3), 337\u2013355 (2011)","journal-title":"J. Algebr. Combin."},{"issue":"3","key":"513_CR15","doi-asserted-by":"crossref","first-page":"36","DOI":"10.37236\/3190","volume":"20","author":"G Kyureghyan","year":"2013","unstructured":"Kyureghyan, G., M\u00fcller, P., Wang, Q.: On the size of Kakeya sets in finite vector spaces. Electron. J. Combin. 20(3), 36 (2013)","journal-title":"Electron. J. Combin."},{"key":"513_CR16","first-page":"10","volume":"99","author":"JM Landsberg","year":"2016","unstructured":"Landsberg, J.M.: An introduction to geometric complexity theory. Eur. Math. Soc. Newsl. 99, 10\u201318 (2016)","journal-title":"Eur. Math. Soc. Newsl."},{"key":"513_CR17","volume-title":"Finite Fields","author":"R Lidl","year":"1997","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields, 2nd edn. Cambridge University Press, Cambridge (1997)","edition":"2"},{"issue":"4","key":"513_CR18","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, Noam: Algebraic methods for interactive proof systems. J. ACM 39(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"key":"513_CR19","unstructured":"Mertens, S., Moore, C.: The complexity of the fermionant, and immanants of constant width (2011). arXiv:1110.1821"},{"issue":"1","key":"513_CR20","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1215\/S0012-7094-04-12112-8","volume":"121","author":"G Mockenhaupt","year":"2004","unstructured":"Mockenhaupt, G., Tao, T.: Restriction and Kakeya phenomena for finite fields. Duke Math. J. 121(1), 35\u201374 (2004)","journal-title":"Duke Math. J."},{"key":"513_CR21","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440147","volume-title":"Combinatorial Mathematics","author":"HJ Ryser","year":"1963","unstructured":"Ryser, H.J.: Combinatorial Mathematics. Mathematical Association of America, Washington D.C. (1963)"},{"issue":"3","key":"513_CR22","doi-asserted-by":"publisher","first-page":"375","DOI":"10.2140\/apde.2008.1.375","volume":"1","author":"S Saraf","year":"2008","unstructured":"Saraf, S., Sudan, M.: An improved lower bound on the size of Kakeya sets over finite fields. Anal. PDE 1(3), 375\u2013379 (2008)","journal-title":"Anal. PDE"},{"key":"513_CR23","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/163","volume-title":"Introduction to Analytic and Probabilistic Number Theory","author":"G Tenenbaum","year":"2015","unstructured":"Tenenbaum, G.: Introduction to Analytic and Probabilistic Number Theory, 3rd edn. American Mathematical Society, Washington D.C. (2015)","edition":"3"},{"key":"513_CR24","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proceedings of the 11th STOC, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"key":"513_CR25","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"513_CR26","doi-asserted-by":"crossref","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 3rd edn. Cambridge University Press, Cambridge (2013)","DOI":"10.1017\/CBO9781139856065"},{"key":"513_CR27","unstructured":"Williams, R.R: Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. In: Proceedings of the 31st CCC, vol. 2, pp. 1\u201317 (2016)"},{"key":"513_CR28","unstructured":"Wolff, T.: Recent work connected with the Kakeya problem. In: Rossi, H. (ed.) Prospects in Mathematics (Princeton, NJ, 1996), American Mathematical Society, Washington D.C., pp. 129\u2013162 (1999)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0513-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0513-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0513-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T21:36:28Z","timestamp":1662068188000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0513-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,18]]},"references-count":28,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["513"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0513-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,18]]},"assertion":[{"value":"31 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}