Conference Programme

Updated: 11 July, 2016


Monday, 11 July, 2016

Registration / Support Desk hours (17:00 -19:00)
Welcome Reception
19:00


Tuesday, 12 July, 2016

Registration / Support Desk hours (08:00 - 13:00 & 14:00 - 17:00)
Room
Aracoeli+Campidoglio
Invited Talk
Devavrat Shah, MIT, USA

09:00-10:00  
Coffee Break
10:00-10:30
Room
Aracoeli+Campidoglio
Room
Trinità dei Monti A
Room
Trinità dei Monti B
Room
NAVONA ABC

A1S1
10:30-13:00


B1S1
10:30-13:00


C1S1
10:30-13:00


D1S1
10:30-13:00

Lunch Break
13:00-14:20

A1S2
14:20-16:00


B1S2
14:20-16:00


C1S2
14:20-16:00


D1S2
14:20-16:00

Coffee Break
16:00-16:30

A1S3
16:30-18:10


B1S3
16:30-18:10


C1S3
16:30-18:10


D1S3
16:30-18:10



Wednesday, 13 July, 2016

Registration / Support Desk hours (08:30 - 13:00 & 14:00 - 17:00)
Room
Aracoeli+Campidoglio
Invited Talk
Xavier Leroy, INRIA, France

09:00-10:00  
Coffee Break
10:00-10:30
Room
Aracoeli+Campidoglio
Room
Trinità dei Monti A
Room
Trinità dei Monti B

A2S1
10:30-13:00


B2S1
10:30-13:00


C2S1
10:30-13:00

Lunch Break
13:00-14:30

A2S2
14:30-15:45


B2S2
14:30-15:45


C2S2
14:30-15:20

Coffee Break
15:45-16:15
Room
Aracoeli+Campidoglio



Awards
16:15-17:45

  • EATCS Distinguished Dissertation Award with introduction of Luca Aceto.
  • Presburger Award, with introduction of Marta Kwiatkowska.
  • Goedel Prize, with introduction of Andy Pitts.
  • EATCS Award, with introduction of Luca Aceto.




Conference Dinner
18:30




Thursday, 14 July, 2016

Registration / Support Desk hours (08:30 - 13:00 & 14:00 - 17:00)
Room
Aracoeli+Campidoglio
Invited Talk
Seffi Naor, Technion, Haifa - Israel

09:00-10:00  
Coffee Break
10:00-10:30
Room
Aracoeli+Campidoglio
Room
Trinità dei Monti A
Room
Trinità dei Monti B

A3S1
10:30-13:00


B3S1
10:30-13:00


C3S1
10:30-13:00

Lunch Break
13:00-14:20

A3S2
14:20-16:00


B3S2
14:20-16:00


C3S2
14:20-16:00

Coffee Break
16:00-16:30
Room
Aracoeli+Campidoglio



General Assembly
16:30-18:15

  1. Welcome from the president
  2. Report from the conference organizers
  3. Report from the PC chairs
  4. Report on the organization of ICALP 2017
  5. Bid for hosting ICALP 2018
  6. Report from the secretary of the EATCS
  7. Report from the treasurer of the EATCS
  8. Report from the president and presentation of the new leadership of the EATCS


Friday, 15 July, 2016

Registration / Support Desk hours (08:30 - 13:00 & 14:00 - 17:00)
Room
Aracoeli+Campidoglio
Invited Talk
Marta Z. Kwiatkowska, Oxford, UK

09:00-10:00  
Coffee Break
10:00-10:30
Room
Aracoeli+Campidoglio
Room
Trinità dei Monti A
Room
Trinità dei Monti B

A4S1
10:30-13:00


B4S1
10:30-13:00


C4S1
10:30-13:00

Lunch Break
13:00-14:20

A4S2
14:20-16:00


B4S2
14:20-16:00


C4S2
14:20-16:00

Coffee Break
16:00-16:30
Room
Aracoeli+Campidoglio
Room
Trinità dei Monti A

A4S3
16:30-17:20


B4S3
16:30-17:20

Monday, 11 July, 2016

Registration / Support Desk hours (17:00 -19:00)
Welcome Reception
19:00

