We use cookies to collect statistics

We start using cookies when you continue to another page. You can decline data collection by clicking here. We will use a cookie to remember your choice.

If you wish to avoid cookies altogether, you must disable cookies in your browser settings. However, rejecting all cookies will result in losing some of the functionalities of the website.

Read more about the IT University's use of cookies.

ICALP logo
Skip to content

Last updated on 2014-05-08Conference > Accepted Papers

Accepted Papers 

Track A: Algorithms, Complexity, and Games

  • Iddo Tzameret, Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem
  • Mehdi Tibouchi and Pierre-Alain Fouque, Close to Uniform Prime Number Generation With Fewer Random Bits
  • Dmitry Gavinsky and Shachar Lovett, En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations
  • Pawel Gawrychowski, Shay Mozes, and Oren Weimann, Improved Submatrix Maximum Queries in Monge Matrices
  • Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Reza Khani, Vahid Liaghat, Hamid Mahini, and Harald Räcke, Online Stochastic Reordering Buffer Scheduling
  • Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar, A Faster Parameterized Algorithm for Treedepth
  • Noga Ron-Zewi, Eli Ben-Sasson, Julia Wolf, and Madhur Tulsiani, Sampling-based proofs of almost-periodicity results and algorithmic applications
  • Scott Aaronson, Andris Ambainis, Kaspars Balodis, and Mohammad Bavarian, Weak Parity
  • Mitsuru Kusumoto and Yuichi Yoshida, Testing Forest-Isomorphism in the Adjacency List Model
  • Jop Briët, Zeev Dvir, Guangda Hu, and Shubhangi Saraf, Lower Bounds for Approximate LDCs
  • René Van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger, Star Partitions of Perfect Graphs
  • Andreas Björklund and Thore Husfeldt, Shortest Two Disjoint Paths in Polynomial Time
  • Justin Hsu, Aaron Roth, Tim Roughgarden, and Jonathan Ullman, Privately Solving Linear Programs
  • Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, and Aarthi Sundaram, On the complexity of trial and error for constraint satisfaction problems
  • David Adjiashvili, Sandro Bosio, Robert Weismantel and, Rico Zenklusen, Time-Expanded Packings
  • Spyros Kontogiannis and Christos Zaroliagis, Distance Oracles for Time-Dependent Networks
  • Uriel Feige and Shlomo Jozeph, Demand Queries with Preprocessing
  • Jin-Yi Cai, Heng Guo, and Tyson Williams, Holographic Algorithms Beyond Matchgates
  • Therese Biedl, On Area-Optimal Planar Graph Drawings
  • Barnaby Martin, Petar Markovic, and Petar Dapic, QCSP on semicomplete digraphs
  • Wiebke Höhn, Julian Mestre, and Andreas Wiese, How Unsplittable-Flow-Covering helps Scheduling with Job-Dependent Cost Functions
  • Jens M. Schmidt, The Mondshein Sequence
  • Subhash Khot, Madhur Tulsiani, and Pratik Worah, The Complexity of Somewhat Approximation Resistant Predicates
  • Richard Cole and Howard Karloff, Fast Algorithms for Constructing Maximum Entropy Summary Trees
  • Konstantin Makarychev and Yury Makarychev, Nonuniform Graph Partitioning with Unrelated Weights
  • Ilya Volkovich, On Learning, Lower Bounds and (un)Keeping Promises
  • Mohammadtaghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi, Near-optimal Online Algorithms for Prize-collecting Steiner Problems
  • Yuval Ishai and Hoeteck Wee, Partial Garbling Schemes and Their Applications
  • Pinyan Lu, Menghui Wang, and Chihao Zhang, FPTAS for Weighted Fibonacci Gates and Its Applications
  • Surender Baswana and Shahbaz Khan, Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
  • Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff, Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
  • György Dósa and Jiří Sgall, Optimal analysis of Best Fit bin packing
  • Ved Prakash and Hartmut Klauck, An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
  • Alexander Golovnev, Alexander Kulikov, and Ivan Mihajlin, Families with infants: a general approach to solve hard partition problems
  • George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis, Determining Majority in Networks with Local Interactions and very Small Local Memory
  • Xavier Allamigeon, Pascal Benchimol, and Stephane Gaubert, The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time On Average
  • Sune K. Jakobsen, Information Theoretical Cryptogenography
  • Peyman Afshani, Timothy M. Chan, and Konstantinos Tsakalidis, Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
  • Jelani Nelson and Huy Nguyen, Lower bounds for oblivious subspace embeddings
  • Eli Ben-Sasson and Emanuele Viola, Short PCPs with projection queries
  • Sayan Bhattacharya, Vahab Mirrokni, and Janardhan Kulkarni, Coordination Mechanisms for (Selfish) Routing over Time on a Tree
  • Amihood Amir, Timothy M. Chan, Moshe Lewenstein and, Noa Lewenstein, On Hardness of Jumbled Indexing
  • Shahar Dobzinski and Renato Paes Leme, Efficiency Guarantees in Auctions with Budgets
  • Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, and Henning Thomas, Internal DLA: Efficient Simulation of a Physical Growth Model
  • Samir Datta, William Hesse and, Raghav Kulkarni, Dynamic Complexity of Directed Rechability and Other Problems
  • Michael Lampis, Parameterized Approximation Schemes using Graph Widths
  • Erik D. Demaine, Yamming Huang, Chung-Shou Liao, and Kunihiko Sadakane, Canadians Should Travel Randomly
  • Laura Mancinska and Thomas Vidick, Unbounded entanglement can be needed to achieve the optimal success probability
  • Omer Reingold, Ron Rothblum, and Udi Wieder, Pseudorandom Graphs in Data Structures
  • Jiri Fiala, Pavel Klavík, Jan Kratochvil and, Roman Nedela, Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
  • Michael Elkin, Ofer Neiman, and Shay Solomon, Light Spanners
  • Zeev Dvir, Rafael Mendes de Oliveira, and Amir Shpilka, Testing Equivalence of Polynomials under Shifts
  • Richard Cleve and Rajat Mittal, Characterization of Binary Constraint System Games.
  • Raghu Meka, Omer Reingold, Guy Rothblum and, Ron Rothblum, Fast Pseudorandomness for Independence and Load Balancing
  • Anna Gilbert, Yi Li, Ely Porat, and Martin Strauss, For-all Sparse Recovery in Near-Optimal Time
  • Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick, Listing Triangles
  • Andrew Childs, David Gosset, and Zak Webb, The Bose-Hubbard model is QMA-complete
  • Konstantin Makarychev and Debmalya Panigrahi, Precedence-constrained Scheduling of Malleable Jobs with Preemption
  • Yitong Yin, Spatial Mixing of Coloring Random Graphs
  • Timon Hertli, Breaking the PPSZ Barrier for Unique 3-SAT
  • Yaoyu Wang and Yitong Yin, Certificates in Data Structures
  • John Iacono, Why some heaps support constant-amortized-time decrease-key operations, and others do not
  • Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann, Consequences of Faster Alignment of Sequences
  • Ramanujan M. S., Saket Saurabh, Pranabendu Misra, Manu Basavaraju, Fedor Fomin, and Petr Golovach, Parameterized Algorithms to Preserve Connectivity
  • Clément Canonne and Ronitt Rubinfeld, Testing probability distributions underlying aggregated data
  • Eric Blais, Johan Håstad, Rocco Servedio, and Li-Yang Tan, On DNF approximators for monotone Boolean functions
  • Yuval Emek and Adi Rosen, Semi-Streaming Set Cover
  • Markus Sortland Dregi and Daniel Lokshtanov, Parameterized Complexity of Bandwidth on Trees
  • Mrinal Kumar and Shubhangi Saraf, Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
  • Erik D. Demaine, Martin Demaine, Sandor Fekete, Matthew Patitz, Robert Schweller, Andrew Winslow, and Damien Woods, One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
  • Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo, Tighter relations between sensitivity and other complexity measures
  • Manoj Prabhakaran, Amit Sahai, and Akshay Wadia, Secure Computation using Leaky Tokens
  • André Chailloux and Giannicola Scarpa, Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
  • Mohammad Bavarian, Dmitry Gavinsky, and Tsuyoshi Ito, On the role of shared randomness in simultaneous communication
  • Ankit Garg and Mark Braverman, Public vs private coin in bounded-round information
  • Rafail Ostrovsky, Giuseppe Persiano, and Ivan Visconti, On Input Indistinguishable Proof Systems
  • Artur Czumaj and Berthold Voecking, Thorp Shuffling, Butterflies, and Non-Markovian Couplings
  • Kunal Talwar and Udi Wieder, Balanced Allocations: A Simple Proof for the Heavily Loaded Case
  • Anupam Gupta, Kunal Talwar, and Udi Wieder, Changing Bases: Multistage Optimization for Matroids and Matchings
  • Swastik Kopparty, Mrinal Kumar, and Michael Saks, Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
  • Karl Wimmer, Yi Wu, and Peng Zhang, Optimal query complexity for estimating the trace of a matrix
  • Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt, Nearly Linear-Time Model-Based Compressive Sensing
  • Tomasz Krawczyk and Bartosz Walczak, Coloring Relatives of Interval Overlap Graphs Via On-Line Games
  • Christian Wulff-Nilsen, Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles
  • Ittai Abraham and Shiri Chechik, Distance Labels with Optimal Local Stretch
  • Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli, Morphing Planar Graph Drawings Optimally
  • Madur Tulsiani, John Wright, and Yuan Zhou, Optimal strong parallel repetition for projection games on low threshold rank graphs

Track B: Logic, Semantics, Automata, and Theory of Programming

Track C: Foundations of Networked Computation



Find this page Online