How to print this document and errata for the printed version

ICALP/LICS/LC/PPDP 2007 & Satellite Workshops

Schedule

Overview
Sunday, July 8 FCS-ARSPA
SE		 WCAN
SE
Monday, July 9 ICALP GOCP
room 222 (+ GE)		 PAuL
SW		 SOS
SE (+ SW)
Tuesday, July 10 LICS
GE
(+ GW/CHEM)
Wednesday, July 11
Thursday, July 12
Friday, July 13
Saturday, July 14 Logic Colloquium PPDP
SE		 TRSH
room 325
Sunday, July 15 LCC
SW/room 141		 DCM
room 222		 TMCNAA
room 223 (+ 222)
Monday, July 16
Tuesday, July 17
Wednesday, July 18
Thursday, July 19
Lecture rooms: detailed information about lecture rooms and their equipment can be found on the venue page.
Duration of talks:
  • ICALP, LICS, PPDP: presentation of regular papers should last no longer than 25 minutes; remaining 5 minutes are reserved for questions and discussion.
  • Logic Colloquium: talks scheduled for 20, 30, 45 and 60 minutes should last, respectively, 15, 25, 40 and 50 minutes; remaining 5 (respectively 10) minutes are reserved for questions and discussion.

Sunday, July 8th
FCS-ARSPA WCAN
08:50-09:00 Welcome to FCS-ARSPA and WCAN, SE
09:00-09:30 Toby Murray and Gavin Lowe: Authority Analysis for Least Privilege Environments, SE
09:30-10:00 Richard Chang and Vitaly Shmatikov: Formal Analysis of Authentication in Bluetooth Device Pairing, SE
10:00-10:30 Todd R. Andel and Alec Yasinsac: Automated Security Analysis of Ad Hoc Routing Protocols, SE
10:30-11:00 Ender Yüksel, Hanne Riis Nielson, Christoffer Rosenkilde Nielsen and Mehmet Bülent Örencik: A Secure Simplification of the PKMv2 Protocol in IEEE 802.16e-2005, SE
11:00-11:30 coffee break
11:30-12:00 Stéphanie Delaune and Veronique Cortier: Deciding knowledge in security protocols for monoidal equational theories, SE
12:00-12:30 Adel Bouhoula and Florent Jacquemard: Verifying Regular Trace Properties of Security Protocols with Explicit Destructors and Implicit Induction, SE
12:30-13:00 Simon Kramer: The Meaning of a Cryptographic Message via Hypothetical Knowledge and Provability, SE
13:00-14:00 lunch
14:00-14:30 Zhiyao Liang and Rakesh Verma: Secrecy Checking of Protocols: Solution of an Open Problem, SE
14:30-15:00 Kazuki Yoneyama, Yuichi Kokubun and Kazuo Ohta: A Security Analysis on Diffie-Hellman Key Exchange against Adaptive Adversaries using Task-Structured PIOA, SE
15:00-16:00 Invited lecture: Srdjan Capkun (ETH Zurich): From Securing Navigation Systems to Securing Wireless Communication Through Location-Awareness, SE
16:00-16:30 coffee break
16:30-17:00 Vanesa Daza, Javier Herranz, Paz Morillo and Carla Rafols: Threshold Broadcast Encryption with Shorter Ciphertexts, SE
17:00-17:30 Nouha Oualha and Yves Roudier: Securing Ad Hoc Storage through Probabilistic Cooperation Assessment, SE
17:30-18:00 Keith M. Martin and Maura Paterson: An Application-Oriented Framework for Wireless Sensor Network Key Establishment, SE
18:00-18:20 Maarit Hietalahti: A Clustering-based Group Key Agreement Protocol for Ad-Hoc Networks (work in progress), SE
18:20-18:40 Giovanni Di Crescenzo: A Survey on Cryptography for Vehicular Networks, SE
18:40-19:00 Sylvia Encheva and Sharil Tumin: Security Administration of Protected Web Resources (work in progress), SE
19:00-20:00
20:00- Workshop dinner


