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.
|