{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:48:43Z","timestamp":1725889723900},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_15","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T06:50:58Z","timestamp":1346223058000},"page":"147-158","source":"Crossref","is-referenced-by-count":5,"title":["Homomorphic Hashing for Sparse Coefficient Extraction"],"prefix":"10.1007","author":[{"given":"Petteri","family":"Kaski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikko","family":"Koivisto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"15_CR1","doi-asserted-by":"publisher","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\u00a061(3), 638\u2013655 (2011)","journal-title":"Algorithmica"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: FOCS, pp. 173\u2013182. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.24"},{"issue":"2","key":"15_CR3","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput.\u00a039(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"15_CR4","unstructured":"Crowston, R., Gutin, G., Jones, M., Yeo, A.: Lower bound for Max-r-Lin2 and its applications in algorithmics and graph theory. CoRR, abs\/1104.1135 (2011)"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R., Italiano, G.F.: Sparse dynamic programming I: linear cost functions. J. ACM\u00a039, 519\u2013545 (1992)","journal-title":"J. ACM"},{"issue":"3","key":"15_CR6","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1145\/146637.146656","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R., Italiano, G.F.: Sparse dynamic programming II: convex and concave cost functions. J. ACM\u00a039(3), 546\u2013567 (1992)","journal-title":"J. ACM"},{"key":"15_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms, 1st edn. Springer-Verlag New York, Inc., New York (2010)","edition":"1"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Szeider, S.: Strong backdoors to nested satisfiability. CoRR, abs\/1202.4331 (2012)","DOI":"10.1007\/978-3-642-31612-8_7"},{"issue":"5","key":"15_CR9","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/060668092","volume":"39","author":"D. Harnik","year":"2010","unstructured":"Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. SIAM Journal on Computing\u00a039(5), 1667\u20131713 (2010)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR10","doi-asserted-by":"publisher","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\u00a048, 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM\u00a021, 277\u2013292 (1974)","journal-title":"J. ACM"},{"issue":"2","key":"15_CR12","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/978-3-642-02927-1_54","volume-title":"Automata, Languages and Programming","author":"I. Koutis","year":"2009","unstructured":"Koutis, I., Williams, R.: Limits and Applications of Group Algebras for Parameterized Problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 653\u2013664. Springer, Heidelberg (2009)"},{"key":"15_CR14","unstructured":"Lipton, R.J.: Beating Bellman for the knapsack problem (2010), \n                  \n                    http:\/\/rjlipton.wordpress.com\/2010\/03\/03\/beating-bellman-for-the-knapsack-problem\/\n                  \n                  \n                , \n                  \n                    http:\/\/rjlipton.wordpress.com"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/1806689.1806735","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","author":"D. Lokshtanov","year":"2010","unstructured":"Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 321\u2013330. ACM, New York (2010)"},{"issue":"2","key":"15_CR16","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1137\/S0097539792239291","volume":"24","author":"Y. Mansour","year":"1995","unstructured":"Mansour, Y.: Randomized interpolation and approximation of sparse polynomials. SIAM J. Comput.\u00a024(2), 357\u2013368 (1995)","journal-title":"SIAM J. Comput."},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/978-3-642-02927-1_59","volume-title":"Automata, Languages and Programming","author":"J. Nederlof","year":"2009","unstructured":"Nederlof, J.: Fast Polynomial-Space Algorithms Using M\u00f6bius Inversion: Improving on Steiner Tree and Related Problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 713\u2013725. Springer, Heidelberg (2009)"},{"issue":"7","key":"15_CR18","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00236-007-0056-x","volume":"44","author":"N. Nishimura","year":"2007","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Solving #sat using vertex covers. Acta Inf.\u00a044(7), 509\u2013523 (2007)","journal-title":"Acta Inf."},{"issue":"4","key":"15_CR19","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"15_CR20","doi-asserted-by":"publisher","first-page":"211","DOI":"10.2307\/2371291","volume":"63","author":"B. Rosser","year":"1941","unstructured":"Rosser, B.: Explicit bounds for some functions of prime numbers. American Journal of Mathematics\u00a063(1), 211\u2013232 (1941)","journal-title":"American Journal of Mathematics"},{"issue":"3","key":"15_CR21","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R. Schroeppel","year":"1981","unstructured":"Schroeppel, R., Shamir, A.: A T\u2009=\u2009O(2\n                  n\/2), S\u2009=\u2009O(2\n                  n\/4) algorithm for certain NP-complete problems. SIAM J. Comput.\u00a010(3), 456\u2013464 (1981)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"15_CR22","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1016\/S0021-9800(67)80064-4","volume":"2","author":"L. Solomon","year":"1967","unstructured":"Solomon, L.: The burnside algebra of a finite group. Journal of Combinatorial Theory\u00a02(4), 603\u2013615 (1967)","journal-title":"Journal of Combinatorial Theory"},{"key":"15_CR23","unstructured":"Traxler, P.: Exponential Time Complexity of SAT and Related Problems. PhD thesis, ETH Z\u00fcrich (2010)"},{"issue":"6","key":"15_CR24","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R. Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in \n                  \n                    \n                  \n                  $\\mathcal{O}^\\star(2^{k})$\n                 time. Inf. Process. Lett.\u00a0109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"key":"15_CR25","unstructured":"Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: IJCAI, pp. 1173\u20131178. Morgan Kaufmann (2003)"},{"issue":"3","key":"15_CR26","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/j.dam.2007.03.023","volume":"156","author":"G.J. Woeginger","year":"2008","unstructured":"Woeginger, G.J.: Open problems around exact algorithms. Discrete Applied Mathematics\u00a0156(3), 397\u2013405 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic Algorithms for Sparse Polynomials. In: Ng, E.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:03:22Z","timestamp":1620115402000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}