Monday, July 9th
ICALP, track A1 ICALP, track A2 GOCP PAuL SOS
Joint ICALP/GOCP session: Lars Arge, GE Invited lecture: Paweł Sobociński (Southampton): A well-behaved LTS for the π-calculus, SE
09:00-10:00 Invited lecture: Bernard Chazelle (Princeton University): Ushering in a New Era of Algorithm Design, GE
Session A1: Xiaotie Deng, GE Session A2: Lars Arge, GW Invited lecture: Antonin Kucera (Masaryk University, Brno): PCTL formulae as a winning objective in stochastic games, SW Traian Serbanuta, Grigore Rosu and Jose Meseguer: A Rewriting Logic Approach to Operational Semantics, SE
10:00-10:15 Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs: Competitive Algorithms for Due Date Scheduling, GE Rajeev Motwani, Rina Panigrahy and Ying Xu: Estimating Sum by Weighted Sampling, GW
10:15-10:30 Emmanuel Bresson, Christian Cachin and Jörg Schwenk: Welcome to the Workshop, room 222
10:30-11:00 George Christodoulou, Elias Koutsoupias and Annamária Kovács: Mechanism Design for Fractional Scheduling on Unrelated Machines, GE Johannes Blömer and Stefanie Naewe: Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima, GW Łukasz Krzywiecki, Mirosław Kutyłowski and Maciej Nikodem: General Anonymous Key Broadcasting via Lagrangian Interpolation, room 222 Patrick Cousot and Radhia Cousot: Bi-inductive Structural Semantics, SE
11:00-11:30 coffee break
Session A3: Loukas Georgiadis, GE Session A4: Ming Kao, GW Invited lecture: Giuseppe Ateniese (Johns Hopkins University): Practical Group Signatures: Are we there yet?, room 222 Tomas Brazdil and Vojtech Forejt: Strategy Synthesis, SW David Frutos Escrig and Carlos Gregorio Rodriguez: Simulations up-to and Canonical Preorders, SE
11:30-12:00 Seth Pettie: Low Distortion Spanners, GE Kazuo Iwama, Harumichi Nishimura, Rudy Raymond and Shigeru Yamashita: Unbounded-Error One-Way Classical and Quantum Communication Complexity, GW
12:00-12:15 André Berger and Michelangelo Grigni: Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs, GE Ashley Montanaro and Andreas Winter: A Lower Bound on Entanglement-Assisted Quantum Communication Complexity, GW Harald Fecher and Heiko Schmidt: Process Algebra Having Inherent Choice: Revised Semantics for Concurrent Systems, SE
12:15-12:30 Axel Legay, Andrzej S. Murawski, Joel Ouaknine and James Worrell: On Automated Verification of Probabilistic Programs, SW
12:30-13:00 Amos Korman: Labeling Schemes for Vertex Connectivity, GE Paul Beame, Matei David, Toniann Pitassi and Philipp Woelfel: Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity, GW Emmanuel Bresson and Mark Manulis: Malicious Participants in Group Key Exchange: Key Control and Contributiveness in the Shadow of Trust, room 222 Astrid Kiehn: An operational semantics for shared messaging communication, SE
13:00-14:30 lunch
Session A5: Lars Arge, GE Session A6: Xiaotie Deng, GW Ling Cheung, Joseph A. Cooley, Roger Khazan and Calvin Newport: Collusion-Resistant Group Key Management Using Attribute-Based Encryption, room 222 Evan Tzanis: A note on probabilistic logics, SW Iain Phillips and Irek Ulidowski: Reversibility and models for concurrency, SE
14:30-15:00 Erik D. Demaine, Shay Mozes, Benjamin Rossman and Oren Weimann: An Optimal Decomposition Algorithm for Tree Edit Distance, GE Chi-Jen Lu, Shi-Chun Tsai and Hsin-Lung Wu: On the Complexity of Hard-Core Set Constructions, GW
15:00-15:15 Dragan Bošnački, Edith Elkind, Blaise Genest and Doron Peled: On Commutativity Based Edge Lean Search, GE Ryan O'Donnell and Karl Wimmer: Approximation by DNF: Examples and Counterexamples, GW Michel Abdalla, Eike Kiltz and Gregory Neven: Generalized Key Delegation for Hierarchical Identity-Based Encryption, room 222 MohammadReza Mousavi and Michel Reniers: A Congruence Rule Format with Universal Quantification, SE
15:15-15:30 Verena Wolf: Modelling of Biochemical Reactions by Stochastic Automata Networks, SW
15:30-16:00 Irit Katriel, Claire Kenyon-Mathieu and Eli Upfal: Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems, GE Peter Bürgisser and Felipe Cucker: Exotic Quantifiers, Complexity Classes, and Complete Problems, GW Aggelos Kiayias and Hong-Sheng Zhou: Hidden Identity Based Signatures, room 222 Jesper Bengtson and Joachim Parrow: A completeness proof for bisimulation in the π-calculus using Isabelle, SE
16:00-16:30 coffee break
16:30-17:30 ICALP Awards Ceremony, GE Invited lecture: Anna Lysyanskaya (Brown University): Compact Ecash and Applications, room 222 Invited lecture: Catuscia Palamidessi (LIX, Ecole Polytechnique): Information-hiding protocols as opaque channels, SW
17:30-18:00 Alberto N. Escalante, Hans Löhr and Ahmad-Reza Sadeghi: An Unsplittable Privacy-Protecting Multi-Coupon Scheme for a Group of Vendors, room 222


