| |
|
|
|
| Monday 10.7 |
Track A |
|
Track C |
| 8:50 - 9:00 |
Opening |
| 9:00 - 10:00 |
Invited talk - Alon Noga: Additive Approximation for Edge-Deletion Problems |
| 10:00 - 10:30 |
Coffee
Break |
| 10:30 - 12:30 |
A.1 - Graph
Theory |
|
C.1 - Zero
Knowledge and Signatures |
| |
Martin Grohe and Oleg
Verbitsky |
|
Ivan Visconti |
| |
Testing Graph Isomorphism in
Parallel by Playing a Game |
|
Efficient Zero Knowledge on
the Internet |
| |
Amin Coja-Oghlan and Andre
Lanka |
|
Jun Furukawa, Kaoru Kurosawa
and Hideki Imai |
| |
The spectral gap of random
graphs with given expected degrees |
|
An Efficient Compiler from
Sigma-Protocol to 2-move Deniable Zero-Knowledge |
| |
Douglas Carroll, Ashish Goel
and Adam Meyerson |
|
Damien Vergnaud |
| |
Embedding Bounded Bandwidth
Graphs into $\ell_1$ |
|
New Extensions of
Pairing-based Signatures into Universal Designated Verifier Signatures |
| |
Martin Dyer, Leslie Ann
Goldberg and Mike Paterson |
|
Rosario Gennaro and Silvio
Micali |
| |
On counting homomorphisms to
directed acyclic graphs |
|
Independent Zero-Knowledge
Sets |
| 12:30 - 14:30 |
Lunch |
| 14:30 - 16:00 |
A.2 - Quantum Computing |
|
C.2 - Cryptographic protocols |
| |
Ben Reichardt |
|
Daniele Micciancio and
Saurabh Panjwani |
| |
Fault-tolerance threshold
for a distance-three quantum code (Extended abstract) |
|
Corrupting One vs.
Corrupting Many: The Case of Broadcast and Multicast Encryption |
| |
Ronald de Wolf |
|
Pedro Adao and Cedric Fournet. |
| |
Lower Bounds on Matrix
Rigidity via a Quantum Argument |
|
Cryptographically Sound
Implementations for Communicating Processes |
| |
Frederic Magniez, Dominic
Mayers, Michele Mosca and Harold Ollivier |
|
Detlef Kähler, Ralf Küsters
and Thomas Wilke |
| |
Self-Testing of Quantum
Circuits |
|
A Dolev-Yao-based Definition
of Abuse-free Protocols |
| 16:00 - 16:30 |
Coffee
Break |
| 16:30 - 18:00 |
A.3 - Randomness |
|
C.3 -
Secrecy and protocol analysis |
| |
Chia-Jung Lee, Chi-Jen Lu
and Shi-Chun Tsai |
|
Rajeev Alur, Pavol
Cerny and Steve Zdancewic. |
| |
Deterministic
Extractors for Independent-Symbol Sources |
|
Preserving Secrecy under
Refinement |
| |
Jaikumar Radhakrishnan |
|
Michele
Boreale. |
| |
Gap amplification in PCPs
using lazy random walks |
|
Quantifying information
leakage in process calculi |
| |
Magnus Bordewich, Martin
Dyer and Karpinski Marek |
|
S. Delaune, P.
Lafourcade, D. Lugiez and R. Treinen |
| |
Stopping Times,
Metrics and Approximate Counting |
|
Symbolic Protocol Analysis
in Presence of a Homomorphism Operator and Exclusive Or |
| 18:00 - 18:30 |
IBM talk - Birgit Pfitzmann:
Security and privacy challenges in industrial research |
| 18:30 - 20:00 |
Welcome Reception |
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| Tuesday 11.7 |
Track A |
Track A |
Track C |
| 9:00 - 10:00 |
Invited talk - Cynthia Dwork:
Differential Privacy |
| 10:00 - 10:30 |
Coffee
Break |
| 10:30 - 12:30 |
A.4.1 -
Formal Languages |
A.4.2 - Approximation Algorithms
I |
C.4 -
Cryptographic primitives |
| |
Michal Kunc |
Mohit Singh and R Ravi |
Vadim Lyubashevsky and
Daniele Micciancio. |
| |
Algebraic characterization
of the finite power property |
Delegate
and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs |
Generalized Compact
Knapsacks are Collision Resistant |
| |
Turlough Neary and Damien
Woods |
Naveen Garg and Amit Kumar |
Vivien Dubois,
Louis Granboulan and Jacques Stern. |
| |
P-completeness of cellular
automaton Rule 110 |
Better
Algorithms for Minimizing Average Flow-time on Related Machines |
An Efficient Provable
Distinguisher for HFE |
| |
Christos Kapoutsis |
Kamalika Chaudhuri, Satish
Rao, Samantha Riesenfeld and Kunal Talwar |
Krzysztof
Pietrzak. |
| |
Small sweeping
2NFAs are not closed under complement |
A Push-Relabel Algorithm for
Approximating Degree Bounded MSTs |
A Tight Bound for EMAC |
| |
Mikolaj Bojanczyk, Mathias
Samuelides, Thomas Schwentick and Luc Segoufin |
Shuheng Zhou and Satish Rao |
Frederik Armknecht and
Matthias Krause. |
| |
On the expressive power
of pebble automata |
Edge Disjoint
Paths in Moderately Connected Graphs |
Constructing single- and
multi-output Boolean functions with maximal immunity |
| 12:30 - 14:30 |
Lunch |
| 14:30 - 16:00 |
A.5.1 -
Approximation Algorithms II |
A.5.2 -
Graph Algorithms I |
C.5 -
Bounded storage and quantum models |
| |
Leah Epstein and Asaf Levin |
Ramesh Hariharan,
Telikepalli Kavitha and Kurt Mehlhorn |
Danny Harnik and Moni Naor. |
| |
A robust APTAS
for the classical bin packing problem |
A
Faster Deterministic Algorithm for Minimum Cycle Bases in Directed
Graphs |
On Everlasting Security in
the Hybrid Bounded Storage Model |
| |
Subhash Khot and Ashok Kumar
Ponnuswami |
Virginia Vassilevska, Ryan
Williams and Raphael Yuster |
Yevgeniy Dodis and Renato
Renner. |
| |
Better Inapproximability
Results for MaxClique, Chromatic Number and Min-3Lin-Deletion |
Finding
the smallest H-subgraph in real weighted graphs and related problems |
On the Impossibility of
Extracting Classical Randomness Using a Quantum Computer |
| |
Rolf Harren |
Piotr Sankowsk |
Akinori Kawachi and Tomoyuki
Yamakami. |
| |
Approximating the Orthogonal
Knapsack Problem for Hypercubes |
Weighted
Bipartite Matching in Matrix Multiplication Time |
Quantum
Hardcore Functions by Complexity-Theoretical Quantum List Decoding |
| 16:00 - 16:30 |
Coffee
Break |
| 16:30 - 18:00 |
A.6.1
- Algorithms I |
A.6.2
- Complexity I |
C.6 - Foundations |
| |
Irene Finocchi, Fabrizio
Grandoni and Giuseppe F. Italiano |
Arist Kojevnikov |
Iftach Haitner,
Danny Harnik and Omer Reingold. |
| |
Optimal Resilient Sorting
and Searching in the Presence of Memory Faults |
Exponential Lower Bound on
the Size of Static Lovasz-Schrijver Calculus |
Efficient Pseudorandom
Generators from Exponentially Hard One-Way Functions |
| |
Kurt Mehlhorn and Ralf
Osbild |
Lance Fortnow, John
Hitchcock, A. Pavan, N. V. Vinodchandran and Fengming Wang |
Pierre-Alain
Fouque, Jacques Stern, David Pointcheval and Sebastien Zimmer. |
| |
Reliable and Efficient
Computational Geometry via Controlled Perturbation |
Extracting Kolmogorov
Complexity with Applications to Dimension Zero-One Laws |
Hardness of Distinguishing
the MSB or LSB of Secret Keys in Diffie-Hellman and Related Schemes |
| |
I. Caragiannis, M. Flammini, C. Kaklamanis,
P. Kanellopoulos and L. Moscardelli |
Parikshit Gopalan, Phokion
Kolaitis, Elitza Maneva and Christos Papadimitriou |
Ricardo Corin and Jerry den
Hartog. |
| |
Tight bounds for selfish and
greedy load balancing |
The
Connectivity of Boolean Satisfiability: Computational and Structural
Dichotomies |
A Probabilistic Hoare-style
logic for Game-based Cryptographic Proofs |
| 18:00 - 19:30 |
EATCS
Assembly |
| |
|
|
|
| |
|
|
|
| |
|
|
|
| Wednesday 12.7 |
Track A |
Track B |
Track C |
| 9:00 - 10:00 |
Invited talk - Simon Peyton Jones:
Composable memory transactions |
| 10:00 - 10:30 |
Coffee
Break |
| 10:30 - 12:30 |
A.7 - Data
Structures and Linear Algebra |
B.1 - Games |
C.7 -
Multi-party protocols |
| |
Richard Cole, Tsvi
Kopelowitz and Moshe Lewenstein |
Wieslaw Zielonka and Hugo
Gimbert |
Duong Hieu
Phan, Rei Safavi-Naini and Dongvu Tonien. |
| |
Suffix
Trays and Suffix Trists: Structures for Faster Text Indexing |
Deterministic
priority mean-payoff games as limits
of discounted games |
Generic Construction of
Hybrid Public Key Traitor Tracing with Full-Public-Traceability |
| |
Alexander Golynski |
Kousha Etessami and Mihalis
Yannakakis. |
Douglas Wikström and Jens
Groth. |
| |
Optimal lower
bounds for rank and select indexes |
Recursive Concurrent
Stochastic Games |
An Adaptively Secure
Mix-Net Without Erasures |
| |
A. Kaporis, C. Makris, S.
Sioutas, A. Tsakalidis, K. Tsichlas and C. Zaroliagis |
Eryk Kopczynski |
Tamir Tassa and Nira Dyn. |
| |
Dynamic Interpolation Search
Revisited |
Half-positional
Determinacy of Infinite Games |
Multipartite Secret Sharing
by Bivariate Interpolation |
| |
Gudmund Skovbjerg Frandsen
and Peter Frands Frandsen |
Colin Stirling |
Michel
Abdalla, Dario Catalano, Alexander Dent, John Malone-Lee, Gregory Neven and
Nigel Smart. |
| |
Dynamic Matrix Rank |
A game-theoretic approach to
deciding higher-order matching |
Identity-Based Encryption
Gone Wild |
| 12:30 - 14:30 |
Lunch |
| 14:30 - 20:00 |
Excursion |
| |
|
|
|
| |
|
|
|
| |
|
|
|
| Thursday 13.7 |
Track A |
Track A |
Track B |
| 9:00 - 10:00 |
Invited talk - Prakash Panangaden:
The One Way to Quantum Computation |
| 10:00 - 10:30 |
Coffee
Break |
| 10:30 - 12:30 |
A.8.1 -
Graphs |
A.8.2 - Complexity II |
B.2 - Semantics |
| |
Xin He and Huaming Zhang |
Thomas Thierauf, Minh Thanh
Hoang and Meena Mahajan |
Kohei Honda, Martin Berger
and Nobuko Yoshida |
| |
Nearly
Optimal Visibility Representations of Plane Graphs |
On the unique bipartite
perfect matching Problem |
Descriptive and Relative
Completeness of Logics for Higher-Order Functions |
| |
Hristo Djidjev and Imrich
Vrt'o |
John Hitchcock and A. Pavan |
Paul Blain Levy |
| |
Planar Crossing Numbers of
Genus g Graphs |
Comparing Reductions to
NP-Complete Sets |
Jumbo Lambda Calculus |
| |
Toshihiro Fujito |
Deeparnab Chakrabarty,
Aranyak Mehta and Vijay Vazirani |
Esfandiar Haghverdi |
| |
How to trim an MST: A
2-approximation algorithm for minimum cost tree cover |
Towards
a Theory of Intelligent Design or Design as Easy as Optimization |
Typed GoI for Exponentials |
| |
Guy Kortsarz and Zeev Nutov |
Xi Chen and Xiaotie Deng |
Stefano Guerrini and
Patrizia Marzuoli |
| |
Tight Approximation
Algorithm for Connectivity Augmentation Problems |
On the
Complexity of 2D Discrete Fixed Point Problem |
Commutative Locative
Quantifiers for Multiplicative Linear Logic |
| 12:30 - 14:30 |
Lunch |
| 14:30 - 16:00 |
A.9.1 - Game Theory I |
A.9.2 - Algorithms |
B.3- Automata I |
| |
Burkhard Monien, Martin
Gairing and Karsten Tiemann |
David Doty, Jack Lutz and
Satyadev Nandakumar |
Filip Murlak |
| |
Routing
(Un-) Splittable Flow in Games with Player-Specific Linear Latency
Functions |
Finite-State Dimension
and Real Arithmetic |
The Wadge Hierarchy of
Deterministic Tree Languages |
| |
Constantinos Daskalakis,
Alex Fabrikant and Christos H. Papadimitriou |
Thore Husfeldt and Andreas
Björklund |
Patricia Bouyer, Serge
Haddad and Pierre-Alain Reynier |
| |
The Game World is Flat: The
Complexity of Nash Equilibria in Succinct Games |
Exact Algorithms for Exact
Satisfiability and Number of Perfect Matchings |
Timed Petri Nets and Timed
Automata: On the Discriminating Power of Zeno Sequences |
| |
Roberto Cominetti, Jose R.
Correa and Nicolas E. Stier-Moses |
Paolo Ferragina, Giovanni
Manzini and Raffaele Giancarlo |
Tomasz Jurdzinski |
| |
Network Games with Atomic
Players |
The Myriad Virtues of Wavelet
Trees |
On Complexity of Grammars
Related to the Safety Problem |
| 16:00 - 16:30 |
Coffee
Break |
| 16:30 - 18:00 |
Award Ceremony |
| 20:00 - 23:00 |
ICALP Banquet |
| |
|
|
|
| |
|
|
|
| |
|
|
|
| Friday 14.7 |
Track A |
Track B |
|
| 9:00 - 10:30 |
A.10 - Game Theory II |
B.4 - Models |
|
| |
Dimitris Fotakis, Spyros
Kontogiannis and Paul Spirakis |
Rasmus Ejlers Møgelberg |
|
| |
Atomic Congestion Games
among Coalitions |
Interpreting Polymorphic FPC
into domain theoretic models of parametric polymorphism |
|
| |
Kasturi Varadarajan, Bruno
Codenotti and Luis Rademacher |
Radha Jagadeesan, Alan
Jeffrey, Corin Pitcher and James Riely. |
|
| |
Computing
Equilibrium Prices in Exchange Economies with Tax Distortions |
LRBAC: Programming With
Role-Based Access Contro |
|
| |
V. Auletta, R. De Prisco, P.
Penna, G. Persiano and C. Ventre |
Juhani Karhumaki, Michal
Kunc and Alexander Okhotin |
|
| |
New Constructions
of Mechanisms with Verification |
Communication of two
stacks and rewriting |
|
| 10:30 -- 11:00 |
Coffee
Break |
| 11:00 -- 13:00 |
A.11 -
Networks, Circuits and Regular Expressions |
B.5 - Equations |
|
| |
A. Fiat, H. Kaplan., M.Levy, S. Olonetsky
and R. Shabo |
Luca Aceto, Taolue Chen, Wan
Fokkink and Anna Ingolfsdottir |
|
| |
On
the Price of Stability for Designing Undirected Networks with Fair Cost
Allocations |
On the Axiomatizability of
Priority |
|
| |
Amos Korman and David Peleg |
Luca Aceto, Wan Fokkink,
Anna Ingolfsdottir and Bas Luttik |
|
| |
Dynamic Routing Schemes
for General Graphs |
A finite equational base for
CCS with left merge and communication merge |
|
| |
Kei Uchizawa, Rodney Douglas
and Wolfgang Maass |
Markus Lohrey and Géraud
Sénizergues |
|
| |
Energy Complexity and
Entropy of Threshold Circuits |
Theories of
HNN-extensions and amalgamated products |
|
| |
Philip Bille |
Wong Karianto, Aloys Krieg
and Wolfgang Thomas |
|
| |
New Algorithms for Regular
Expression Matching |
On
Intersection Problems for Polynomially Generated Sets |
|
| 13:00 - 14:30 |
Lunch |
| 14:30 - 16:00 |
A.12 - Fixed Parameter Complexity and
Approximation Algorithms |
B.6 - Logics |
|
| |
Dániel Marx |
Ittai Balaban, Amir Pnueli
and Lenore Zuck. |
|
| |
A Parameterized View on
Matroid Optimization Problems |
Invisible Safety of
Distributed Protocols |
|
| |
G. Blelloch, K. Dhamdhere,
E. Halperin, R. Ravi, R. Schwartz and S. Sridhar |
Piero A. Bonatti, Carsten
Lutz, Aniello Murano and Moshe Y. Vardi |
|
| |
Fixed
Parameter tractability of Binary Near-Perfect Phylogenetic Tree
Reconstruction |
The Complexity of Enriched
mu-Calculi |
|
| |
G. Baier, T. Erlebach, A.
Hall, E. Koehler, H. Schilling and M. Skutella |
Michael Benedikt and
Christoph Koch |
|
| |
Length-Bounded Cuts and Flows |
Interpreting Tree-to-Tree
Queries |
|
| 16:00 - 16:30 |
Coffee
Break |
| 16:30 - 18:00 |
A.13 |
B.7 - Automata II |
|
| |
Amin Coja-Oghlan |
Blaise Genest and Anca
Muscholl |
|
| |
An
adaptive spectral heuristic for partitioning random graphs |
Constructing
Exponential-size Deterministic Zielonka Automata |
|
| |
Jin-Yi Cai and Vinay
Choudhary |
Marius Bozga Radu Iosif and
Yassine Lakhnech |
|
| |
Some Results on Matchgates
and Holographic Algorithms |
Flat Parametric Counter
Automata |
|
| |
Julian Mestre |
Qiqi Yan |
|
| |
Weighted Popular Matchings |
Lower Bounds for
Complementation of omega-Automata via the Full Automata Technique |
|
| 18:00 - 18:10 |
Closing |
|
|
|
|
