Mohammad Reza Mousavi Jiˇrí Sgall (Eds.) 8 0 Topics in Theoretical 6 0 1 S Computer Science C N L Second IFIP WG 1.8 International Conference, TTCS 2017 Tehran, Iran, September 12–14, 2017 Proceedings 123 Lecture Notes in Computer Science 10608 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zurich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbrücken, Germany More information about this series at http://www.springer.com/series/7407 ří Mohammad Reza Mousavi Ji Sgall (Eds.) (cid:129) Topics in Theoretical Computer Science Second IFIP WG 1.8 International Conference, TTCS 2017 – Tehran, Iran, September 12 14, 2017 Proceedings 123 Editors Mohammad Reza Mousavi JiříSgall University of Leicester CharlesUniversity Leicester Prague UK Czech Republic ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-319-68952-4 ISBN978-3-319-68953-1 (eBook) DOI 10.1007/978-3-319-68953-1 LibraryofCongressControlNumber:2017956068 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©IFIPInternationalFederationforInformationProcessing2017 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictionalclaimsin publishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Welcome to the Second IFIP International Conference on Topics in Theoretical ComputerScience(TTCS2017),heldduringSeptember12–14,2017,attheSchoolof ComputerScience,InstituteforResearchinFundamentalSciences(IPM),Tehran,Iran. This volume contains the papers accepted for presentation at TTCS 2017. For this edition of TTCS, we received 20 submissions from 10 different countries. An inter- national Program Committee comprising 32 leading scientists from 13 countries reviewed the papers thoroughly providing on average four review reports for each paper. We accepted eight submissions, which translates into 40% of all submissions. Thismeansthattheprocesswasselectiveandonlyhigh-qualitypaperswereaccepted. The program also includes four invited talks by the following world-renowned com- puter scientists: – Mahdi Cheraghchi, Imperial College, UK – Łukasz Jeż, University of Wrocław, Poland – Jaco van de Pol, University of Twente, The Netherlands – Peter Csaba Ölveczky, University of Oslo, Norway Additionally, the program features two talks and one tutorial in the PhD Forum, which are not included in the proceedings. We thank IPM, and in particular the Organizing Committee, for having provided various facilities and for their generous support. We are also grateful to our Program Committeefortheirprofessionalandhardworkinprovidingexpertreviewreportsand thorough discussions leading to a very interesting and strong program. We also acknowledge the excellent facilities provided by the EasyChair system, which were crucial in managing the process of submission, selection, revision, and publication of the manuscripts included in these proceedings. September 2017 Mohammad Reza Mousavi Jiří Sgall Organization General Chair Hamid Sarbazi-azad IPM, Iran; Sharif University of Technology, Iran Local Organization Chair Hamid Reza Shahrabi IPM, Iran Publicity Chair Mahmoud Shirazi IPM, Iran Program Committee Farhad Arbab CWI and Leiden University, The Netherlands Amitabha Bagchi Indian Institute of Technology, Delhi, India Sam Buss University of California, San Diego, USA Jarek Byrka University of Wroclaw, Poland Ilaria Castellani Inria Sophia Antipolis, France Amir Daneshgar Sharif University of Technology, Iran Anna Gal University of Texas at Austin, USA Fatemeh Ghassemi University of Tehran, Iran Mohammad T. Hajiaghayi University of Maryland, College Park, USA Hossein Hojjat Rochester Institute of Technology, Rochester, New York, USA Mohammad Izadi Sharif University of Technology, Iran Sung-Shik T.Q. Jongmans Open University of The Netherlands, Imperial College London, UK Ramtin Khosravi University of Tehran, Iran Jan Kretinsky Masaryk University, Czech Republic Amit Kumar IIT Delhi, India Bas Luttik Eindhoven University of Technology, The Netherlands Mohammad Mahmoody University of Virginia Larry Moss Indiana University, USA MohammadRezaMousavi University of Leicester, UK Rolf Niedermeier TU Berlin, Germany Giuseppe Persiano Università degli Studi di Salerno, Italy Jörg-Rüdiger Sack Carleton University, Canada Mehrnoosh Sadrzadeh Queen Mary University of London, UK Rahul Santhanam University of Edinburgh, UK Gerardo Schneider Chalmers, University of Gothenburg, Sweden VIII Organization Jiří Sgall Computer Science Institute of Charles University, Czech Republic Subodh Sharma Indian Institute of Technology Delhi, India Mirco Tribastone IMT Institute for Advanced Studies Lucca, Italy Kazunori Ueda Waseda University, Japan Vijay Vazirani Georgia Tech, USA Gerhard Woeginger RWTH Aachen, Germany Hamid Zarrabi-Zadeh Sharif University of Technology, Iran Additional Reviewers Abd Alrahman, Yehia Mirjalali, Kian Bagga, Divyanshu Molter, Hendrik Baharifard, Fatemeh Neruda, Roman Bentert, Matthias van der Woude, Jaap Klinz, Bettina van Oostrom, Vincent Krämer, Julia Vegh, Laszlo Maggi, Alessandro Łukaszewski, Andrzej Meggendorfer, Tobias Abstracts of Invited Talks The Coding Lens in Explicit Constructions Mahdi Cheraghchi Departmentof Computing, Imperial CollegeLondon,UK [email protected] Abstract. The theory of error-correcting codes, originally developed as a fun- damental technique for a systematic study of communications systems, has served as a pivotal tool in major areas of mathematics, computer science and electrical engineering. Understanding problems through a “coding lens” has consistently led to breakthroughs in a wide spectrum of research areas, often seemingly foreign from coding theory, including discrete mathematics, geom- etry, cryptography, signal processing, algorithms and complexity, to name a few.Thistalkwillfocusontheroleofcodingtheoryinpseudorandomness,and particularly, explicit construction problems in sparse recovery and signal processing.