Tuesday, July 10th
ICALP, track A ICALP, track C LICS
Joint ICALP session: Christian Cachin, GW Session 1: Type Theory, GE
09:00-09:30 Invited lecture: Ivan Damgård (Aarhus University): A "Proof-Reading" of some Issues in Cryptography, GW Andreas Abel, Thierry Coquand and Peter Dybjer: Dependent Types with Universes via Normalization-by-Evaluation, GE
09:30-10:00 Colin Riba: Strong Normalization as Safe Interaction, GE
Session A7: Thomas Erlebach, GW Session C1: Stefan Dziembowski, SW Wojciech Moczydłowski: A Dependent Set Theory, GE
10:00-10:30 Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky and Shakhar Smorodinsky: Online Conflict-Free Colorings for Hypergraphs, GW Yuval Ishai, Tal Malkin, Martin J. Strauss and Rebecca N. Wright: Private Multiparty Sampling and Approximation of Vector Combinations, SW
Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas and Andrzej Pelc: Distributed Computing with Advice: Information Sensitivity of Graph Coloring, GW Nenad Dedic and Payman Mohassel: Constant-Round Private Database Queries, SW Session 2: Security, GE
10:30-11:00 Mika Cohen and Mads Dam: A Complete Axiomatization of Knowledge and Cryptography, GE
11:00-11:30 coffee break
Session A8: Branislav Rovan, GW Session C2: Christian Cachin, SW Session 3: Computational Proof Theory, GE
11:30-12:00 Benoît Larose and Pascal Tesson: Universal Algebra and Hardness Results for Constraint Satisfaction Problems, GW Tal Moran, Moni Naor and Gil Segev: Deterministic History-Independent Strategies for Storing Information on Write-Once Memories, SW Paul Brauner, Clément Houtmann and Claude Kirchner: Principles of Superdeduction, GE
12:00-12:30 Albert Atserias, Andrei Bulatov and Victor Dalmau: On the power of k-consistency, GW Aggelos Kiayias and Hong-Sheng Zhou: Trading Static for Adaptive Security in Universally Composable Zero-Knowledge, SW James Brotherston and Alex Simpson: Complete Sequent Calculi for Induction and Infinite Descent, GE
Nachum Dershowitz and Iddo Tzameret: Complexity of Propositional Proofs Under a Promise, GW Bruce Kapron, Lior Malka and Venkatesh Srinivasan: A Characterization of Non-Interactive Instance-Dependent Commitment-Schemes (NIC), SW Short presentations 1, GE
12:30-12:40 Mikołaj Bojańczyk: The common fragment of CTL and LTL needs existential modalities, GE
12:40-12:50 James Worthington: A Bisimulation-based Proof System for the Equational Theory of Kleene Algebra, GE
12:50-13:00
13:00-14:30 lunch
Session A9: Jan Arne Telle, GW Session C3: Tal Malkin, SW Invited lecture: Thomas C. Hales (University of Pittsburgh): The Kepler Conjecture and the Flyspeck Project, GE
14:30-15:00 Michael R. Fellows, Guillaume Fertin, Danny Hermelin and Stéphane Vialette: Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs, GW Rafail Ostrovsky, Omkant Pandey and Amit Sahai: Private Locally Decodable Codes, SW
15:00-15:30 Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich and Saket Saurabh: Parameterized Algorithms for Directed Maximum Leaf Problems, GW Mihir Bellare and Thomas Ristenpart: Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms, SW
15:30-16:00 Martin Grohe and Magdalena Grüber: Parameterized Approximability of the Disjoint Cycle Problem, GW Mihir Bellare, Chanathip Namprempre and Gregory Neven: Unrestricted Aggregate Signatures, SW LICS awards ceremony, GE
16:00-16:30 Jiong Guo and Rolf Niedermeier: Linear Problem Kernels for NP-Hard Problems on Planar Graphs, GW Nishanth Chandran, Jens Groth and Amit Sahai: Ring Signatures of Sub-linear Size without Random Oracles, SW
16:30-17:00 coffee break
EATCS Assembly, GW Session 4: Timed and Stochastic Systems, GE
17:00-17:30 Hugo Gimbert and Wiesław Zielonka: Limits of Multi-Discounted Markov Decision Processes, GE
17:30-18:00 Luca de Alfaro, Rupak Majumdar, Vishwanath Raman and Marielle Stoelinga: Game Relations and Metrics, GE
18:00-18:30 Patricia Bouyer, Nicolas Markey, Joel Ouaknine and James Worrell: The Cost of Punctuality, GE
18:30-20:00
20:00- Welcome reception in Oratorium Marianum


Wednesday, July 11th
ICALP, track A ICALP, track B ICALP, track C LICS
Joint ICALP session: Witold Charatonik, GW Session 5: Verification, GE
09:00-09:30 Invited lecture: Fred B. Schneider (Cornell University): Credentials-Based Authorization: Evaluation and Implementation, GW Rajeev Alur, Marcelo Arenas, Pablo Barcelo, Kousha Etessami, Neil Immerman and Leonid Libkin: First-order and Temporal Logics for Nested Words, GE
09:30-10:00 Salvatore La Torre, Madhusudan Parthasarathy and Gennaro Parlato: A Robust Class of Context-Sensitive Languages, GE
Session A10: Thomas Erlebach, GW Session B1: Pierpaolo Degano, SW Session C4: Anna Lysyanskaya, SE Francesco Ranzato and Francesco Tapparo: A New Efficient Simulation Equivalence Algorithm, GE
10:00-10:30 Noga Alon and Shai Gutner: Balanced Families of Perfect Hash Functions and Their Applications, GW Lutz Schröder and Dirk Pattinson: Modular Algorithms for Heterogeneous Modal Logics, SW Ben Adida and Douglas Wikström: Offline/Online-Mixing, SE
10:30-11:00 Ioannis Caragiannis, Michele Flammini and Luca Moscardelli: An Exponential Improvement on the MST Heuristic for the Minimum Energy Broadcasting in Ad Hoc Wireless Networks, GW Luke Simon, Ajay Bansal, Ajay Mallya and Gopal Gupta: Co-Logic Programming: Extending Logic Programming with Coinduction, SW Jun Furukawa and Nuttapong Attrapadung: Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys, SE Detlef Kaehler, Ralf Kuesters and Tomasz Truderung: Infinite State AMC-Model Checking for Cryptographic Protocols, GE
11:00-11:30 coffee break
Session A11: Lars Arge, GW Session B2: Lidia Tendera, SW Mikołaj Bojańczyk: Two-way unary temporal logic over trees, GE
11:30-12:00 Meng He, J. Ian Munro and S. Srinivasa Rao: Succinct Ordinal Trees Based on Tree Covering, GW Manuel Bodirsky, Hubie Chen, Jan Kára and Timo von Oertzen: Maximal Infinite-Valued Constraint Languages, SW
12:00-12:30 Ankur Gupta, Wing-Kai Hon, Rahul Shah and Jeffrey Scott Vitter: A Framework for Dynamizing Succinct Data Structures, GW Albert Atserias, Andrei Bulatov and Anuj Dawar: Affine Systems of Equations and Counting Infinitary Logic, SW Marcin Jurdziński and Ranko Lazic: Alternation-Free Modal μ-Calculus for Data Trees, GE
12:30-13:00 Gianni Franceschini and S. Muthukrishnan: In-Place Suffix Sorting, GW Stephan Kreutzer, Martin Otto and Nicole Schweikardt: Boundedness of Monadic FO over Acyclic Structures, SW Angelo Montanari and Gabriele Puppis: A Contraction Method to Decide MSO Theories of Trees, GE
13:00-14:30 lunch
14:30-22:45 Excursion


