ICALP (1)

Publications

2015

Matthew Coudron, Thomas Vidick
Interactive Proofs with Approximately Commuting Provers. ICALP (1) (2015)
Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
Condensed Unpredictability. ICALP (1) (2015)
Lila Kari, Steffen Kopecki, Pierre-Étienne Meunier, Matthew J. Patitz, Shinnosuke Seki
Binary Pattern Tile Set Synthesis Is NP-hard. ICALP (1) (2015)
Sumit Ganguly
Taylor Polynomial Estimator for Estimating Frequency Moments. ICALP (1) (2015)
Yossi Azar, Ilan Reuven Cohen
Serving in the Dark should be done Non-Uniformly. ICALP (1) (2015)
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Paul G. Spirakis, Przemyslaw Uznanski
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols. ICALP (1) (2015)
Leslie Ann Goldberg, Rob Gysel, John Lapinskas
Approximately Counting Locally-Optimal Structures. ICALP (1) (2015)
Yann Disser, Max Klimm, Elisabeth Lübbecke
Scheduling Bidirectional Traffic on a Path. ICALP (1) (2015)
Huacheng Yu
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication. ICALP (1) (2015)
Zdenek Dvorák, Martin Kupec
On Planar Boolean CSP. ICALP (1) (2015)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Feasible Interpolation for QBF Resolution Calculi. ICALP (1) (2015)
Benjamin A. Burton, Clément Maria, Jonathan Spreer
Algorithms and Complexity for Turaev-Viro Invariants. ICALP (1) (2015)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. ICALP (1) (2015)
Johan Thapper, Stanislav Zivný
Sherali-Adams Relaxations for Valued CSPs. ICALP (1) (2015)
Serge Gaspers, Gregory B. Sorkin
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. ICALP (1) (2015)
Peter Fulla, Stanislav Zivný
A Galois Connection for Valued Constraint Languages of Infinite Size. ICALP (1) (2015)
Shweta Agrawal, Yuval Ishai, Dakshita Khurana, Anat Paskin-Cherniavsky
Statistical Randomized Encodings: A Complexity Theoretic View. ICALP (1) (2015)
Chandra Chekuri, Shalmoli Gupta, Kent Quanrud
Streaming Algorithms for Submodular Function Maximization. ICALP (1) (2015)
Sevag Gharibian, Jamie Sikora
Ground State Connectivity of Local Hamiltonians. ICALP (1) (2015)
Lingxiao Huang, Jian Li
Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points. ICALP (1) (2015)
Mark Bun, Justin Thaler
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. ICALP (1) (2015)
Oded Goldreich, Tom Gur, Ron D. Rothblum
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract). ICALP (1) (2015)
Susanne Albers, Dario Frascaria
Quantifying Competitiveness in Paging with Locality of Reference. ICALP (1) (2015)
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
On the Hardest Problem Formulations for the 0/1 0 / 1 Lasserre Hierarchy. ICALP (1) (2015)
Aleksandar Nikolov
An Improved Private Mechanism for Small Databases. ICALP (1) (2015)
Clément L. Canonne
Big Data on the Rise? - Testing Monotonicity of Distributions. ICALP (1) (2015)
Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao Wang
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains. ICALP (1) (2015)
Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. ICALP (1) (2015)
Sungjin Im, Benjamin Moseley
Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities. ICALP (1) (2015)
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria. ICALP (1) (2015)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Lower Bounds for the Graph Homomorphism Problem. ICALP (1) (2015)
Jerry Li, John Peebles
Replacing Mark Bits with Randomness in Fibonacci Heaps. ICALP (1) (2015)
Balagopal Komarath, Jayalal Sarma, K. S. Sunil
Comparator Circuits over Finite Bounded Posets. ICALP (1) (2015)
Christoph Berkholz, Martin Grohe
Limitations of Algebraic Approaches to Graph Isomorphism Testing. ICALP (1) (2015)
Paul Beame, Vincent Liew, Mihai Patrascu
Finding the Median (Obliviously) with Bounded Space. ICALP (1) (2015)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set. ICALP (1) (2015)
Marvin Künnemann, Bodo Manthey
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. ICALP (1) (2015)
Marcin Kozik, Joanna Ochremiak
Algebraic Properties of Valued Constraint Satisfaction Problem. ICALP (1) (2015)
Hamid Jahanjou, Eric Miles, Emanuele Viola
Local Reductions. ICALP (1) (2015)
Omri Weinstein, David P. Woodruff
The Simultaneous Communication of Disjointness with Applications to Data Streams. ICALP (1) (2015)
Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time. ICALP (1) (2015)
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set. ICALP (1) (2015)
Gil Cohen, Igor Shinkar
Zero-Fixing Extractors for Sub-Logarithmic Entropy. ICALP (1) (2015)
Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
Spotting Trees with Few Leaves. ICALP (1) (2015)
Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha
Lower Bounds for Sums of Powers of Low Degree Univariates. ICALP (1) (2015)
Pawel Gawrychowski, Shay Mozes, Oren Weimann
Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search. ICALP (1) (2015)
Ágnes Cseh, Chien-Chung Huang, Telikepalli Kavitha
Popular Matchings with Two-Sided Preferences and One-Sided Ties. ICALP (1) (2015)
Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi
Finding a Path in Group-Labeled Graphs with Two Labels Forbidden. ICALP (1) (2015)
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland
Relative Discrepancy Does not Separate Information and Communication Complexity. ICALP (1) (2015)

volume 9134, 2015

Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I ICALP (1) 9134 (2015)