AgileByExample 2016

AgileByExample 2016

Agenda

July

10 11 12 13 14 CONFERENCE

Agenda / July 10

Track A.1
Track A.2
Track B
Track C

INVITED TALK

8:55

 

ICALP welcome and opening remarks

09:00

Ronitt Rubinfeld 

Local Computation Algorithms

10:00-10:25: COFFEE BREAK

10:25

R. Baleshzar, D. Chakrabarty, R. K. S. Pallavoor, S. Raskhodnikova and C. Seshadhri: 

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

10:50

G. Even, R. Levi, M. Medina and A. Rosén: 

Sublinear Random Access Generators for Preferential Attachment Graphs

11:40

I. Diakonikolas, D. Kane and V. Nikishkin: 

Near-optimal Closeness Testing of Discrete Histogram Distributions

12:05

O. Ben Eliezer, S. Korman and D. Reichman: 

Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays

11:15

V. Nagarajan and X. Shen: 

Online Covering with Sum of lq-Norm Objectives

11:40

M. Bienkowski, J. Byrka and M. Mucha: 

Dynamic beats fixed: On phase-based algorithms for file migration

12:05

C. Coester, E. Koutsoupias and P. Lazos: 

The Infinite Server Problem

10:25

A. Amarilli, P. Bourhis, L. Jachiet and S. Mengel: 

A Circuit-Based Approach to Efficient Enumeration

10:50

R. Alur, K. Mamouras and C. Stanford: 

Automata-based Stream Processing

11:15

L. Dartois, P. Fournier, I. Jecker and N. Lhote: 

On Reversible Transducers

11:40

M. Bojańczyk, L. Daviaud, B. Guillon and V. Penelle: 

Which classes of origin graphs are generated by transducers?

12:05

M. Cadilhac, C. Paperman and O. Carton: 

Continuity and Rational Functions

10:25

V. Bilò, I. Caragiannis, A. Fanelli, M. Flammini and G. Monaco: 

Simple greedy algorithms for fundamental multidimensional graph problems

10:50

B. Gorain and A. Pelc: 

Deterministic Graph Exploration with Advice

11:15

M. Gupta and S. Khan: 

Multiple Source Dual Fault Tolerant BFS Trees

11:40

M. Abrahamsen, S. Alstrup, J. Holm, M. B. T. Knudsen and M. Stöckel: 

Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

12:05

BEST TRACK C PAPER: E. I. Ásgeirsson, M. M. Halldorsson and T. Tonoyan: 

Universal Framework for Wireless Scheduling Problems

12:30-14:00: LUNCH BREAK

15:15

C. Dohotaru and P. Høyer: 

Controlled quantum amplification

14:50

M. Künnemann, R. Paturi and S. Schneider: 

On the Fine-grained Complexity of One-Dimensional Dynamic Programming

15:15

M. Cygan, M. Mucha, K. Węgrzycki and M. Włodarczyk: 

On problems equivalent to (min,+)-convolution

14:00

S. Datta, A. Mukherjee, T. Schwentick, N. Vortmeier and T. Zeume: 

A Strategy for Dynamic Programs: Start over and Muddle through

14:25

N. Bacquey, E. Grandjean and F. Olive: 

Definability by Horn formulas and linear time on cellular automata

14:00

L. Boczkowski, I. Kerenidis and F. Magniez: 

Streaming Communication Protocols

14:25

M. Monemizadeh, S. Muthukrishnan, P. Peng and C. Sohler: 

Testable Bounded Degree Graph Properties Are Random Order Streamable

14:50

S. Ehsani, S. Dehghani, M. Hajiaghayi and S. Seddighin: 

Stochastic k-server Problem

15:40-16:00: COFFEE BREAK
19:00: WELCOME RECEPTION – BROWARMIA

Agenda / July 11

Track A.1
Track A.2
Track B
Track C
10:00-10:25: COFFEE BREAK

10:25

A. Antoniadis, R. Hoeksma, J. Meissner, J. Verschae and A. Wiese: 

A QPTAS for the general scheduling problem with identical release dates

11:40

S. Chen, D. Di Castro, Z. Karnin, L. Lewin-Eytan, S. Naor and R. Schwartz: 

Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification

12:05

M. Adamczyk, F. Grandoni, S. Leonardi and M. Włodarczyk: 

When the Optimum is also Blind: a New Perspective on Universal Optimization

11:15

D. Apon, N. Döttling, S. Garg and P. Mukherjee: 

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

11:40

K. Pietrzak and M. Skorski: 

Non-Uniform Attacks Against Pseudoentropy

12:05

E. Ben-Sasson, A. Chiesa, A. Gabizon, M. Riabzev and N. Spooner: 