Thursday, July 12th
ICALP, track A ICALP, track B LICS
Joint ICALP session: Marek Piotrów, GW Session 6: Constraints, GE
09:00-09:30 Invited lecture: Fedor V. Fomin (University of Bergen): Subexponential Parameterized Algorithms, GW Laszlo Egri, Benoit Larose and Pascal Tesson: Symmetric Datalog and Constraint Satisfaction Problems in Logspace, GE
09:30-10:00 Manuel Bodirsky and Hubie Chen: Quantified Equality Constraints, GE
Session A12: Xiaotie Deng, GW Session B3: Eugenio Moggi, SW Paweł Idziak, Petar Markovic, Ralph McKenzie, Matt Valeriote and Ross Willard: Tractability and learnability arising from algebras with few subpowers, GE
10:00-10:30 Amos Fiat, Haim Kaplan, Meital Levy and Svetlana Olonetsky: Strong Price of Anarchy for Machine Load Balancing, GW Marcelo Fiore and Chung-Kil Hur: Equational Systems and Free Constructions, SW
Spyros C. Kontogiannis and Paul G. Spirakis: Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games, GW Ichiro Hasuo, Bart Jacobs and Tarmo Uustalu: Categorical Views on Computations on Trees, SW Session 7: Proof Complexity, GE
10:30-11:00 Steven James Perron: Examining The Fragments of G, GE
11:00-11:30 coffee break
Session A13: Branislav Rovan, GW Session B4: Andrzej Murawski, SW Phuong Nguyen: Separating DAG-Like and Tree-Like Proof Systems, GE
11:30-12:00 Jin-Yi Cai and Pinyan Lu: Holographic Algorithms: The Power of Dimensionality Resolved, GW James Laird: A Fully Abstract Trace Semantics for General References, SW
12:00-12:30 Laurent Bienvenu and Wolfgang Merkle: Reconciling data compression and Kolmogorov complexity, GW Jonathan K. Lee, Jens Palsberg and Fernando Magno Quintão Pereira: Aliased Register Allocation for Straight-line Programs is NP-Complete, SW Phuong Nguyen and Stephen A. Cook: The Complexity of Proving the Discrete Jordan Curve Theorem, GE
Gary L. Miller, Todd Phillips and Donald Sheehy: Size Competitive Meshing without Large Angles, GW Sylvain Schmitz: Conservative Ambiguity Detection in Context-Free Grammars, SW Session 8: Finite Model Theory, GE
12:30-13:00 Anuj Dawar, Martin Grohe and Stephan Kreutzer: Locally Excluding a Minor, GE
13:00-14:30 lunch
Session A14: Marcin Bieńkowski, GW Session B5: Rob van Glabbeek, SW Invited lecture: Phokion Kolaitis (IBM Almaden Research Centre): Reflections on Finite Model Theory, GE
14:30-15:00 Sudipto Guha and Andrew McGregor: Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming, GW Naoki Kobayashi and Takashi Suto: Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the π-Calculus, SW
15:00-15:30 Michael Elkin: Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners, GW Gerald Lüttgen and Walter Vogler: Ready Simulation for Concurrency: It's Logical!, SW
15:30-16:00 Matthew Chu, Sampath Kannan and Andrew McGregor: Checking and Spot-Checking the Correctness of Priority Queues, GW Jean Goubault-Larrecq: Continuous Capacities on Continuous State Spaces, SW Balder ten Cate, Jouko Vaananen and Johan van Benthem: Lindström theorems for fragments of first-order logic, GE
16:00-16:30 coffee break
Session A15: Ming Kao, GW Session B6: Tomasz Truderung, SW Session 9: Concurrency and Process Calculus, GE
16:30-17:00 Amin Coja-Oghlan, Konstantinos Panagiotou and Angelika Steger: On the Chromatic Number of Random Graphs, GW Bernard Boigelot and Julien Brusten: A Generalization of Cobham's Theorem to Automata over Real Numbers, SW Davide Sangiorgi, Naoki Kobayashi and Eijiro Sumii: Environment Bisimulations for Higher-Order Languages, GE
17:00-17:30 Noga Alon, Amin Coja-Oghlan, Hiệp Hàn, Mihyun Kang, Vojtěch Rödl and Mathias Schacht: Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions, GW Thomas Brihaye, Thomas A. Henzinger, Vinayak S. Prabhu and Jean-François Raskin: Minimum-Time Reachability in Timed Games, SW Marcello Bonsangue and Alexander Kurz: π-Calculus in Logical Form, GE
17:30-18:00 Markus Bläser and Holger Dell: Complexity of the Cover Polynomial, GW Marcin Jurdziński and Ashutosh Trivedi: Reachability-Time Games on Timed Automata, SW Yuxin Deng, Rob van Glabbeek, Matthew Hennessy, Carroll Morgan and Chenyi Zhang: Characterising Testing Preorders for Finite Probabilistic Processes, GE
18:00-18:30 Hugo Gimbert and Wiesław Zielonka: Perfect Information Stochastic Priority Games, SW
18:30-19:30
19:30- Cocktail reception in the Town Hall