Tuesday, 12 July, 2016

  Registration / Support Desk hours (08:00 - 13:00 & 14:00 - 17:00)
09:00-10:00 Invited Talk - Devavrat Shah, MIT, USA Room: Aracoeli+Campidoglio
10:00-10:30 Coffee Break  
10:30-13:00 Session: A1S1 Track: A
Room:
Aracoeli+Campidoglio
Fine-grained complexity analysis of two classic TSP variants Mark de Berg, Kevin Buchin, Bart M. P. Jansen and Gerhard J. Woeginger.
Bicovering: Covering edges with two small subsets of vertices Amey Bhangale, Rajiv Gandhi, Mohammadtaghi Hajiaghayi, Rohit Khandekar and Guy Kortsarz.
Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs Chandra Chekuri, Alina Ene and Marcin Pilipczuk.
Quasi-4-Connected Components Martin Grohe.
Subexponential Time Algorithms for Embedding H-Minor Free Graphs Hans L. Bodlaender, Jesper Nederlof and Tom van der Zanden.
Relating Graph Thickness to Planar Layers and Bend Complexity Stephane Durocher and Debajyoti Mondal.
10:30-13:00 Session: B1S1
Chair: Jacob Rehof Track: B
  Logics and Tree languages  
Room:
Trinità dei Monti A
Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness Hubie Chen.
Past, Present, and Infinite Future Thomas Wilke.
Thin MSO with a probabilistic path quantifier Mikolaj Bojanczyk.
Deciding Piecewise Testable Separability for Regular Tree Languages Jean Goubault-Larrecq and Sylvain Schmitz.
Computation Tree Logic for Synchronization Properties Krishnendu Chatterjee and Laurent Doyen.
Deciding topological complexity of Buchi languages Michal Skrzypczak and Igor Walukiewicz.
10:30-13:00 Session: C1S1 Track: C
Room:
Trinità dei Monti B
An Optimal Dual Fault Tolerant Reachability Oracle Keerti Choudhary.
Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds Yun Kuen Cheung, Gramoz Goranci and Monika Henzinger.
Distance labeling schemes for trees Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen and Ely Porat.
Near Optimal Adjacency Labeling Schemes for Power-Law Graphs Casper Petersen, Noy Rotbart, Jakob Grue-Simonsen and Christian Wulff-Nilsen.
On the Resiliency of Randomized Routing Against Multiple Edge Failures Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Schapira and Scott Shenker.
Partition bound is quadratically tight for product distributions Prahladh Harsha, Rahul Jain and Jaikumar Radhakrishnan.
10:30-13:00 Session: D1S1 Track: A
Room:
Navona ABC
Optimal approximate matrix product in terms of stable rank Michael B. Cohen, Jelani Nelson and David P. Woodruff.
Approximate Span Programs Tsuyoshi Ito and Stacey Jeffery.
Power of Quantum Computation with Few Clean Qubits Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate and Seiichiro Tani.
Space-Efficient Error Reduction for Unitary Quantum Computations Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae and Harumichi Nishimura.
Linear time algorithm for quantum 2SAT Itai Arad, Miklos Santha, Aarthi Sundaram and Shengyu Zhang.
Optimal quantum algorithm for polynomial interpolation Andrew Childs, Wim Van Dam, Shih-Han Hung and Igor Shparlinski.
13:00-14:20 Lunch Break  
14:20-16:00 Session: A1S2 Track: A
Room:
Aracoeli+Campidoglio
Semi-Streaming Algorithms for Annotated Graph Streams Justin Thaler.
Dynamic Graph Stream Algorithms in o(n) Space Zengfeng Huang and Pan Peng.

Diameter and k-Center in Sliding Windows

Vincent Cohen-Addad, Chris Schwiegelshohn and Christian Sohler.

Approximate Hamming distance in a stream

Tatiana Starikovskaya and Raphael Clifford.
14:20-16:00 Session: B1S2
Chair: Ranko Lazic Track: B
  Probabilities and Stochastic Models  