Interactive Oracle Proofs with Constant Rate and Query Complexity

10:25

G. Barthe, T. Espitau, J. Hsu, T. Sato and P.-Y. Strub: 

*-Liftings for Differential Privacy

10:50

B. Balle, P. Gourdeau and P. Panangaden: 

Bisimulation Metrics for Weighted Automata

11:15

G. Bacci, G. Bacci, K. G. Larsen and R. Mardare: 

On the Metric-based Approximate Minimization of Markov Chains

11:40

N. Fijalkow, B. Klin and P. Panangaden: 

Expressiveness of Probabilistic Modal Logics, Revisited

12:05

M. Bojanczyk, H. Gimbert and E. Kelmendi: 

Emptiness of zero automata is decidable

10:25

M. Babaioff, L. Blumrosen and N. Nisan: 

Selling Complementary Goods: Dynamics, Efficiency and Revenue

10:50

J. Choudhari, A. Dasgupta, N. Misra and Ramanujan M. S.: 

Saving Critical Nodes with Firefighters is FPT

11:40

R. Gmyr, K. Hinnenthal, C. Scheideler and C. Sohler: 

Distributed Monitoring of Network Properties: The Power of Hybrid Networks

12:30-14:00: LUNCH BREAK

14:00

J. Alman, M. Mnich and V. Vassilevska Williams: 

Dynamic Parameterized Problems and Algorithms

14:25

L. Georgiadis, T. D. Hansen, G. F. Italiano, S. Krinninger and N. Parotsidis: 

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

14:50

A. Bernstein, Y. Disser and M. Groß: 

General Bounds for Incremental Maximization

14:50

Y. Giannakopoulos, E. Koutsoupias and P. Lazos: 

Online Market Intermediation

15:15

N. Gravin, Y. Peres and B. Sivan: 

Tight Lower Bounds for Multiplicative Weights Algorithmic Families

14:00

BEST TRACK B PAPER:M. Benedikt, P. Bourhis and M. Vanden Boom: 

Characterizing Definability in Decidable Fixpoint Logics

14:25

J. C. Jung, C. Lutz, M. Martel, T. Schneider and F. Wolter: 

Conservative Extensions in Guarded and Two-Variable Fragments

15:15

A. Atserias and J. Ochremiak: 

Proof Complexity Meets Algebra

14:00

B. Doerr and A. Kostrygin: 

Randomized Rumor Spreading Revisited

15:40-16:00 COFFEE BREAK

16:00

AWARDS SESSION 

- EATCS Award: Éva Tardos
- EATCS Presburger Award: Alexandra Silva
- EATCS Appointment of Fellows
- EATCS Distinguished Dissertation Awards: Vincent Cohen-Addad, Mika Göös, Steen Vester
- ICALP Best Paper Awards
- ICALP Best Student Paper Awards

Agenda / July 12

Track A.1
Track A.2
Track B

INVITED TALK

10:00-10:25 COFFEE BREAK

10:50

B. Rossman and S. Srinivasan: 

Separation of AC^0[⊕] Formulas and Circuits

11:40

M. Göös, T.S. Jayram, T. Pitassi and T. Watson: 

Randomized Communication vs. Partition Number

12:05

A. Bogdanov and C. Williamson: 

Approximate Bounded Indistinguishability

10:25

I. Bezakova, R. Curticapean, H. Dell and F. Fomin: 

Finding Detours is Fixed-parameter Tractable

11:15

F. Fomin, P. Golovach, D. Lokshtanov and S. Saurabh: 

Covering vectors by spaces: Regular matroids

11:40

A. Giannopoulou, M. Pilipczuk, J.-F. Raymond, D. Thilikos and M. Wrochna: 

Linear kernels for edge deletion problems to immersion-closed graph classes

12:05

G. Gutin, F. Reidl and M. Wahlström: 

k-Distinct In- and Out-Branchings in Digraphs

10:25

L. Bozzelli, A. Molinari, A. Montanari, A. Peron and P. Sala: 

Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption

11:40

N. Basset, G. Geeraerts, J.-F. Raskin and O. Sankur: 

Admissibility in Concurrent Games

12:30-14:00 LUNCH BREAK

14:00

E. Price, Z. Song and D. P. Woodruff: 

Fast Regression with an l_∞ Guarantee

15:15

J. Kärkkäinen, M. Piątkowski and S. Puglisi: 

String Inference from Longest-Common-Prefix Array

14:00

K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O-J. Kwon, M. Pilipczuk, R. Rabinovich and S. Siebertz: 

Neighborhood complexity and kernelization for nowhere dense classes of graphs

14:25

R. Krauthgamer and O. Trabelsi: 

Conditional Lower Bounds for All-Pairs Max-Flow