Friday, July 13th
ICALP, track B LICS
ICALP/LICS joint session: Andrzej Tarlecki, GW Session 10: Semantics of Programming Languages
09:00-10:00 Invited lecture: Gordon Plotkin (University of Edinburgh): The Algebraic Theory of Effects, GW
10:00-10:30 coffee break
Session B7: Wolfgang Thomas, GW Bartek Klin: Bialgebraic operational semantics and modal logic, GE
10:30-11:00 Henrik Björklund and Mikołaj Bojańczyk: Bounded Depth Data Trees, GW
11:00-11:30 Wong Karianto and Christof Löding: Unranked Tree Automata with Sibling Equalities and Disequalities, GW Rasmus Ejlers Mogelberg and Alex Simpson: Relational Parametricity for Computational Effects, GE
11:30-12:00 Marcelo Arenas, Pablo Barceló and Leonid Libkin: Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization, GW Francois Pottier: Static Name Control for FreshML, GE
12:00-12:30 Thomas Colcombet: A Combinatorial Theorem for Trees, GW Cristiano Calcagno, Peter O'Hearn and Hongseok Yang: Local Action and Abstract Separation Logic, GE
12:30-14:00 lunch
ICALP/LICS joint session: Leszek Pacholski, GW
14:00-15:00 Invited lecture: Michael O. Rabin (Harvard University and Hebrew University): Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations, and Applications, GW
15:00-15:30 coffee break
Session B8: Doron Peled, GW Session 11: Game Semantics, GE
15:30-16:00 Anuj Dawar, Martin Grohe, Stephan Kreutzer and Nicole Schweikardt: Model Theory Makes Formulas Large, GW Paul-André Melliès and Nicolas Tabareau: Resource Modalities in Game Semantics, GE
16:00-16:30 Laura Bozzelli and Salvatore La Torre: Decision Problems for Lower/Upper Bound Parametric Timed Automata, GW Nikos Tzevelekos: Full abstraction for nominal general references, GE
Gennaro Parlato and Salvatore La Torre: On the Complexity of LTL Model-Checking of Recursive State Machines, GW Short presentations 2, GE
16:30-16:40 Andrzej Murawski: On the effect of bad variables, GE
16:40-16:50 Manas Patra: Descriptive characterization of quantum circuits (Abstract), GE
16:50-17:00
17:00-17:30
17:30-18:30 Michael O. Rabin's honorary PhD ceremony in Aula Leopoldina
18:30-19:15
19:15- LICS business meeting (drinks and snacks offered by Google™), GE


Saturday, July 14th
LICS LC LC LC LC PPDP TRSH
08:00-09:00 LC registration, room 109
Session 12: Linear Logic, GE LC opening ceremony, GW Nick Benton and Uri Zarfaty: Formalizing and Verifying Semantic Type Soundness of a Simple Compiler, SE
09:00-09:15 Ulrich Schoepp: Stratified Bounded Affine Logic for Logarithmic Space, GE
09:15-09:30 Opening ceremony, room 325
09:30-10:00 Patrick Baillot, Paolo Coppola and Ugo Dal Lago: Light Logics and Optimal Reduction: Completeness and Complexity, GE Invited lecture: Bjørn Kjos-Hanssen (Cornell): Brownian Motion and Kolmogorov Complexity, GW William C. Benton and Charles N. Fischer: Interactive, Scalable, Declarative Program Analysis: From Prototype to Implementation, SE Tutorial: Carsten Witt (University of Dortmund): Theory of Randomized Search Heuristics in Combinatorial Optimization, room 325
10:00-10:30 Paulo Oliva: Modified Realizability Interpretation of Classical Linear Logic, GE Leslie De Koninck, Tom Schrijvers and Bart Demoen: User-definable Rule Priorities for CHR, SE
10:30-11:00 coffee break
11:00-11:30 Invited lecture: Martin Hyland (Cambridge): Combinatorics of Proofs, GW Invited lecture: Konstantinos Sagonas (Uppsala University): Detecting bugs in Erlang programs using static analysis, SE Per Kristian Lehre and Xin Yao: Runtime Analysis of (1+1) EA on Computing Unique Input Output Sequences, room 325
11:30-12:00 Joachim Reichel and Martin Skutella: Maximum Flow and Minimum Cut, room 325
12:00-12:30 Invited lecture: Rosalie Iemhoff (Utrecht): Skolemization in Constructive Theories, GW Salvador Lucas: Practical use of polynomials over the reals in proofs of termination, SE Tobias Friedrich, Nils Hebbinghaus and Frank Neumann: Plateaus Can Be Harder in Multi-Objective Optimization, room 325
12:30-13:00 Invited lecture: Alex Simpson (Edinburgh): Non-well-founded Proofs, GW Christian Skalka: Type Safe Dynamic Linking for JVM Access Control, SE Discussion, room 325
13:00-14:30 lunch
14:30-15:00 Invited lecture: Colin Stirling (Edinburgh): Higher-Order Matching, Games and Automata, GW Sebastian Fischer and Herbert Kuchen: Systematic Generation of Glass-Box Test Cases for Functional Logic Programs, SE Dirk Sudholt: On the Parametrization of Memetic Evolutionary Algorithms, room 325
15:00-15:30 James Cheney and Alberto Momigliano: Mechanized Metatheory Model-Checking, SE Pietro S. Oliveto, Jun He and Xin Yao: Evolutionary Algorithms and the Vertex Cover Problem, room 325
15:30-16:00 Invited lecture: Cristiano Calcagno (Imperial College): Can Logic Tame Systems Programs?, GW Nick Benton, Andrew Kennedy, Lennart Beringer and Martin Hofmann: Relational Semantics for Effect-Based Program Transformations with Dynamic Allocation, SE Benjamin Doerr, Edda Happ and Christian Klein: Crossover is Provably Useful in Evolutionary Computation, room 325
16:00-16:30 Invited lecture: Martín Escardó (Birmingham): Infinite sets that admit exhaustive search I, GW Makoto Hamana: Higher-Order Semantic Labelling for Inductive Datatype Systems, SE Discussion, room 325
16:30-17:00 coffee break
Session 13: Topology and Computable Mathematics, GE Contributed talks: Set Theory, GW Contributed talks: Proof Theory, SW Contributed talks: Computable Model Theory, room 222 Contributed talks: Modal/Monadic Logic, room 223 Alberto de la Encina, Luis Llana, Fernando Rubio and Mercedes Hidalgo-Herrero: Debugging Parallel Functional Languages, SE Room for discussion and cooperation, room 325
17:00-17:20 Martín Escardó: Infinite sets that admit exhaustive search II, GE Natasha Dobrinen: On the Consistency Strength of the Tree Property at the Double Successor of a Measurable Cardinal, GW Joost Joosten: Interpretability in PRA, SW Alexander Gavryushkin: Computable Models Spectra of Ehrenfeucht Theories, room 222 Tomasz Skura: Finite Reduction Trees in Modal Logic, room 223
17:20-17:30 Andrew Brooke-Taylor: Definable Well-ordering, the GCH, and Large Cardinals, GW Ryan Young: Asymmetric Systems of Natural Deduction, SW Andrey Frolov: Δ0n-categorical linear orderings, room 222 Mikhail Sheremet: A Modal Logic of Metric Spaces, room 223
17:30-17:40 Jean Goubault-Larrecq: On Noetherian Spaces, GE Bernd Brassel and Sergio Antoy: Computing with Subspaces, SE
17:40-18:00 Franqui Cárdenas: A Forcing Extension of a (ω2,1) Simplified Morasses With No (ω2,1) Simplified Morasses With Linear Limits Using an Unfoldable Cardinal, GW Elliott Spoors: Provably Recursive Functions in Extensions of a Predicative Arithmetic, SW Alexandra Revenko: Automatic Linear Orders, room 222 Zofia Kostrzycka: On Formulas in One Variable and Logics Determined by Wheel Frames in NEXT(KTB), room 223
18:00-18:30 Abbas Edalat: A Computable Approach to Measure and Integration Theory, GE
18:30-21:00 ASL reception in Botanical Garden