Room:
Trinità dei Monti A
On the Skolem Problem for Continuous Linear Dynamical Systems
Ventsislav Chonev, Joel Ouaknine and James Worrell.
Analysing decisive stochastic processes Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye and Pierre
Carlier.
Composition of stochastic transition systems based on spans and couplings Daniel Gburek, Christel Baier and Sascha Klüppelholz.
On Restricted Nonnegative Matrix Factorization Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi and
James Worrell.
14:20-16:00 Session: C1S2 Track: C
Room:
Trinità dei Monti B
Efficient Plurality Consensus, or: The benefits of cleaning up from time to time Petra Berenbrink, Tom Friedetzky, George Giakkoupis and Peter Kling.
Fast, Robust, Quantizable Approximate Consensus Bernadette Charron-Bost, Matthias Függer and Thomas Nowak.
Leader Election in Unreliable Radio Networks Mohsen Ghaffari and Calvin Newport.
Faster Deterministic Communication in Radio Networks Artur Czumaj and Peter Davies.
14:20-16:00 Session: D1S2 Track: A
Room:
Navona ABC

Price of Competition and Dueling Games

Sina Dehghani, Mohammadtaghi Hajiaghayi, Hamid Mahini and Saeed Seddighin.
Popular Half-integral Matchings Telikepalli Kavitha.
Voronoi Choice Games Meena Boppana, Rani Hod, Michael Mitzenmacher and Tom Morgan.
The Complexity of Hex and the Jordan Curve Theorem Aviv Adler, Constantinos Daskalakis and Erik Demaine.
16:00-16:30 Coffee Break  
16:30-18:10 Session: A1S3 Track: A
Room:
Aracoeli+Campidoglio
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems Andreas Emil Feldmann and Dániel Marx.
Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth Dániel Marx and Valia Mitsou.
Kernelization of Cycle Packing with Relaxed Disjointness Constraints Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer Mouawad and Saket Saurabh
Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems Till Fluschnik, Danny Hermelin, André Nichterlein and Rolf Niedermeier.
16:30-18:10 Session: B1S3
Chair: Naoki Kobayashi Track: B
  Verification  
Room:
Trinità dei Monti A
Proving the Herman-Protocol Conjecture Maria Bruna, Radu Grigore, Stefan Kiefer, Joel Ouaknine and James
Worrell.
A Polynomial-Time Algorithm for Reachability in Branching VASS in
Dimension One
Stefan Göller, Christoph Haase, Ranko Lazic and Patrick Totzke.
Reachability in Networks of Register Protocols under Stochastic Schedulers Patricia Bouyer, Nicolas Markey, Mickael Randour, Arnaud Sangnier and Daniel Stan.
A program logic for union bounds - proving accuracy of differentially private computations Gilles Barthe, Marco Gaboardi, Benjamin Grégoire, Justin Hsu and
Pierre-Yves Strub.
16:30-18:10 Session: C1S3 Track: C
Room:
Trinità dei Monti B
Network of Complements Moshe Babaioff, Liad Blumrosen and Noam Nisan.
House Markets with Matroid and Knapsack Constraints Piotr Krysta and Jinshan Zhang.
Reservation Exchange Markets for Internet Advertising Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad and Renato Paes-Leme.
Competitive Analysis of Constrained Queueing Systems Sungjin Im, Janardhan Kulkarni and Kamesh Munagala.
16:30-18:10 Session: D1S3 Track: A
Room:
Navona ABC
Do Distributed Differentially-Private Protocols Require Oblivious Transfer? Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey and Amit Sahai.

Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions

Benoit Libert, Somindu C. Ramanna and Moti Yung.
Look-ahead Non-malleable Codes Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey and Jalaj Upadhyay.
Provably Secure Virus Detection: Using The Observer Effect Against Malware Vassilis Zikas, Rafail Ostrovsky and Richard Lipton.

Wednesday, 13 July, 2016

  Registration / Support Desk hours (08:30 - 13:00 & 14:00 - 17:00)
09:00-10:00 Invited Talk - Xavier Leroy, INRIA, France Room: Aracoeli+Campidoglio
10:00-10:30 Coffee Break  
10:30-13:00 Session: A2S1 Track: A
Room:
Aracoeli+Campidoglio
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits Neeraj Kayal, Chandan Saha and Sébastien Tavenas.
AC0(MOD2) lower bounds for the Boolean inner product Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer and Ning Xie.
Improved Bounds on the Sign-Rank of AC^0 Mark Bun and Justin Thaler.
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi and Toniann Pitassi.
Boundaries of VP and VNP Joshua Grochow, Ketan Mulmuley and Youming Qiao.
On the Sensitivity Conjecture Avishay Tal.
10:30-13:00 Session: B2S1 Track: A
Room:
Trinità dei Monti A
Online Semidefinite Programming Noa Elad, Satyen Kale and Joseph Naor.

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