14:50

F. Fomin, D. Lokshtanov, F. Panolan, S. Saurabh and M. Zehavi: 

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

14:00

A. Pouly and O. Bournez: 

A Universal Ordinary Differential Equation

14:25

L. Clemente, W. Czerwiński, S. Lasota and C. Paperman: 

Regular Separability of Parikh Automata

15:15

D. Figueira, R. Lazic, J. Leroux, F. Mazowiecki and G. Sutre: 

Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One

15:40-16:00 COFFEE BREAK

16:00

 

EATCS ASSEMBLY

19:30: DINNER – NEW UNIVERSITY LIBRARY

Agenda / July 13

Track A.1
Track A.2
Track B

INVITED TALK

9:00

Mikołaj Bojańczyk: 

Orbit-Finite Sets and their Algorithms

10:00-10:25: COFFEE BREAK

11:15

E. J. Lee and S. Gaspers: 

Exact Algorithms via Multivariate Subroutines

12:05

D. Lokshtanov, A. Mouawad, S. Saurabh and M. Zehavi: 

Packing Cycles Faster Than Erdős-Pósa

10:50

G. Bodwin, F. Grandoni, M. Parter and V. Vassilevska Williams: 

Preserving Distances in Very Faulty Graphs

11:15

L. Georgiadis, D. Graf, G. F. Italiano, N. Parotsidis and P. Uznański: 

All-Pairs 2-Reachability in O(n^ω(log n)) Time

11:40

L. Schlipf and J. M. Schmidt: 

Edge-Orders

12:05

L. Mancinska, D. Roberson, R. Samal, S. Severini and A. Varvitsiotis: 

Relaxations of Graph Isomorphisms

10:25

B. Rossman: 

Subspace-Invariant AC^0 Formulas

10:50

D. Chistikov and C. Haase: 

On the complexity of quantified integer programming

12:05

K. Asada and N. Kobayashi: 

Pumping Lemma for Higher-order Languages

12:30-14:00: LUNCH BREAK
15:40-16:00: COFFEE BREAK

16:00

P. Pudlák, D. Scheder and N. Talebanfard: 

Tighter Hard Instances for PPSZ

16:25

V. Guruswami, C. Xing and C. Yuan: 

Subspace Designs based on Algebraic Function Fields

16:50

S. Goldwasser and O. Grossman: 

Bipartite Perfect Matching in Pseudo-Deterministic NC

16:00

J. Matuschke, T. Mccormick and G. Oriolo: 

Rerouting flows when links fail

16:25

É. Bonnet, S. Gaspers, A. Lambilliotte, S. Rümmele and A. Saffidine: 

The Parameterized Complexity of Positional Games

17:15

BEST TRACK A PAPER:A. Björklund, P. Kaski and I. Koutis: 

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

17:40

BEST TRACK A STUDENT PAPER:E. Lee: 

Improved Hardness for Cut, Interdiction, and Firefighter Problems

Agenda / July 14

ASSG
AVeRTS
SP

9:30

O-joung Kwon 

On low rank-width colorings

10:00

Stephan Kreutzer 

New perspectives for first-order model-checking

9:30

Dominik Wojtczak 

Optimal Control for Multi-Mode Systems with Discrete Costs

10:15

Emmanuel Filiot 

A decidable logic for finite word transductions

9:30

Marc Zeitoun 

Separation and concatenation hierarchies (part I)

10:15

Thomas Place 

Separation and concatenation hierarchies (part II)

11:00 - 11:30 COFFEE BREAK

11:30

Felix Reidl 

Practise what you preach: sparsity in the real world

12:30

Sebastian Siebertz 

Applications of sparsity to distributed computing

11:30

Anca Muscholl 

A tour of recent results on word transducers

12:15

Piotr Hofman 

State equations for Petri Nets with data

11:30

Wojciech Czerwiński 

Separability of Reachability Sets of Vector Addition Systems

12:15

Sylvain Schmitz 

An Order-Theoretic Framework for PTL Separability

13:00 - 14:30 LUNCH BREAK

14:30

Daniel Král' 

Results and open problems on sparse graph convergence

15:30

Szymon Toruńczyk 

From infinite to finite

14:30

Nicolas Basset 

Uniform Sampling for Timed Automata with Application to Language Inclusion Measurement

15:15

Lorenzo Clemente 

Modelling time and recursion

14:30

Christof Löding 

Regular Separability for Well-Matched Complements of Visibly Pushdown Languages

15:15

Georg Zetzsche 

Parameterized WQOs, downward closures, and separability problems

16:00 - 16:30 COFFEE BREAK

16:30

 

Open problem session

16:30

Thomas Colcombet 

Separation of tropical automata

17:15

 

Open problem session