Sunday, July 15th
LC LC LC PPDP LCC TRSH DCM TMCNAA
09:00-09:30 Invited lecture: Matthias Baaz (Vienna): Towards a Proof Theory of Analogical Reasoning, GE Musab AlTurki and José Meseguer: Real-Time Rewriting Semantics of Orc, SE Invited lecture: Martin Grohe (Humboldt- Universität, Berlin): Algorithmic meta-theorems, SW Tutorial: Anne Auger (INRIA Futurs, Paris): Continuous Randomized Search Heuristics: Theory is Alive and Well, room 325 Invited lecture: Samson Abramsky (Oxford University): Copy-cat Strategies and Information Flow in Physics, Geometry, Logic and Computation, room 222
09:30-10:00 Brad Lushman and Gordon V. Cormack: A Larger Decidable Semiunification Problem, SE
10:00-10:30 coffee break
10:30-11:00 Invited lecture: Paul Larson (Miami): Large Cardinals and Forcing-Absoluteness, GE Invited lecture: Josh Berdine (Microsoft Research): Local Reasoning About Storable Locks, SE Invited lecture: Matt Valeriote (McMaster University, Hamilton): An algebraic approach to the constraint satisfaction problem, SW Mohamed Jebalia and Anne Auger: Linear Convergence and Premature Convergence of Evolution Strategies in Noisy Spherical Environment, room 325 Vincent Danos and Ellie D'Hondt: Quantum knowledge for cryptographic reasoning, room 222 Invited lecture: Masahito Hasegawa (Kyoto University): On Traced Monoidal Closed Categories, room 223
11:00-11:15 Anne Auger, Sylvain Gelly, Sylvie Ruette and Olivier Teytaud: On Invariances in Evolutionary Algorithms, room 325 Simon Perdrix: A Hierarchy of Quantum Semantics, room 222
11:15-11:30 Invited lecture: Paulo Oliva (University of London): Hoare Logic in the Abstract, room 223
11:30-12:00 Invited lecture: Tony Martin (UCLA): Sets and the Concept of Set, GE Michael Hanus: Putting Declarative Programming into the Web: Translating Curry to JavaScript, SE Evgenia Ternovska, David Mitchell and Brendan Guild: Meta-finite model expansion, SW Anne Auger and Olivier Teytaud: Continuous Lunches are Free!, room 325 Elham Kashefi: Lost in Translation, room 222
12:00-12:05 Isabelle Gnaedig: Induction for Positive Almost Sure Termination, SE Discussion, room 325 Pablo Arrighi and Renan Fargetton: Intrisically universal one-dimensional quantum cellular automata, room 222
12:05-12:30 Ross Duncan: Quantum Entanglement and Freely Constructed Compact Categories, room 223
12:30-14:00 lunch
Special session: Philosophical and Applied Logic at the JPL, GE Special session: Model Theory, GW Paolo Tacchella, Maria Chiara Meo and Maurizio Gabbrielli: Unfolding in CHR, SE Invited lecture: Mikołaj Bojańczyk (Warsaw University): Expressive power of tree logics, SW Room for discussion and cooperation, room 325 Invited lecture: Ian Mackie: Linearity and optimality, room 222 Invited lecture: Prakash Panangaden (McGill University, Montreal): Traces, Kahn Networks and the Geometry of Interaction, room 223
14:00-14:30 Aldo Antonelli (Irvine): From Philosophical Logic to Computer Science — and back, GE Amador Martin-Pizarro (HU Berlin): Some thoughts on bad objects, GW
14:30-14:45 Chongbing Liu and Enrico Pontelli: Nonmonotonic Inductive Logic Programming by Instance Patterns, SE
14:45-15:00 Vera Djordjevic (Uppsala): Independence in structures and finite satisfiability, GW Invited lecture: Gheorghe Stefanescu (University of Bucharest): Streams, Network Algebras, and Interactive Systems, room 223
15:00-15:30 Francisco Lopez-Fraguas, Juan Rodriguez-Hortala and Jaime Sanchez-Hernandez: A simple rewrite notion for call-time choice semantics, SE Tobias Ganzow and Sasha Rubin: Order-invariant MSO is stronger than counting MSO, SW Ross Duncan: Verifying the Measurement Calculus by Rewriting, room 222
15:30-16:00 coffee break
16:00-16:30 Tutorial: Bakh Khoussainov (Auckland): Automatic Structures (1), GE Invited lecture: Witold Charatonik (University of Wrocław): Regular Directional Types for Logic Programs, SE Invited lecture: Jan Johannsen (Ludwig- Maximilians- Universität München): Resolution proof systems and clause learning SAT algorithms, room 141 Shinya Sato and Ian Mackie: A calculus for interaction nets based on the linear chemical abstract machine, room 222 Invited lecture: Gordon Plotkin (University of Edinburgh): TBA, room 223
16:30-16:45 Giorgio Bacci and Marino Miculan: Undecidability of Model checking in Brane Logic, room 222
16:45-17:00 Peter Hines (York University): The Trace and the Inverse: Iterative Traces in Inverse Categories, room 223
Contributed talks: Intuitionistic Logic, GE Contributed talks: Set Theory, GW Contributed talks: Randomness / Complexity Theory, SW Katia Hristova, K. Tuncay Tekle and Yanhong A. Liu: Efficient Trust Management Policy Analysis from Rules, SE Jean-Yves Marion and Romain Pechoux: Resource control of object-oriented programs, room 141 Anne Crumiere and Paul Ruet: Spatial differentiation and positive circuits in a discrete framework, room 222
17:00-17:10 Konrad Zdanowski: On the Second Order Intuitionistic Propositional Logic Without Universal Quantifier, GE Benjamin Claverie: Changing u2 by Stationary Set Preserving Forcing, GW Peter Cholak: Strong Jump-traceability I: the Computably Enumerable Case, SW
17:10-17:15
17:15-17:20 Invited lecture: Dusko Pavlovic (Kestrel Institute, Palo Alto and Oxford University): Traces of intruders II: From Copy-cat, through Man-in-the-Middle, to Automated Turing Test, room 223
17:20-17:30 Tomasz Połacik: Back and Forth Between Kripke Models, GE Ioanna Dimitriou: Equiconsistency of Choiceless Higher Chang Conjectures with One Erdős Cardinal, GW Steffen Lempp: Separating notions of randomness, SW
17:30-17:40 Roberto Amadio and Frederic Dabrowski: Feasible reactivity in a synchronous π-calculus, SE Davide Ancona, Sonia Fagorzi and Elena Zucca: A Parametric Calculus for Mobile Open Code, room 222
17:40-18:00 Dariusz Surowik: A New Axiomatization of IKt System, GE Hiroaki Minami: Around Splitting And Reaping Number For Partitions of ω, GW Leszek Kołodziejczyk: The Polynomial and Linear Time Hierarchies in Weak Arithmetic, SW
18:00-18:20 Jack Stecher: Intuitionism and Repeated Games, GE Barbara Majcher-Ivanov: Nice Topologies of Polish G-spaces and Admissible Sets, GW James Worthington: Automatic Proof Generation in Kleene Algebra with Tests, SW Bernadette Charron-Bost and Andre Schiper: Computing in Distributed Systems in the Presence of Benign Failures, room 222 Invited lecture: Martin Hyland (University of Cambridge): TBA, room 223
18:20-18:30 Marina Stukacheva: On Models of Paraconsistent Analogue of the Scott Logic, GE Teruyuki Yorioka: Fragments of Martin's Axiom Related to the Rectangle Refining Property, GW Satoru Kuroda: Bounded Arithmetic and LOGCFL, SW
18:30-18:40 Ship excursion
18:40-18:45 Michael O'Connor: The Order-Theoretic Structure of Free Heyting Algebras, GE Luca Motto Ros: General Reducibilities for Sets of Reals, GW Sam Sanders: What If Computers Could Count to Infinity?, SW
18:45-19:00
19:00-20:30
20:30-23:00 ASL Council meeting, GE
23:00-24:00


