{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T21:17:56Z","timestamp":1781644676910,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,6,8]],"date-time":"2014-06-08T00:00:00Z","timestamp":1402185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,6,8]]},"DOI":"10.1145\/2582112.2582124","type":"proceedings-article","created":{"date-parts":[[2014,5,2]],"date-time":"2014-05-02T14:01:31Z","timestamp":1399039291000},"page":"67-76","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["The limited blessing of low dimensionality"],"prefix":"10.1145","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[{"name":"Institute of Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science & Engineering, and Dept. of Mathematics, The Ohio State University, Columbus, OH, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,6,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/299917.299918"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.001"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/100812653"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.003"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000811"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377676.1377693"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.003"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007391"},{"key":"e_1_3_2_1_11_1","first-page":"4","volume-title":"Proc. of AAAI-90","author":"Freuder E. C.","year":"1990","unstructured":"E. C. Freuder . Complexity of k-tree structured constraint satisfaction problems . In Proc. of AAAI-90 , pages 4 -- 9 , Boston, MA , 1990 . E. C. Freuder. Complexity of k-tree structured constraint satisfaction problems. In Proc. of AAAI-90, pages 4--9, Boston, MA, 1990."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_16"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.06.005"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2011.09.001"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_1"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109590"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13562-0_5"},{"key":"e_1_3_2_1_23_1","first-page":"649","volume-title":"STACS","author":"Knauer C.","year":"2011","unstructured":"C. Knauer , H. R. Tiwary , and D. Werner . On the computational complexity of ham-sandwich cuts, helly sets, and related problems . In STACS , pages 649 -- 660 , 2011 . C. Knauer, H. R. Tiwary, and D. Werner. On the computational complexity of ham-sandwich cuts, helly sets, and related problems. In STACS, pages 649--660, 2011."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.06.039"},{"key":"e_1_3_2_1_25_1","first-page":"41","article-title":"Lower bounds based on the Exponential Time Hypothesis","volume":"84","author":"Lokshtanov D.","year":"2011","unstructured":"D. Lokshtanov , D. Marx , and S. Saurabh . Lower bounds based on the Exponential Time Hypothesis . Bulletin of the EATCS , 84 : 41 -- 71 , 2011 . D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 84:41--71, 2011.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.50"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721845"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9248-9"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80067-3"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796397"},{"key":"e_1_3_2_1_35_1","first-page":"192","volume-title":"ISAAC","author":"Thilikos D. M.","year":"2000","unstructured":"D. M. Thilikos , M. J. Serna , and H. L. Bodlaender . Constructive linear time algorithms for small cutwidth and carving-width . In ISAAC , pages 192 -- 203 , 2000 . D. M. Thilikos, M. J. Serna, and H. L. Bodlaender. Constructive linear time algorithms for small cutwidth and carving-width. In ISAAC, pages 192--203, 2000."}],"event":{"name":"SOCG'14: Annual Symposium on Computational Geometry","location":"Kyoto Japan","acronym":"SOCG'14","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirtieth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2582112.2582124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2582112.2582124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:09Z","timestamp":1750234209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2582112.2582124"}},"subtitle":["when 1-1\/d is the best possible exponent for d-dimensional geometric problems"],"short-title":[],"issued":{"date-parts":[[2014,6,8]]},"references-count":35,"alternative-id":["10.1145\/2582112.2582124","10.1145\/2582112"],"URL":"https:\/\/doi.org\/10.1145\/2582112.2582124","relation":{},"subject":[],"published":{"date-parts":[[2014,6,8]]},"assertion":[{"value":"2014-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}