AgileByExample 2016

AgileByExample 2016

Accepted papers: track A

Andreas Galanis, Leslie Ann Goldberg and Kuan Yang.
Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
Andreas Galanis, Leslie Ann Goldberg and Daniel Stefankovic.
Inapproximability of the independent set polynomial below the Shearer threshold
Andreas Wiese.
A (1+eps)-approximation for Unsplittable Flow on a Path in fixed-parameter running time
Guy Even, Reut Levi, Moti Medina and Adi Rosén.
Sublinear Random Access Generators for Preferential Attachment Graphs
Aviad Rubinstein.
Honest signaling in zero-sum games is hard… and lying is even harder!
Susanne Albers and Dennis Kraft.
On the Value of Penalties in Time-Inconsistent Planning
Guy Blelloch, Yan Gu and Yihan Sun.
Efficient Construction of Probabilistic Tree Embeddings
Pavel Pudlák, Dominik Scheder and Navid Talebanfard.
Tighter Hard Instances for PPSZ
Gregory Gutin, Felix Reidl and Magnus Wahlström.
k-Distinct In- and Out-Branchings in Digraphs
Marcin Bienkowski, Jaroslaw Byrka and Marcin Mucha.
Dynamic beats fixed: On phase-based algorithms for file migration
Pasin Manurangsi and Prasad Raghavendra.
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
Aaron Bernstein.
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
Guy Kindler and Ryan O’Donnell.
Quantum automata cannot detect biased coins, even in the limit
Benjamin Rossman and Srikanth Srinivasan.
Separation of AC^0[⊕] Formulas and Circuits
Marc Bury and Chris Schwiegelshohn.
On Finding the Jaccard Center
Archontia Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios Thilikos and Marcin Wrochna.
Linear kernels for edge deletion problems to immersion-closed graph classes
Shaull Almagor, Joel Ouaknine and James Worrell.
The Polytope-Collision Problem
Keerti Choudhary, Surender Baswana and Liam Roditty.
An efficient strongly connected components algorithm in the fault tolerant model
Eric Price, Zhao Song and David P. Woodruff.
Fast Regression with an $\ell_\infty$ Guarantee
Yi Li and David P. Woodruff.
Embeddings of Schatten Norms with Applications to Data Streams
Mikhail Raskin.
A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model
Euiwoong Lee.
Improved Hardness for Cut, Interdiction, and Firefighter Problems
Pasin Manurangsi.
Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
Daniel Lokshtanov, Amer Mouawad, Saket Saurabh and Meirav Zehavi.
Packing Cycles Faster Than Erdős-Pósa
Chengyu Lin and Shengyu Zhang.
Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
Shafi Goldwasser and Ofer Grossman.
Bipartite Perfect Matching in Pseudo-Deterministic NC
Amos Korman and Yoav Rodeh.
The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback
Josh Alman, Matthias Mnich and Virginia Vassilevska Williams.
Dynamic Parameterized Problems and Algorithms
Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh.
Covering vectors by spaces: Regular matroids
Talya Eden, Dana Ron and C. Seshadhri.
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev and Nicholas Spooner.
Interactive Oracle Proofs with Constant Rate and Query Complexity
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-Joung Kwon, Michał Pilipczuk, Roman Rabinovich and Sebastian Siebertz.
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Mathias Bæk Tejs Knudsen.
Additive Spanners and Distance Oracles in Quadratic Time
Antonios Antoniadis, Ruben Hoeksma, Julie Meissner, José Verschae and Andreas Wiese.
A QPTAS for the general scheduling problem with identical release dates
Sebastian Brandt, Yuval Emek, Jara Uitto and Roger Wattenhofer.
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
Benjamin Weitz and Prasad Raghavendra.
On the Bit Complexity of Sum-of-Squares Proofs
Matthias Kohler and Harald Räcke.
Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces
Robert Krauthgamer and Ohad Trabelsi.
Conditional Lower Bounds for All-Pairs Max-Flow
Florian Barbero, Christophe Paul and Michał Pilipczuk.
Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
Viswanath Nagarajan and Xiangkun Shen.
Online Covering with Sum of lq-Norm Objectives
Sara Ahmadian and Zachary Friggstad.
Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs
Ivona Bezakova, Radu Curticapean, Holger Dell and Fedor Fomin.
Finding Detours is Fixed-parameter Tractable
Rajesh Jayaram and Barna Saha.
Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultra-linear grammars are where Parsing Becomes Hard!
Greg Bodwin.
Testing Core Membership in Public Goods Economies
Jing Chen, Bo Li and Yingkai Li.
Efficient Approximations for the Online Dispersion Problem
Edward J. Lee and Serge Gaspers.
Exact Algorithms via Multivariate Subroutines
Shweta Agrawal and Ishaan Preet Singh.
Reusable Garbled Deterministic Finite Automata from Learning With Errors
Yoichi Iwata.
Linear-time Kernelization for Feedback Vertex Set
Lena Schlipf and Jens M. Schmidt.
Edge-Orders
Greg Bodwin, Fabrizio Grandoni, Merav Parter and Virginia Vassilevska Williams.
Preserving Distances in Very Faulty Graphs
Miriam Backens.
A new Holant dichotomy inspired by quantum computation
Toni Böhnlein, Stefan Kratsch and Oliver Schaudt.
Revenue maximization in Stackelberg Pricing Games: Beyond the combinatorial setting
Fedor Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi.
Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
Jiabao Lin and Hanpin Wang.
The Complexity of Holant Problems over Boolean Domain with Non-negative Weights
Venkatesan Guruswami, Chaoping Xing and Chen Yuan.
Subspace Designs based on Algebraic Function Fields
Marek Cygan, Marcin Mucha, Karol Węgrzycki and Michał Włodarczyk.
On problems equivalent to (min,+)-convolution
Omer Gold and Micha Sharir.
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
Aaron Bernstein, Yann Disser and Martin Groß.
General Bounds for Incremental Maximization
Pascal Schweitzer.
A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova and C. Seshadhri.
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
Jannik Matuschke, Tom Mccormick and Gianpaolo Oriolo.
Rerouting flows when links fail
Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis and Przemysław Uznański.
All-Pairs $2$-Reachability in $O(n^{\omega}\log n)$ Time
Christian Coester, Elias Koutsoupias and Philip Lazos.
The Infinite Server Problem
Andre Linhares and Chaitanya Swamy.
Improved Algorithms for MST and Metric-TSP Interdiction
Dimitris Achlioptas, Fotis Iliopoulos and Nikos Vlassis.
Stochastic Control via Entropy Compression
Ran Cohen, Sandro Coretti, Juan Garay and Vassilis Zikas.
Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols
Daniel Apon, Nico Döttling, Sanjam Garg and Pratyay Mukherjee.
Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13
Krzysztof Pietrzak and Maciej Skorski.
Non-Uniform Attacks Against Pseudoentropy
Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger and Nikos Parotsidis.
Decremental Data Structures for Connectivity and Dominators in Directed Graphs
Mika Göös, T.S. Jayram, Toniann Pitassi and Thomas Watson.
Randomized Communication vs. Partition Number
Andreas Björklund, Petteri Kaski and Ioannis Koutis.
Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
Andrej Bogdanov and Christopher Williamson.
Approximate Bounded Indistinguishability
Ilias Diakonikolas, Daniel Kane and Vladimir Nikishkin.
Near-optimal Closeness Testing of Discrete Histogram Distributions
Dariusz Dereniowski, Adrian Kosowski, Przemysław Uznański and Mengchuan Zou.
Approximation Strategies for Generalized Binary Search in Weighted Trees
Alex Galicki.
Polynomial-time Rademacher theorem, porosity and randomness
Marvin Künnemann, Ramamohan Paturi and Stefan Schneider.
On the Fine-grained Complexity of One-Dimensional Dynamic Programming
Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Seffi Naor and Roy Schwartz.
Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification
Richard Cleve and Chunhao Wang.
Efficient Quantum Algorithms for Simulating Lindblad Evolution
Yiannis Giannakopoulos, Elias Koutsoupias and Philip Lazos.
Online Market Intermediation
Juha Kärkkäinen, Marcin Piątkowski and Simon Puglisi.
String Inference from Longest-Common-Prefix Array
Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi and Michał Włodarczyk.
When the Optimum is also Blind: a New Perspective on Universal Optimization
Nick Gravin, Yuval Peres and Balasubramanian Sivan.
Tight Lower Bounds for Multiplicative Weights Algorithmic Families
Badih Ghazi and Madhu Sudan.
The Power of Shared Randomness in Uncertain Communication
Vasileios Nakos.
On Fast Decoding of High-Dimensional Signals from One-Bit Measurements
Cătălin Dohotaru and Peter Høyer.
Controlled quantum amplification
Omri Ben Eliezer, Simon Korman and Daniel Reichman.
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
Laura Mancinska, David Roberson, Robert Samal, Simone Severini and Antonios Varvitsiotis.
Relaxations of Graph Isomorphisms
Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele and Abdallah Saffidine.
The Parameterized Complexity of Positional Games