Monday, July 16th
LC LC LC LC
09:00-10:00 Tutorial: Steve Jackson (North Texas): Cardinal Arithmetic in L(R) (1), GE
10:00-10:30 coffee break
10:30-11:30 Invited lecture: Albert Atserias (Barcelona): Structured Finite Model Theory, GE
11:30-12:30 Invited lecture: Piotr Kowalski (Wrocław): Definability in Differential Fields, GE
12:30-14:00 time for lunch
14:00-15:00 Invited lecture: Vasco Brattka (Cape Town): Computable Analysis and Effective Descriptive Set Theory, GE
15:00-16:00 Tutorial: Bakh Khoussainov (Auckland): Automatic Structures (2), GE
16:00-16:30 coffee break
Special session: Philosophical and Applied Logic at the JPL, GE Special session: Model Theory, GW
16:30-17:15 Greg Restall (Melbourne): Proof Theory and Meaning: Three Case Studies, GE Marcus Tressl (Regensburg): Super real closed rings, GW
17:15-18:00 Albert Visser (Utrecht): Interpretations in Philosophical Logic, GE Ziv Shami (Tel Aviv): Countable Imaginary Simple Unidimensional Theories, GW
Contributed talks: Philosophical Logic, GW Contributed talks: Model Theory, SW Contributed talks: Logic in Computer Science, SE
18:00-18:20 Michal Peliš: Epistemic Logic and Questions, GW Martin Koerwien: Complexity of Isomorphism for Countable Models of Omega-stable Theories, SW Maria Bulińska: Computational Complexity of NL1 with Assumptions, SE
18:20-18:40 Luis Adrian Urtubey: An Analysis of Some Basic Philosophical Thesis about Non-deductive Inference in the Framework of CHC Models, GW Alexey Muranov: Interpretability of the Arithmetic in Certain Finitely Presented Groups, SW Aleksandra Kiślak-Malinowska: Pregroups: Their Logic and Applications for Natural Languages, SE
18:40-19:00 Kerkko Luosto: Unary Quantifiers and Built-in Successor, SW Heinrich Wansing: Harmonious Many-valued Propositional Logics and the Logic of Computer Networks, SE
19:00-20:00
20:00-21:00 Invited lecture: Andrzej Grzegorczyk (Warsaw): Philosophical Content of Formal Achievements, GE


