{"id":949,"date":"2018-01-29T13:31:30","date_gmt":"2018-01-29T13:31:30","guid":{"rendered":"http:\/\/corner.mimuw.edu.pl\/?p=949"},"modified":"2018-09-12T09:39:18","modified_gmt":"2018-09-12T09:39:18","slug":"esa-test-of-time-award-2017","status":"publish","type":"post","link":"https:\/\/corner.mimuw.edu.pl\/?p=949","title":{"rendered":"ESA Test-of-Time Award 2017"},"content":{"rendered":"<p><strong>Announcement of the ESA Test-of-Time Award 2017<\/strong><\/p>\n<p>European Symposium on Algorithms (ESA)<br \/>\n<a href=\"http:\/\/esa-symposium.org\/\">http:\/\/esa-symposium.org\/<\/a><\/p>\n<hr \/>\n<p>The ESA Test-of-Time Award (ESA ToTA) recognizes outstanding papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. For the 2017 award, papers from ESA'96 to ESA'98 were considered.<\/p>\n<p>The committee nominates the following paper for the ESA ToTA 2017. The paper stands out as a classic in the algorithms field and continues to be cited as an exemplary study in its field.<\/p>\n<p>From ESA 96-98:<\/p>\n<p>James Abello, Adam L. Buchsbaum, and Jeffery R. Westbrook<br \/>\nA Functional Approach to External Graph Algorithms<br \/>\nProceedings ESA'98, pp. 332-343<br \/>\nalso in: Algorithmica 32 (2002) 437-458<\/p>\n<p>Laudation:<br \/>\nThe paper deals with the design of algorithms that operate on massive data sets in external memory. Building on the well-known I\/O model of\u00a0complexity by Aggarwal and Vitter, the authors introduce a novel design principle for external algorithms based purely on functional\u00a0transformations of the data, which facilitates standard checkpointing and program optimization techniques. Illustrated on a variety of graph\u00a0problems, their approach is proved to be elegant and versatile in the design of both deterministic and randomized external algorithms while\u00a0the resulting I\/O complexities remain competitive. Functional algorithms are also designed for semi-external problems, in which the<br \/>\nnodes fit in main memory but the connecting edges are abundant and only available in external memory. The paper is an excellent illustration of how general principles of functional program design and model-based complexity can remain in harmony in the field of external algorithms.<\/p>\n<p>Award Committee:<br \/>\nGiuseppe F. Italiano (Rome),<br \/>\nMike Paterson (Warwick),<br \/>\nJan van Leeuwen (Utrecht)<\/p>\n<hr \/>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Announcement of the ESA Test-of-Time Award 2017 European Symposium on Algorithms (ESA) http:\/\/esa-symposium.org\/ The ESA Test-of-Time Award (ESA ToTA) recognizes outstanding papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential &hellip; <a href=\"https:\/\/corner.mimuw.edu.pl\/?p=949\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/949"}],"collection":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=949"}],"version-history":[{"count":6,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/949\/revisions"}],"predecessor-version":[{"id":1008,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/949\/revisions\/1008"}],"wp:attachment":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=949"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=949"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=949"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}