{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T15:03:51Z","timestamp":1746803031183},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,6,24]],"date-time":"2012-06-24T00:00:00Z","timestamp":1340496000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00224-012-9415-2","type":"journal-article","created":{"date-parts":[[2012,7,7]],"date-time":"2012-07-07T16:20:43Z","timestamp":1341678043000},"page":"719-728","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Complexity of Satisfying Almost All Linear Equations over $\\mathbb{F}_{2}$"],"prefix":"10.1007","volume":"52","author":[{"given":"R.","family":"Crowston","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Gutin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Yeo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,6,24]]},"reference":[{"issue":"3","key":"9415_CR1","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N. Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61(3), 638\u2013655 (2011)","journal-title":"Algorithmica"},{"key":"9415_CR2","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.jalgor.2003.09.003","volume":"50","author":"N. Alon","year":"2004","unstructured":"Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. J. Algorithms 50, 118\u2013131 (2004)","journal-title":"J. Algorithms"},{"key":"9415_CR3","first-page":"229","volume-title":"Proc. FSTTCS 2011","author":"R. Crowston","year":"2011","unstructured":"Crowston, R., Fellows, M., Gutin, G., Jones, M., Rosamond, F., Thomass\u00e9, S., Yeo, A.: Simultaneously satisfying linear equations over $\\mathbb {F}_{2}$ : MaxLin2 and Max-r-Lin2 parameterized above average. In: Proc. FSTTCS 2011, pp. 229\u2013240 (2011)"},{"key":"9415_CR4","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/978-3-642-13731-0_17","volume-title":"SWAT 2010","author":"R. Crowston","year":"2010","unstructured":"Crowston, R., Gutin, G., Jones, M., Kim, E.J., Ruzsa, I.: Systems of linear equations over $\\mathbb{F}_{2}$ and problems parameterized above average. In: SWAT 2010. Lect. Notes Comput. Sci., vol. 6139, pp.\u00a0164\u2013175 (2010)"},{"key":"9415_CR5","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/978-3-642-29344-3_16","volume-title":"Proc. LATIN 2012","author":"R. Crowston","year":"2012","unstructured":"Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S.: Parameterized complexity of MaxSat above average. In: Proc. LATIN 2012. Lect. Notes Comput. Sci., vol. 7256, pp. 184\u2013194 (2012)"},{"key":"9415_CR6","series-title":"Lect. Notes Comput. Sci.","first-page":"1","volume-title":"Proc. IPEC 2011","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. In: Proc. IPEC 2011. Lect. Notes Comput. Sci., vol. 7112, pp. 1\u201312 (2011)"},{"issue":"2","key":"9415_CR7","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0097539797323571","volume":"29","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R., Vardy, A., Whittle, G.: The parameterized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29(2), 545\u2013570 (1999)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"9415_CR8","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9415_CR9","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1016\/j.jcss.2010.06.001","volume":"77","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: A probabilistic approach to problems parameterized above or below tight bounds. J. Comput. Syst. Sci. 77, 422\u2013429 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9415_CR10","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48, 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"9415_CR11","series-title":"Lect. Notes Comput. Sci.","first-page":"118","volume-title":"Proc. IPEC 2011","author":"E.J. Kim","year":"2011","unstructured":"Kim, E.J., Williams, R.: Improved parameterized algorithms for above average constraint satisfaction. In: Proc. IPEC 2011. Lect. Notes Comput. Sci., vol. 7112, pp. 118\u2013131 (2011)"},{"key":"9415_CR12","first-page":"94","volume-title":"Proc. SODA 2012","author":"S. Kratsch","year":"2012","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In: Proc. SODA 2012, pp. 94\u2013103 (2012)"},{"key":"9415_CR13","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. Preprint. arXiv:1203.0833v2 [cs.DS]"},{"issue":"2","key":"9415_CR14","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137\u2013153 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9415_CR15","unstructured":"Rafiey, A.: Private Communication (2011)"},{"key":"9415_CR16","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-642-23719-5_33","volume-title":"Proc. ESA 2011","author":"V. Raman","year":"2011","unstructured":"Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, flowers and vertex cover. In: Proc. ESA 2011. Lect. Notes Comput. Sci., vol. 6942, pp. 382\u2013393 (2011)"},{"issue":"8","key":"9415_CR17","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9415-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9415-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9415-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:24Z","timestamp":1558698864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9415-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,24]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9415"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9415-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,24]]}}}