Sina Dehghani, Soheil Ehsani, Mohammadtaghi Hajiaghayi, Vahid Liaghat, Harald Racke and Saeed Seddighin.

Carpooling in Social Networks

Amos Fiat, Anna Karlin, Elias Koutsoupias, Claire Mathieu and Rotem Zach.
Beating the Harmonic lower bound for online bin packing Sandy Heydrich and Rob van Stee.

Randomization can be as helpful as a glimpse of the future in online computation

Jesper W. Mikkelsen.
An improved analysis of the ER-SpUD dictionary learning algorithm Jaroslaw Blasiok and Jelani Nelson.
10:30-13:00 Session: C2S1 Track: C
Room:
Trinità dei Monti B
The Linear Voting Model Nicolás Rivera and Colin Cooper.
Discordant voting processes on finite graphs Colin Cooper, Alan Frieze, Nicolás Rivera and Martin Dyer.
Bounds on the Voter Model in Dynamic Networks Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec and Frederik Mallmann-Trenn.
Bootstrap percolation on geometric inhomogeneous random graphs Christoph Koch and Johannes Lengler.
Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques Alessio Conte, Roberto Grossi, Andrea Marino and Luca Versari.
On the Size and the Approximability of Minimum Temporally Connected Subgraphs Kyriakos Axiotis and Dimitris Fotakis.
13:00-14:30 Lunch Break  
14:30-15:45 Session: A2S2 Track: A
Room:
Aracoeli+Campidoglio
Approximation via Correlation Decay when Strong Spatial Mixing Fails Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo and Daniel Štefankovič.
A complexity trichotomy for approximately counting list H-colourings Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum.
Parity Separation: A Scientifically Proven Method for Permanent Weight Loss Radu Curticapean.
14:30-15:45 Session: B2S2
Chair: Thomas Wilke Track: B
  Computability Issues  
Room:
Trinità dei Monti A
The decidable properties of subrecursive functions Mathieu Hoyrup.
Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length. Olivier Bournez, Daniel Graça and Amaury Pouly.
Algorithmic optimization for the realization of an effective subshift by a sofic Mathieu Sablik and Michael Schraudner.
14:30-15:20 Session: C2S2 Tracks: C+A
Room:
Trinità dei Monti B
On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter Søren Dahlgaard.
Incremental 2-Edge-Connectivity in Directed Graphs Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis.
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem Benjamin Doerr and Marvin Künnemann.
15:45-16:15 Coffee Break  
16:15-17:45 Awards Session

  • EATCS Distinguished Dissertation Award with introduction of Luca Aceto.
  • Presburger Award, with introduction of Marta Kwiatkowska.
  • Goedel Prize, with introduction of Andy Pitts.
  • EATCS Award, with introduction of Luca Aceto.
Room: Aracoeli+Campidoglio
     
19:30 Conference Dinner  

Thursday, 14 July, 2016

  Registration / Support Desk hours (08:30 - 13:00 & 14:00 - 17:00)
09:00-10:00 Invited Talk - Seffi Naor, Technion, Haifa - Israel Room: Aracoeli+Campidoglio
10:00-10:30 Coffee Break  
10:30-13:00 Session: A3S1 Track: A
Room:
Aracoeli+Campidoglio
Random-Edge is slower than Random-Facet on abstract cubes Thomas Dueholm Hansen and Uri Zwick.
Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction Di Wang, Satish Rao and Michael Mahoney.
Approximating the Solution to Mixed Packing and Covering LPs in parallel ~{O}(ε^{-3}) time Di Wang, Michael Mahoney, Satish Rao and Peng Zhang.
A Fast Distributed Stateless Algorithm for α-Fair Packing Problems Jelena Marasevic, Clifford Stein and Gil Zussman.
Faster Algorithms for Maximum Inscribed Balls and Minimum Enclosing Balls Zeyuan Allen-Zhu, Zhenyu Liao and Yang Yuan.
All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing Christian Sommer.
10:30-13:00 Session: B3S1
Chair: Marco Gaboardi Track: B
  Types, Topology and Optimisation  
