AgileByExample 2016

AgileByExample 2016

Programme

Programme

Monday, July 10


9:00-10:00 : Invited talk

Ronitt Rubinfeld: (TBA)


10:00-10:25: Coffee break


10:25-12:30

TRACK A.1


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:15
T. Eden, D. Ron and C. Seshadhri:
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection


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

TRACK A.2


10:25
S. Albers and D. Kraft:
On the Value of Penalties in Time-Inconsistent Planning


10:50
J. Chen, B. Li and Y. Li:
Efficient Approximations for the Online Dispersion Problem


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

TRACK B


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

TRACK C


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


14:00-15:40

TRACK A.1


14:00
G. Kindler and R. O’Donnell:
Quantum automata cannot detect biased coins, even in the limit


14:25
M. Backens:
A new Holant dichotomy inspired by quantum computation


14:50
R. Cleve and C. Wang:
Efficient Quantum Algorithms for Simulating Lindblad Evolution


15:15
C. Dohotaru and P. Høyer:
Controlled quantum amplification

TRACK A.2


14:00
R. Jayaram and B. Saha:
Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultra-linear grammars are where Parsing Becomes Hard!


14:25
R. Krauthgamer and O. Trabelsi:
Conditional Lower Bounds for All-Pairs Max-Flow


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

TRACK B


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:50
Best Track B Student Paper:
F. Reiter:
Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment


15:15
J. Chalopin and V. Chepoi:
A Counterexample to Thiagarajan’s Conjecture on Regular Event Structures

TRACK C


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:15
M. Hoefer and B. Kodric
Combinatorial Secretary Problems with Ordinal Information


15:40-16:00: Coffee break


16:00-17:40

TRACK A.1


16:00
M. Bury and C. Schwiegelshohn:
On Finding the Jaccard Center


16:25
S. Almagor, J. Ouaknine and J. Worrell:
The Polytope-Collision Problem


16:50
O. Gold and M. Sharir:
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier


17:15
G. Blelloch, Y. Gu and Y. Sun:
Efficient Construction of Probabilistic Tree Embeddings

TRACK A.2


16:00
A. Galanis, L. A. Goldberg and K. Yang:
Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems


16:25
A. Galanis, L. A. Goldberg and D. Stefankovic:
Inapproximability of the independent set polynomial below the Shearer threshold


16:50
J. Lin and H. Wang:
The Complexity of Holant Problems over Boolean Domain with Non-negative Weights


17:15
A. Galicki:
Polynomial-time Rademacher theorem, porosity and randomness


Tuesday, July 11


9:00-10:00 : Invited talk

Monika Henzinger: (TBA)


10:00-10:25: Coffee break


10:25-12:30

TRACK A.1


10:25
A. Antoniadis, R. Hoeksma, J. Meissner, J. Verschae and A. Wiese:
A QPTAS for the general scheduling problem with identical release dates


10:50
A. Linhares and C. Swamy:
Improved Algorithms for MST and Metric-TSP Interdiction


11:15
M. Kohler and H. Räcke:
Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces


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

TRACK A.2


10:25
S. Agrawal and I. P. Singh:
Reusable Garbled Deterministic Finite Automata from Learning With Errors


10:50
R. Cohen, S. Coretti, J. Garay and V. Zikas:
Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols


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:
Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck

TRACK B


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

TRACK C


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:15
O. Michail, G. Skretas and P. Spirakis:
On the Transformation Capability of Feasible Mechanisms for Programmable Matter


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-15:40

TRACK A.1


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


15:15
A. Bernstein:
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs

TRACK A.2


14:00
G. Bodwin:
Testing Core Membership in Public Goods Economies


14:25
T. Böhnlein, S. Kratsch and O. Schaudt:
Revenue maximization in Stackelberg Pricing Games: Beyond the combinatorial setting


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

TRACK B


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


14:50
G. Dowek:
Models and termination of proof reduction in the lambda-Pi-calculus modulo theory


15:15
A. Atserias and J. Ochremiak:
Proof Complexity Meets Algebra

TRACK C


14:00
B. Doerr and A. Kostrygin:
Randomized Rumor Spreading Revisited


14:25
L. Cai and T. Sauerwald:
Randomized Load Balancing on Networks with Stochastic Inputs


14:50
T. Mai, I. Panageas and V. Vazirani:
Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion


15:15
A. Belleville, D. Doty and D. Soloveichik:
Hardness of computing and approximating predicates and functions with leaderless population protocols


