AgileByExample 2016

ICALP welcome and opening remarks

Ronitt Rubinfeld 

Local Computation Algorithms

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

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

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

Sublinear Random Access Generators for Preferential Attachment Graphs

T. Eden, D. Ron and C. Seshadhri: 

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection

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

Near-optimal Closeness Testing of Discrete Histogram Distributions

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

Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays

S. Albers and D. Kraft: 

On the Value of Penalties in Time-Inconsistent Planning

J. Chen, B. Li and Y. Li: 

Efficient Approximations for the Online Dispersion Problem

V. Nagarajan and X. Shen: 

Online Covering with Sum of lq-Norm Objectives

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

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

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

The Infinite Server Problem

G. Kindler and R. O’Donnell: 

Quantum automata cannot detect biased coins, even in the limit

M. Backens: 

A new Holant dichotomy inspired by quantum computation

R. Cleve and C. Wang: 

Efficient Quantum Algorithms for Simulating Lindblad Evolution

C. Dohotaru and P. Høyer: 

Controlled quantum amplification

R. Jayaram and B. Saha: 

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultra-linear grammars are where Parsing Becomes Hard!

M. B. T. Knudsen 

Additive Spanners and Distance Oracles in Quadratic Time

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

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

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

On problems equivalent to (min,+)-convolution

M. Bury and C. Schwiegelshohn: 

On Finding the Jaccard Center

S. Almagor, J. Ouaknine and J. Worrell: 

The Polytope-Collision Problem

O. Gold and M. Sharir: 

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

G. Blelloch, Y. Gu and Y. Sun: 

Efficient Construction of Probabilistic Tree Embeddings

A. Galanis, L. A. Goldberg and K. Yang: 

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems

A. Galanis, L. A. Goldberg and D. Stefankovic: 

Inapproximability of the independent set polynomial below the Shearer threshold

J. Lin and H. Wang: 

The Complexity of Holant Problems over Boolean Domain with Non-negative Weights

A. Galicki: 

Polynomial-time Rademacher theorem, porosity and randomness

Monika Henzinger: 

Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification

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

A QPTAS for the general scheduling problem with identical release dates

A. Linhares and C. Swamy: 

Improved Algorithms for MST and Metric-TSP Interdiction

M. Kohler and H. Räcke: 

Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces

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

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

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

S. Agrawal and I. P. Singh: 

Reusable Garbled Deterministic Finite Automata from Learning With Errors

R. Cohen, S. Coretti, J. Garay and V. Zikas: 

Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols

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

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

K. Pietrzak and M. Skorski: 

Non-Uniform Attacks Against Pseudoentropy

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

Interactive Oracle Proofs with Constant Rate and Query Complexity

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

Dynamic Parameterized Problems and Algorithms

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

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

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

General Bounds for Incremental Maximization

A. Bernstein: 

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs

G. Bodwin: 

Testing Core Membership in Public Goods Economies

T. Böhnlein, S. Kratsch and O. Schaudt: 

Revenue maximization in Stackelberg Pricing Games: Beyond the combinatorial setting

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

Online Market Intermediation

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

Tight Lower Bounds for Multiplicative Weights Algorithmic Families

AWARDS SESSION 

Mikkel Thorup: 

Fast and Powerful Hashing Using Tabulation

B. Ghazi and M. Sudan: 

The Power of Shared Randomness in Uncertain Communication

B. Rossman and S. Srinivasan: 

Separation of AC^0[⊕] Formulas and Circuits

C. Lin and S. Zhang: 

Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers

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

Randomized Communication vs. Partition Number

A. Bogdanov and C. Williamson: 

Approximate Bounded Indistinguishability

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

Finding Detours is Fixed-parameter Tractable

S. Ahmadian and Z. Friggstad: 

Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs

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

Covering vectors by spaces: Regular matroids

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

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

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

k-Distinct In- and Out-Branchings in Digraphs

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

Fast Regression with an l_∞ Guarantee

Y. Li and D. P. Woodruff: 

Embeddings of Schatten Norms with Applications to Data Streams

V. Nakos: 

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements

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

String Inference from Longest-Common-Prefix Array

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

R. Krauthgamer and O. Trabelsi: 

Conditional Lower Bounds for All-Pairs Max-Flow

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

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

Pascal Schweitzer: 

A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry

EATCS ASSEMBLY

Mikołaj Bojańczyk: 

Orbit-Finite Sets and their Algorithms

A. Wiese: 

A (1+eps)-approximation for Unsplittable Flow on a Path in fixed-parameter running time

Y. Iwata: 

Linear-time Kernelization for Feedback Vertex Set

E. J. Lee and S. Gaspers: 

Exact Algorithms via Multivariate Subroutines

F. Barbero, C. Paul and M. Pilipczuk: 

Exploring the complexity of layout parameters in tournaments and semi-complete digraphs

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

Packing Cycles Faster Than Erdős-Pósa

K. Choudhary, S. Baswana and L. Roditty: 

An efficient strongly connected components algorithm in the fault tolerant model

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

Preserving Distances in Very Faulty Graphs

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

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

L. Schlipf and J. M. Schmidt: 

Edge-Orders

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

Relaxations of Graph Isomorphisms

A. Rubinstein: 

Honest signaling in zero-sum games is hard... and lying is even harder!

P. Manurangsi and P. Raghavendra: 

A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

P. Manurangsi: 

Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis

B. Weitz and P. Raghavendra: 

On the Bit Complexity of Sum-of-Squares Proofs

A. Korman and Y. Rodeh: 

The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

S. Brandt, Y. Emek, J. Uitto and R. Wattenhofer: 

A Tight Lower Bound for the Capture Time of the Cops and Robbers Game

D. Achlioptas, F. Iliopoulos and N. Vlassis: 

Stochastic Control via Entropy Compression

D. Dereniowski, A. Kosowski, P. Uznański and M. Zou: 

Approximation Strategies for Generalized Binary Search in Weighted Trees

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

Tighter Hard Instances for PPSZ

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

Subspace Designs based on Algebraic Function Fields

S. Goldwasser and O. Grossman: 

Bipartite Perfect Matching in Pseudo-Deterministic NC

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

Rerouting flows when links fail

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

The Parameterized Complexity of Positional Games

M. Raskin: 

A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model

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

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

BEST TRACK A STUDENT PAPER:E. Lee: 

Improved Hardness for Cut, Interdiction, and Firefighter Problems

O-joung Kwon 

On low rank-width colorings

Stephan Kreutzer 

New perspectives for first-order model-checking

Dominik Wojtczak 

Optimal Control for Multi-Mode Systems with Discrete Costs

Emmanuel Filiot 

A decidable logic for finite word transductions

Felix Reidl 

Practise what you preach: sparsity in the real world

Sebastian Siebertz 

Applications of sparsity to distributed computing

Anca Muscholl 

A tour of recent results on word transducers

Piotr Hofman 

State equations for Petri Nets with data

Daniel Král' 

Results and open problems on sparse graph convergence

Szymon Toruńczyk 

From infinite to finite

Nicolas Basset 

Uniform Sampling for Timed Automata with Application to Language Inclusion Measurement

Lorenzo Clemente 

Modelling time and recursion

Open problem session