Room:
Trinità dei Monti A
On Word and Frontier Languages of Unsafe Higher-Order Grammars Kazuyuki Asada and Naoki Kobayashi.
The Schutzenberger product for Syntactic Spaces Mai Gehrke, Daniela Petrisan and Luca Reggio.
Logic of Local Inference for Contextuality in Quantum Physics and Beyond Kohei Kishida.
Minimizing resources of sweeping and streaming string transducers Félix Baschenis, Olivier Gauwin, Anca Muscholl and Gabriele Puppis.
A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods Victor Poupet and Anaël Grandjean.
New Interpretation and Generalization of the Kameda-Weiner Method Hellis Tamm.
10:30-13:00 Session: C3S1 Track: A
Room:
Trinità dei Monti B
Lower Bounds for the Approximate Degree of Block-Composed Functions Justin Thaler.
Randomized query complexity of sabotaged and composed functions Shalev Ben-David and Robin Kothari.
Deterministic Time-Space Tradeoffs for k-SUM Andrea Lincoln, Virginia Vassilevska Williams, Joshua Wang and Ryan Williams.
Total space in Resolution is at least width squared Ilario Bonacina.
Supercritical Space-Width Trade-offs for Resolution Christoph Berkholz and Jakob Nordstrom.
Coding for interactive communication correcting insertions and deletions Mark Braverman, Ran Gelles, Jieming Mao and Rafail Ostrovsky.
13:00-14:20 Lunch Break  
14:20-16:00 Session: A3S2 Track: A
Room:
Aracoeli+Campidoglio
Amplifiers for the Moran Process Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas and David Richerby.
Mixing Time of Markov Chains, Dynamical Systems and Evolution Ioannis Panageas and Nisheeth Vishnoi.
Information Cascades on Arbitrary Topologies Jun Wan, Yu Xia, Liang Li and Thomas Moscibroda.
Analysing Survey Propagation Guided Decimation on Random Formulas Samuel Hetterich.
14:20-16:00 Session: B3S2
Chair: Jean-Francois Raskin Track: B
  Graphs and Databases  
Room:
Trinità dei Monti A
Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity M. Praveen and B Srivathsan.
A Hierarchy of Local Decision Laurent Feuilloley, Pierre Fraigniaud and Juho Hirvonen.
Constraint satisfaction problems for reducts of homogeneous graphs Manuel Bodirsky, Barnaby Martin, Michael Pinsker and András Pongrácz.
Sensitivity of Counting Queries Myrto Arapinis, Diego Figueira and Marco Gaboardi.
14:20-16:00 Session: C3S2 Track: A
Room:
Trinità dei Monti B
Approximation algorithms for aversion k-clustering and local k-median Anupam Gupta, Guru Guruganesh and Melanie Schmidt.
The Non-Uniform k-Center Problem Deeparnab Chakrabarty, Prachi Goyal and Ravishankar Krishnaswamy.
k-center Clustering under Perturbation Resilience Maria-Florina Balcan, Nika Haghtalab and Colin White.

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

Sara Ahmadian and Chaitanya Swamy.
16:00-16:30 Coffee Break  
16:30-18:15

General Assembly

  • Welcome from the president
  • Report from the conference organizers
  • Report from the PC chairs
  • Report on the organization of ICALP 2017
  • Bid for hosting ICALP 2018
  • Report from the secretary of the EATCS
  • Report from the treasurer of the EATCS
  • Report from the president and presentation of the new leadership of the EATCS

Room: Aracoeli+Campidoglio

Friday, 15 July, 2016

  Registration / Support Desk hours (08:30 - 13:00 & 14:00 - 17:00)