15:40-16:00: Coffee break


16:00-17:40: 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


Wednesday, July 12


9:00-10:00: Invited talk

Mikkel Thorup: (TBA)


10:00-10:25: Coffee break


10:25-12:30

TRACK A.1


10:25
B. Ghazi and M. Sudan:
The Power of Shared Randomness in Uncertain Communication


10:50
B. Rossman and S. Srinivasan:
Separation of AC^0[⊕] Formulas and Circuits


11:15
C. Lin and S. Zhang:
Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers


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

TRACK A.2


10:25
I. Bezakova, R. Curticapean, H. Dell and F. Fomin:
Finding Detours is Fixed-parameter Tractable


10:50
S. Ahmadian and Z. Friggstad:
Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs


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

TRACK B


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


10:50
R. Berthon, M. Randour and J.-F. Raskin:
Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes


11:15
A. Finkel and E. Lozes:
Synchronizability of Communicating Finite State Machines is not Decidable


11:40
N. Basset, G. Geeraerts, J.-F. Raskin and O. Sankur:
Admissibility in Concurrent Games


12:05
K. Bringmann, T. D. Hansen and S. Krinninger:
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs


12:30-14:00: Lunch break


14:00-15:40

TRACK A.1


14:00
E. Price, Z. Song and D. P. Woodruff:
Fast Regression with an $\ell_\infty$ Guarantee


14:25
Y. Li and D. P. Woodruff:
Embeddings of Schatten Norms with Applications to Data Streams


14:50
V. Nakos:
On Fast Decoding of High-Dimensional Signals from One-Bit Measurements


15:15
J. Kärkkäinen, M. Piątkowski and S. Puglisi:
String Inference from Longest-Common-Prefix Array

TRACK A.2


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
M. B. T. Knudsen:
Additive Spanners and Distance Oracles in Quadratic Time


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


15:15
Pascal Schweitzer:
A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry

TRACK B


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


14:50
B. Boigelot, I. Mainz, V. Marsault and M. Rigo:
An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention


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-17:40: EATCS Assembly


Thursday, July 13


9:00-10:00: Invited talk

Mikołaj Bojańczyk: (TBA)


10:00-10:25: Coffee break


10:25-12:30

TRACK A.1


10:25
A. Wiese:
A (1+eps)-approximation for Unsplittable Flow on a Path in fixed-parameter running time


10:50
Y. Iwata:
Linear-time Kernelization for Feedback Vertex Set


11:15
E. J. Lee and S. Gaspers:
Exact Algorithms via Multivariate Subroutines


11:40
F. Barbero, C. Paul and M. Pilipczuk:
Exploring the complexity of layout parameters in tournaments and semi-complete digraphs


12:05
D. Lokshtanov, A. Mouawad, S. Saurabh and M. Zehavi:
Packing Cycles Faster Than Erdős-Pósa

TRACK A.2


10:25
K. Choudhary, S. Baswana and L. Roditty:
An efficient strongly connected components algorithm in the fault tolerant model


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^{\omega}\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

TRACK B


10:25
B. Rossman:
Subspace-Invariant AC^0 Formulas


10:50
D. Chistikov and C. Haase:
On the complexity of quantified integer programming


11:15
A. Jeż:
Word equations in nondeterministic linear space


11:40
V. Diekert and M. Elder:
Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups


12:05
K. Asada and N. Kobayashi:
Pumping Lemma for Higher-order Languages


12:30-14:00: Lunch break


14:00-15:40

TRACK A.1


14:00
A. Rubinstein:
Honest signaling in zero-sum games is hard… and lying is even harder!


14:25
P. Manurangsi and P. Raghavendra:
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs


14:50
P. Manurangsi:
Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis


15:15
B. Weitz and P. Raghavendra:
On the Bit Complexity of Sum-of-Squares Proofs

TRACK A.2


14:00
A. Korman and Y. Rodeh:
The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback


14:25
S. Brandt, Y. Emek, J. Uitto and R. Wattenhofer:
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game


14:50
D. Achlioptas, F. Iliopoulos and N. Vlassis:
Stochastic Control via Entropy Compression


15:15
D. Dereniowski, A. Kosowski, P. Uznański and M. Zou:
Approximation Strategies for Generalized Binary Search in Weighted Trees


15:40-16:00: Coffee break


16:00-18:05

TRACK A.1


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

TRACK A.2


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


16:50
M. Raskin:
A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model


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


Friday, July 14


Satellite Workshops (schedule to appear soon)