Javier Esparza Pierre Fraigniaud Thore Husfeldt S Elias Koutsoupias (Eds.) S o C R A 2 7 Automata, Languages, 5 8 S C and Programming N L 41st International Colloquium, ICALP 2014 Copenhagen, Denmark, July 8-11, 2014 Proceedings, Part I 123 Lecture Notes in Computer Science 8572 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison,UK TakeoKanade,USA JosefKittler,UK JonM.Kleinberg,USA AlfredKobsa,USA FriedemannMattern,Switzerland JohnC.Mitchell,USA MoniNaor,Israel OscarNierstrasz,Switzerland C.PanduRangan,India BernhardSteffen,Germany DougTygar,USA DemetriTerzopoulos,USA GerhardWeikum,Germany Advanced Research in Computing and Software Science SublineofLecturesNotesinComputerScience SublineSeriesEditors GiorgioAusiello,UniversityofRome‘LaSapienza’,Italy VladimiroSassone,UniversityofSouthampton,UK SublineAdvisoryBoard SusanneAlbers,UniversityofFreiburg,Germany BenjaminC.Pierce,UniversityofPennsylvania,USA BernhardSteffen,UniversityofDortmund,Germany DengXiaotie,CityUniversityofHongKong JeannetteM.Wing,MicrosoftResearch,Redmond,WA,USA Javier Esparza Pierre Fraigniaud Thore Husfeldt Elias Koutsoupias (Eds.) Automata, Languages, and Programming 41st International Colloquium, ICALP 2014 Copenhagen, Denmark, July 8-11, 2014 Proceedings, Part I 1 3 VolumeEditors JavierEsparza TechnischeUniversitätMünchen,Germany E-mail:[email protected] PierreFraigniaud LIAFA,UniversitéParisDiderot-Paris7,France E-mail:[email protected] ThoreHusfeldt ITUniversityofCopenhagen,Denmark E-mail:[email protected] EliasKoutsoupias UniversityofOxford,UK E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-662-43947-0 e-ISBN978-3-662-43948-7 DOI10.1007/978-3-662-43948-7 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2014941765 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©Springer-VerlagBerlinHeidelberg2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection withreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeingenteredand executedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthePublisher’slocation, inistcurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Permissionsforuse maybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violationsareliabletoprosecution undertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpublication, neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforanyerrorsor omissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespecttothe materialcontainedherein. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface ThisvolumecontainsthepaperspresentedatICALP2014:the41stInternational ColloquiumonAutomata,LanguagesandProgramming,heldduringJuly8–11, 2014,atITUniversityofCopenhagen.ICALPisthemainconferenceandannual meetingoftheEuropeanAssociationforTheoreticalComputerScience(EATCS) and first took place in 1972. This year the ICALP program consisted of three tracks: – Track A: Algorithms, Complexity, and Games – Track B: Logic, Semantics, Automata, and Theory of Programming – Track C: Foundations of Networked Computation In response to the call for papers, the three Program Committees received 484 submissions, a record number for ICALP. Track A received 319 submissions (another record), track B received 106 submissions, and track C received 59 submissions.EachsubmissionwasreviewedbyatleastthreeProgramCommittee members, aided by many subreviewers. The committee decided to accept 136 papers,which arecollectedin these proceedings.The selectionwasmade by the Program Committees based on originality, quality, and relevance to theoretical computer science. The quality of the submissions was very high indeed, and many deserving papers could not be selected. TheEATCSsponsoredawardsforbothabestpaperandabeststudentpaper for each of the three tracks, selected by the ProgramCommittees. The best paper awards were given to the following papers: – Track A: Andreas Bj¨orklund and Thore Husfeldt, “Shortest Two Disjoint Paths in Polynomial Time” – TrackB:JoelOuaknineandJamesWorrell.“UltimatePositivityIsDecidable for Simple Linear Recurrence Sequences” – Track C: Oliver G¨obel, Martin Hoefer, Thomas Kesselheim, Thomas Schlei- den, and Berthold V¨ocking, “Online Independent Set Beyond the Worst- Case: Secretaries, Prophets, and Periods” The best student paper awards, for papers that are solely authored by stu- dents, were given to the following papers: – Track A: Sune K. Jakobsen,“Information Theoretical Cryptogenography” – TrackB:MichaelWehar,“HardnessResultsforIntersectionNon-Emptiness” – Track C: Mohsen Ghaffari, “Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set” Apart from the contributed talks, the conference included invited presenta- tions by Sanjeev Arora, Maurice Herlihy, Viktor Kuncak, and Claire Mathieu. Abstracts of their talks are included in these proceedings as well. VI Preface The program of ICALP 2014 also included presentation of the Presburger Award 2014 to David Woodruff, the EATCS Award 2014 to Gordon Plotkin, and the G¨odel Prize to Ronald Fagin, Amnon Lotem, and Moni Naor. Two satellite events of ICALP were held on 7 July, 2014: – Trends in Online Algorithms (TOLA 2014) – Young Researcher Workshop on Automata, Languages and Programming (YR-ICALP 2014) We wish to thank all the authors who submitted extended abstracts for con- sideration, the members of the three Program Committees for their scholarly efforts, and all additional reviewers who assisted the Program Committees in the evaluation process. We thank the sponsors Springer-Verlag, EATCS, CWI Amsterdam, and Statens Kunstfond for their support, and the IT University of Copenhagen for hosting ICALP 2014. WearealsogratefultoallmembersoftheOrganizingCommitteeandtotheir support staff. The conference-management system EasyChair was used to handle the sub- missions, to conduct the electronic ProgramCommittee meetings, and to assist with the assembly of the proceedings. May 2014 Javier Esparza Pierre Fraigniaud Thore Husfeldt Elias Koutsoupias Organization Program Committee Dimitris Achlioptas UC, Santa Cruz, USA Pankaj Agrawal Duke University, USA Paolo Baldan Universita` di Padova, Italy Nikhil Bansal Eindhoven University of Technology, The Netherlands Michele Boreale Universit`a di Firenze, Italy Tomas Brazdil Masaryk University, Czech Republic Gerth Stølting Brodal Aarhus University, Denmark V´eronique Bruy`ere University of Mons, Belgium Jean Cardinal Universit´e libre de Bruxelles, Belgium Ning Chen Nanyang Technological University, Singapore Giorgos Christodoulou University of Liverpool, UK Andrea Clementi University of Rome Tor Vergata, Italy Veronique Cortier CNRS, Loria, France Anuj Dawar University of Cambridge, UK Xiaotie Deng Shanghai Jiaotong University, China Ilias Diakonikolas University of Edinburgh, UK Benjamin Doerr MPI Saarbru¨cken, Germany Chaled Elbassioni Masdar Institute, Abu Dhabi Javier Esparza TU Mu¨nchen, Germany Kousha Etessami University of Edinburgh, UK Panagiota Fatourou University of Crete, Greece Michal Feldman Hebrew University, Israel Maribel Fernandez Kings College London, UK Antonio Fern´andez Anta Universidad Rey Juan Carlos, Spain Amos Fiat Tel Aviv University, Israel Pierre Fraigniaud CNRS and University of Paris Diderot, France David Frutos Escrig Complutense University of Madrid, Spain Pierre Ganty IMDEA Software Institute, Spain Leszek Gasieniec University of Liverpool, UK Phillip Gibbons Intel Labs, USA Leslie Goldberg University of Oxford, UK Vipul Goyal Microsoft, India Peter Habermehl LIAFA, University of Paris 7, France Magnus Halldorsson Reykjavik University, Iceland Giuseppe Italiano University of Rome Tor Vergata, Italy Marcin Kaminski University of Warsaw, Poland VIII Organization Haim Kaplan Tel Aviv University, Israel Anna Karlin University of Washington, USA Ioardanis Kerenidis University of Paris Diderot, France Anne-Marie Kermarrec Inria Rennes, France Robert Kleinberg Cornell University, USA Michal Koucky Czech Academy of Sciences, Czech Republic Elias Koutsoupias University of Oxford, UK Robert Krauthgamer Weizmann Institute, Israel Manfred Kufleitner University of Stuttgart, Germany Sl(cid:3)awomir Lasota Warsaw University, Poland James Lee University of Washington, USA Oded Maler CNRS-VERIMAG, France Sebastian Maneth NICTA and UNSW, Australia Madhavan Mukund Chennai Mathematical Institute, India Ashwin Nayak University of Waterloo, Canada Jens Palsberg UCLA, USA Gopal Pandurangan Nanyang Technological University, Singapore Boaz Patt-Shamir Tel Aviv University, Israel Andrea Pietracaprina Universita` di Padova, Italy Andrea Richa Arizona State University, USA Lu´ıs Rodrigues Universidade T´ecnica de Lisboa, Portugal Jared Saia University of New Mexico, USA Piotr Sankowski University of Warsaw, Poland Christian Scheideler Universit¨at Paderborn, Germany Thomas Schwentick TU Dortmund, Germany Maria Serna UP Catalunya, Spain Sonja Smets University of Amsterdam, The Netherlands Christian Sohler TU Dortmund, Germany Jiri Srba Aalborg University, Denmark Jukka Suomela Aalto University, Finland Ryan Williams Stanford University, USA Philipp Woelfel University of Calgary, Canada Steve Zdancewic University of Pennsylvania, USA Additional Reviewers Aaronson, Scott Agarwal, Rachit Abe, Masayuki Aghazadeh, Zahra Abraham, Ittai Agrawal, Shweta Aceto, Luca Ajwani, Deepak Adler, Isolde Akutsu, Tatsuya Adsul, Bharat Al-Humaimeedy, Abeer Afshani, Peyman Alamdari, Soroush Agarwal, Alekh Alglave, Jade Organization IX Allender, Eric Bogdanov, Andrej Alon, Noga Bojanczyk, Mikolaj Althaus, Ernst Boker, Udi Alves, Sandra Bollig, Beate An, Hyung-Chan Bollig, Benedikt Anagnostopoulos, Aris Bonamy, Marthe Ananth, Prabhanjan Bonchi, Filippo Andoni, Alex Boneh, Dan Andoni, Alexandr Bonifaci, Vincenzo Ardenboim, Alon Bonnet, Edouard Arkhipov, Alex Bonsangue, Marcello Asarin, Eugene Bonsma, Paul Aspnes, James Borgstr¨om, Johannes Atig, Mohamed Faouzi Boutsidis, Christos Atserias, Albert Boyar, Joan Augustine, John Boyle, Elette Avron, Haim Brakerski, Zvika Babichenko, Yakov Brandstadt, Andreas Bacci, Giorgio Braverman, Mark Bacci, Giovanni Bremner, Michael Bach, Eric Brettell, Nick Balabonski, Thibaut Briet, Jop Banerjee, Abhishek Brihaye, Thomas Barrington, David Broadbent, Anne Bartoletti, Massimo Brody, Joshua Basset, Nicolas Bruni, Roberto Bavarian, Mohammad Brzuska, Christina Beame, Paul Buchbinder, Niv Becchetti, Luca Buchin, Kevin Bei, Xiaohui Buhrman, Harry Belmonte, R´emy Byrka, Jaroslaw Ben Avraham, Rinat B¨ohl, Florian Ben-Amram, Amir Cai, Yang Berger, Eli Caltais, Georgiana Berry, Jonathan Canetti, Ran Bertrand, Nathalie Canonne, Cl´ement Berwanger, Dietmar Cao, Yixin Bhaskar, Umang Carraro, Alberto Bitansky, Nir Cash, David Blazy, Olivier Ceccarello, Matteo Blesa, Maria J. Chakrabarti, Amit Bl¨omer, Johannes Chakraborty, Supratik Bodirsky, Manuel Chalermsook, Parinya Bodlaender, Hans L. Chan, Hubert Bodlaender, Marijke Chan, Siu On X Organization Chan, Timothy Delahaye, Benoit Chandran, Nishanth Delling, Daniel Charatonik, Witold Delvenne, Jean-Charles Chase, Melissa Delzanno, Giorgio Chatterjee, Krishnendu Denysyuk, Oksana Chechik, Shiri Dereniowski, Dariusz Chekuri, Chandra Devanur, Nikhil Chen, Jing Devroye, Luc Chen, Xujin Diaz, Josep Chen, Zhou Dietzfelbinger, Martin Cheval, Vincent Diks, Krzysztof Choudhury, Ashish Dima, Catalin Chow, Sherman S.M. Diochnos, Dimitris Chrobak, Marek Dobrev, Stefan Chung, Kai-Min Doerr, Carola Ciancia, Vincenzo Doyen, Laurent Cicalese, Ferdinando Driemel, Anne Clavier, Christophe Duflot, Marie Clemente, Lorenzo Dumitrescu, Adrian Codenotti, Paolo Dupuis, Fr´ed´eric Cohen, Edith Durand, Arnaud Cohen, Sarel Durand-Gasselin, Antoine Cohn, Henry Durnoga, Konrad Colcombet, Thomas Dvir, Zeev Colini Baldeschi, Riccardo Dyer, Martin Costello, Craig Edmonds, Jeff Crescenzi, Pierluigi Efremenko, Klim Cryan, Mary Efthymiou, Charilaos Cygan, Marek Ehrgott, Matthias Czerwin´ski, Wojciech Ehsanfar, Ebrahim Dalmau, Victor Elbassioni, Khaled Damaschke, Peter Elberfeld, Michael Damg˚ard, Ivan Elmasry, Amr Dang, Thao Els¨asser, Robert Dani, Varsha Emmi, Michael Dasgupta, Bhaskar Ene, Alina Datta, Samir Enea, Constantin David, Alexandre Enqvist, Sebastian De Bonis, Annalisa Eppstein, David de Caro, Angelo Epstein, Leah De Caro, Angelo Erlebach, Thomas De Liguoro, Ugo Escoffier, Bruno de Wolf, Ronald Even, Guy Decker, Normann Fahrenberg, Uli Degorre, Aldric Fanelli, Angelo