Tuesday, July 17th
LC LC
09:00-10:00 Tutorial: Steve Jackson (North Texas): Cardinal Arithmetic in L(R) (2), GE
10:00-10:30 coffee break
10:30-11:30 Invited lecture: Fernando Ferreira (Lisbon): On a New Functional Interpretation, GE
11:30-12:30 Tutorial: Kobi Peterzil (Haifa): The Infinitesimal Subgroup of a Definably Compact Group (1), GE
12:30-13:00 time for lunch
13:00-14:00 Guided sightseeing
14:00-15:30 Excursion time for lunch
15:30-18:00 Guided sightseeing
18:00-18:30
18:30- Boat party


Wednesday, July 18th
LC LC LC LC LC
09:00-10:00 Tutorial: Steve Jackson (North Texas): Cardinal Arithmetic in L(R) (3), GE
10:00-10:30 coffee break
10:30-11:30 Invited lecture: Zoé Chatzidakis (Paris 7): Model theory of difference fields, and some applications, GE
11:30-12:30 Tutorial: Kobi Peterzil (Haifa): The Infinitesimal Subgroup of a Definably Compact Group (2), GE
12:30-14:00 time for lunch
Special session: Proof Complexity and Nonclassical Logics, GE Special session: Logic and Analysis, GW Special session: Set Theory, SE
14:00-14:30 Alasdair Urquhart (Toronto): Complexity Problems for Substructural Logics, GE Julien Melleray (Urbana): Geometry of the Urysohn Space: A Model-theoretic Approach, GW Matteo Viale (Vienna): The Constructible Universe for the Anti-Foundation Axiom System ZFA, SE
14:30-14:45 Emil Jeřábek (Prague): Proof Systems for Modal Logics, GE Lionel Nguyen Van Thé (Calgary), joint with Jordi López Abad (Université Paris 7) and Norbert Sauer (University of Calgary): The Urysohn sphere is oscillation stable, SE
14:45-15:00 Philipp Gerhardy (Pittsburgh/Oslo): Local stability of ergodic averages, GW
15:00-15:30 George Metcalfe (Vanderbilt): Substructural Fuzzy Logics, GE Gunter Fuchs (Münster): Maximality Principles for Closed Forcings, SE
15:30-16:00 coffee break
16:00-17:00 Tutorial: Bakh Khoussainov (Auckland): Automatic Structures (3), GE
Contributed talks: Fuzzy Logic, GE Contributed talks: Set Theory, GW Contributed talks: Model Theory, SE Contributed talks: Computability, SW Contributed talks: Other Logics, room 222
17:00-17:20 Petr Hájek: Complexity of Fuzzy Predicate Logics with Witnessed Semantics, GE Philipp Schlicht: Thin Projective Equivalence Relations and Inner Models, GW Nicolas Guzy: Towards a Notion of p-adic Closure for a Ring, SE Thomas Kent: Non-splitting Enumeration Degrees, SW Achim Blumensath: Simple Monadic Theories, room 222
17:20-17:40 Ondrej Majer: Probabilistic representation of fuzzy logics, GE Heike Mildenberger: There May Be Infinitely Many Coherence Classes under u<d, GW Immanuel Halupczok: Motivic measure for pseudo-finite like fields, SE Serikzhan Badaev: Completion of Numberings, SW Satoshi Matsuoka: MLL Proof Nets as Error-correcting Codes, room 222
17:40-18:00 Libor Běhounek: Multiplicative Quantifiers in Fuzzy and Substructural Logics, GE Denis Saveliev: On Cardinals in Set Theory Without Choice and Regularity, GW Assaf Hasson: On Uncountably Categorical Approximations and Gromov-Hausdorff Limits, SE James Hunter: Higher-Order Reverse Topology, SW Gemma Robles: Relevance Logics and Intuitionistic Negation, room 222
18:00-18:20 Petr Cintula: Structural Completeness For Fuzzy Logics, GE Robert Owen: Outer Models, Class Forcing, and Weakly Self-defining Classes, GW Ikuo Yoneda: CM-triviality and Geometric Elimination of Imaginaries, SE Ilnur Batyrshin: The Algebraic Structure of Quasi-degrees, SW Horacio Faas: Logical Inferences and Visualization, room 222
18:20-18:40 Urszula Wybraniec-Skardowska: On Vague Sets and Vague Logic, GE Robert Lubarsky: Signed-bit Representations of Real Numbers and the Constructive Stone-Yosida Theorem, GW Koichiro Ikeda: A Remark on a Characterization of Non-forking in Generic Structures, SE Alexey Stukachev: On Ershov Semilattices of Degrees of Σ-definability of Structures, SW Cyrus Nourani: Positive Realizability Morphisms and Tarski Models, room 222
18:40-19:30
19:30-21:15 ASL banquet in Piwnica Świdnicka
21:15-22:00 Possible second ASL Council meeting, GE
22:00-23:00


Thursday, July 19th
LC LC
09:00-10:00 Invited lecture: Gabriel Debs (Paris 6): Coding compact spaces of Borel functions, GE
10:00-11:00 Tutorial: Kobi Peterzil (Haifa): The Infinitesimal Subgroup of a Definably Compact Group (3), GE
11:00-11:30 coffee break
Special session: Logic and Analysis, GE Special session: Set theory, GW
11:30-12:00 Peter Hertling (München): Computability and Non-Computability Results for the Topological Entropy of Shift Spaces, GE Victoria Gitman (City University of New York): Scott's Problem For Proper Scott Sets, GW
12:00-12:15 Márton Elekes (Hungarian Academy of Sciences): Partitioning κ-fold Covers into κ Many Subcovers, GW
12:15-12:30 Andreas Weiermann (Ghent): Analytic Combinatorics of the Transfinite, GE
12:30-13:00 Asger Törnquist (Toronto): Classifying Measure Preserving Actions Up to Conjugacy and Orbit Equivalence, GW