{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T04:27:07Z","timestamp":1783225627034,"version":"3.54.6"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,11,28]],"date-time":"2019-11-28T00:00:00Z","timestamp":1574899200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,28]],"date-time":"2019-11-28T00:00:00Z","timestamp":1574899200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00224-019-09941-z","type":"journal-article","created":{"date-parts":[[2019,11,28]],"date-time":"2019-11-28T03:02:49Z","timestamp":1574910169000},"page":"374-399","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Computing Hitting Set Kernels By AC0-Circuits"],"prefix":"10.1007","volume":"64","author":[{"given":"Max","family":"Bannach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3946-8028","authenticated-orcid":false,"given":"Till","family":"Tantau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,11,28]]},"reference":[{"issue":"3","key":"9941_CR1","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00453-006-1214-1","volume":"45","author":"FN Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Langston, M.A., Shanbhag, P., Symons, C.T.: Scalable parallel algorithms for fpt problems. Algorithmica 45(3), 269\u2013284 (2006)","journal-title":"Algorithmica"},{"issue":"4","key":"9941_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"9941_CR3","unstructured":"Bannach, M., Stockhusen, C., Tantau, T.: Fast parallel fixed-parameter algorithms via color coding. In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), pp. 224\u2013235 (2015)"},{"key":"9941_CR4","unstructured":"Bannach, M., Tantau, T.: Parallel multivariate meta-theorems. In: Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), pp. 4:1\u20134:17 (2016)"},{"key":"9941_CR5","unstructured":"Bannach, M., Tantau, T.: Computing Kernels in parallel: lower and upper bounds. In: Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), pp. 13:1\u201313:14 (2018)"},{"key":"9941_CR6","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC1. In: Proceedings of the 3rd Annual Structure in Complexity Theory Conference, pp. 47\u201359 (1988)","DOI":"10.1109\/SCT.1988.5262"},{"issue":"1","key":"9941_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R. G., Fellows, M.R.: Advice classes of parameterized tractability. Ann. Pure Appl. Logic 84(1), 119\u2013138 (1997)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9941_CR8","doi-asserted-by":"crossref","unstructured":"Cesati, M., Di Ianni, M.: Parameterized parallel complexity. In: Proceedings of the 4th International Euro-Par Conference, vol. 1470 of Lecture Notes in Computer Science, pp. 892\u2013896. Springer (1998)","DOI":"10.1007\/BFb0057945"},{"key":"9941_CR9","unstructured":"Chen, Y., Flum, J.: Some lower bounds in parameterized AC0. In: Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), pp. 27:1\u201327:14 (2016)"},{"key":"9941_CR10","unstructured":"Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: Proceedings of the 18th IEEE Conference on Computational Complexity (CCC 2003), pp. 13\u201329. IEEE Computer Society (2003)"},{"key":"9941_CR11","unstructured":"Chen, Y., Flum, J., Huang, X.: Slicewise definability in first-order logic with bounded quantifier rank. In: Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, (CSL 2017), August 20\u201324. Stockholm, Sweden, pp. 19:1\u201319:16 (2017)"},{"key":"9941_CR12","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput. 24, 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9941_CR13","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2014","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space complexity of parameterized problems: Classes and completness. Algorithmica 71(3), 661\u2013701 (2014)","journal-title":"Algorithmica"},{"issue":"1","key":"9941_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"1","author":"P Erdo\u030bs","year":"1960","unstructured":"Erdo\u030bs, P., Rado, R.: Intersection theorems for systems of sets. J. Lond. Math. Soc. 1(1), 85\u201390 (1960)","journal-title":"J. Lond. Math. Soc."},{"key":"9941_CR15","doi-asserted-by":"crossref","unstructured":"Flum, J., Grohe, M.: Describing parameterized complexity classes. In: Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2002), vol. 2285 of Lecture Notes in Computer Science, pp. 359\u2013371. Springer (2002)","DOI":"10.1007\/3-540-45841-7_29"},{"key":"9941_CR16","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Texts in Theoretical Computer Science. Springer (2006)"},{"issue":"1","key":"9941_CR17","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3-hitting set. J. Discrete Algoritms 1(1), 89\u2013102 (2003)","journal-title":"J. Discrete Algoritms"},{"key":"9941_CR18","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Siebertz, S., Toru\u0144czyk, S.: Parameterized circuit complexity of model-checking on sparse structures. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, (LICS 2018), pp 789\u2013798. ACM, New York (2018)","DOI":"10.1145\/3209108.3209136"},{"issue":"1","key":"9941_CR19","first-page":"129","volume":"70","author":"R van Bevern","year":"2014","unstructured":"van Bevern, R.: Towards optimal and expressive kernelization for d-hitting set. Algorithmica 70(1), 129\u2013147 (2014)","journal-title":"Algorithmica"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09941-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09941-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09941-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T00:59:02Z","timestamp":1606438742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09941-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,28]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9941"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09941-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,28]]},"assertion":[{"value":"28 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}