09:00-10:00 Invited Talk - Marta Z. Kwiatkowska, Oxford, UK Room: Aracoeli+Campidoglio
10:00-10:30 Coffee Break  
10:30-13:00 Session: A4S1 Track: A
Room:
Aracoeli+Campidoglio
Closing the Gap for Makespan Scheduling via Sparsification Techniques Klaus Jansen, Kim-Manuel Klein and Jose Verschae.
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest Frans Schalekamp, Anke van Zuylen and Suzanne van der Ster.
Robust Assignments via Ear Decompositions and Randomized Rounding David Adjiashvili, Viktor Bindewald and Dennis Michaels.
Tight Analysis of a Multiple-Swap Heuristic for Budgeted Red-Blue Median Zachary Friggstad and Yifeng Zhang.
Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation Gökalp Demirci and Shi Li.
Approximating Directed Steiner Problems via Tree Embedding Bundit Laekhanukit.
10:30-13:00 Session: B4S1
Chair: Volker Diekert Track: B
  Classification and comparisons and language properties  
Room:
Trinità dei Monti A
The Complexity of Rational Synthesis Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini and
Jean-Francois Raskin.
On the Complexity of Grammar-Based Compression over Fixed Alphabets Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras and Markus
L. Schmid.
The complexity of downward closure comparisons Georg Zetzsche.
Anti-Powers in Infinite Words Gabriele Fici, Antonio Restivo, Manuel Silva and Luca Quadro Zamboni.
On Equivalence and Uniformisation Problems for Finite Transducers Emmanuel Filiot, Ismael Jecker, Christof Löding and Sarah Winter.
The Bridge Between Regular Cost Functions and Omega-Regular Languages Thomas Colcombet and Nathanael Fijalkow.
10:30-13:00 Session: C4S1 Track: A
Room:
Trinità dei Monti B
On Percolation and NP-Hardness Huck Bennett, Daniel Reichman and Igor Shinkar.
Correlation Decay and Tractability of CSPs Jonah Brown-Cohen and Prasad Raghavendra.
Tight Sum-of-Squares lower bounds for binary polynomial optimization problems Samuli Leppänen, Adam Kurpisz and Monaldo Mastrolilli.
A parallel repetition theorem for all entangled games Henry Yuen.
Tight Hardness Results for Maximum Weight Rectangles Christos Tzamos, Arturs Backurs and Nishanth Dikkala.
Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices Shi Bai, Damien Stehle and Weiqiang Wen.
13:00-14:20 Lunch Break  
14:20-16:00 Session: A4S2 Track: A
Room:
Aracoeli+Campidoglio
Quasimetric embeddings and their applications Facundo Memoli, Anastasios Sidiropoulos and Vijay Sridhar.
The Johnson-Lindenstrauss Lemma is Optimal for Linear Dimensionality Reduction Kasper Green Larsen and Jelani Nelson.
Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities Yitong Yin.
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost Alexandr Andoni, Assaf Naor and Ofer Neiman.
14:20-16:00 Session: B4S2
Chair: Radu Grigore Track: B
  Linear, commutative and regular structures  
Room:
Trinità dei Monti A
Solutions of Word Equations over Partially Commutative Structures Volker Diekert, Artur Jez and Manfred Kufleitner.
The Taming of the Semi-Linear Set Dmitry Chistikov and Christoph Haase.
Characterizing classes of regular languages using prefix codes of bounded synchronization delay Volker Diekert and Tobias Walter.
14:20-16:00 Session: C4S2 Track: A
Room:
Trinità dei Monti B
The Landscape of Communication Complexity Classes Mika Göös, Toniann Pitassi and Thomas Watson.
Information complexity is computable Mark Braverman and Jon Schneider.
Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound Manoj Prabhakaran and Vinod M Prabhakaran.
On isoperimetric profiles and computational complexity Pavel Hrubes and Amir Yehudayoff.
16:00-16:30 Coffee Break  
16:30-17:20 Session: A4S3 Track: A
Room:
Aracoeli+Campidoglio
Tolerant Testers of Image Properties Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova.
Erasure-Resilient Property Testing Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta and Nithin Mahendra Varma.
16:30-17:20 Session: B4S3 Track: A
Room:
Trinità dei Monti A
Towards Tight Lower Bounds for Range Reporting on the RAM Allan Grønlund and Kasper Green Larsen.
Data Structure Lower Bounds for Document Indexing Problems Peyman Afshani and Jesper Sindahl Nielsen.