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-07-08Conference > Program > Track A

Track A 

Updated Tue Jul 8 16:02:07 CEST 2014

Tuesday 10.00–12.00 AUD1

Chair: Joan Boyar

  1. 10:00 György Dósa and Jiří Sgall. Optimal analysis of Best Fit bin packing
  2. 10:25 Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Reza Khani, Vahid Liaghat, Hamid Mahini and Harald Räcke. Online Stochastic Reordering Buffer Scheduling
  3. 10:50 Mohammadtaghi Hajiaghayi, Vahid Liaghat and Debmalya Panigrahi. Near-optimal Online Algorithms for Prize-collecting Steiner Problems
  4. 11:15 Erik D. Demaine, Yamming Huang, Chung-Shou Liao and Kunihiko Sadakane. Canadians Should Travel Randomly
  5. 11:40 Eric Blais, Johan Håstad, Rocco Servedio and Li-Yang Tan. On DNF approximators for monotone Boolean functions

Tuesday 13.00–14.35 AUD1

Chair: Troels Sørensen

  1. 13:00 Justin Hsu, Aaron Roth, Tim Roughgarden and Jonathan Ullman. Privately Solving Linear Programs
  2. 13:25 Uriel Feige and Shlomo Jozeph. Demand Queries with Preprocessing
  3. 13:50 Sayan Bhattacharya, Vahab Mirrokni and Janardhan Kulkarni. Coordination Mechanisms for (Selfish) Routing over Time on a Tree
  4. 14:15 Shahar Dobzinski and Renato Paes Leme. Efficiency Guarantees in Auctions with Budgets

Tuesday 15.00–16.35 AUD1

Chair: Christos Zaroliagis

  1. 15:00 Dmitry Gavinsky and Shachar Lovett. En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations
  2. 15:25 Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff. Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
  3. 15:50 Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun and Song Zuo. New decision tree complexity upper bounds in terms of sensitivity
  4. 16:15 Mohammad Bavarian, Dmitry Gavinsky and Tsuyoshi Ito. On the role of shared randomness in simultaneous communication

Wednesday 10.00–12.00 AUD1

Chair: Christian Wulff-Nielsen

  1. 10:00 (BEST PAPER) Andreas Björklund and Thore Husfeldt. Shortest Two Disjoint Paths in Polynomial Time
  2. 10:25 Mitsuru Kusumoto and Yuichi Yoshida. Testing Forest-Isomorphism in the Adjacency List Model
  3. 10:50 René Van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier and Gerhard J. Woeginger. Star Partitions of Perfect Graphs
  4. 11:15 Spyros Kontogiannis and Christos Zaroliagis. Distance Oracles for Time-Dependent Networks
  5. 11:40 Anna Gilbert, Yi Li, Ely Porat and Martin Strauss. For-all Sparse Recovery in Near-Optimal Time

Wednesday 13.00–14.35


Chair: Artur Czumaj

  1. 13:00 Therese Biedl. On Area-Optimal Planar Graph Drawings
  2. 13:25 Jens M. Schmidt. The Mondshein Sequence
  3. 13:50 Richard Cole and Howard Karloff. Fast Algorithms for Constructing Maximum Entropy Summary Trees
  4. 14:15 Konstantin Makarychev and Yury Makarychev. Nonuniform Graph Partitioning with Unrelated Weights


Chair: Jelani Nelson

  1. 13:00 Ved Prakash and Hartmut Klauck. An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
  2. 13:25 Yuval Emek and Adi Rosen. Semi-Streaming Set Cover
  3. 13:50 Yaoyu Wang and Yitong Yin. Certificates in Data Structures
  4. 14:15 Ankit Garg and Mark Braverman. Public vs private coin in bounded-round information

Thursday 10.00–12.00


Chair: Moni Naor

  1. 10:00 (BEST STUDENT PAPER) Sune K. Jakobsen. Information Theoretical Cryptogenography
  2. 10:25 Jop Briët, Zeev Dvir, Guangda Hu and Shubhangi Saraf. Lower Bounds for Approximate LDCs
  3. 10:50 Yuval Ishai and Hoeteck Wee. Partial Garbling Schemes and Their Applications
  4. 11:15 Manoj Prabhakaran, Amit Sahai and Akshay Wadia. Secure Computation using Leaky Tokens
  5. 11:40 Rafail Ostrovsky, Giuseppe Persiano and Ivan Visconti. On Input Indistinguishable Proof Systems


Chair: Kim Larsen

  1. 10:00 David Adjiashvili, Sandro Bosio, Robert Weismantel and Rico Zenklusen. Time-Expanded Packings
  2. 10:25 Wiebke Höhn, Julian Mestre and Andreas Wiese. How Unsplittable-Flow-Covering helps Scheduling with Job-Dependent Cost Functions
  3. 10:50 Noga Ron-Zewi, Eli Ben-Sasson, Julia Wolf and Madhur Tulsiani. Sampling-based proofs of almost-periodicity results and algorithmic applications
  4. 11:15 Amir Abboud, Virginia Vassilevska Williams and Oren Weimann. Consequences of Faster Alignment of Sequences
  5. 11:40 Eli Ben-Sasson and Emanuele Viola. Short PCPs with projection queries

Thursday 13.00–14.35


Chair: Thore Husfeldt

  1. 13:00 Xavier Allamigeon, Pascal Benchimol and Stephane Gaubert. The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time On Average
  2. 13:25 Christian Wulff-Nilsen. Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles
  3. 13:50 Pawel Gawrychowski, Shay Mozes and Oren Weimann. Improved Submatrix Maximum Queries in Monge Matrices
  4. 14:15 Konstantin Makarychev and Debmalya Panigrahi. Precedence-constrained Scheduling of Malleable Jobs with Preemption


Chair: Elias Koutsoupias

  1. 13:00 Tomasz Krawczyk and Bartosz Walczak. Coloring Relatives of Interval Overlap Graphs Via On-Line Games
  2. 13:25 Ittai Abraham and Shiri Chechik. Distance Labels with Optimal Local Stretch
  3. 13:50 Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani and Vincenzo Roselli. Morphing Planar Graph Drawings Optimally
  4. 14:15 Alexander Golovnev, Alexander Kulikov and Ivan Mihajlin. Families with infants: a general approach to solve hard partition problems

Thursday 15.00–16.35


Chair: Martin Dietzfelbinger

  1. 15:00 Raghu Meka, Omer Reingold, Guy Rothblum and Ron Rothblum. Fast Pseudorandomness for Independence and Load Balancing
  2. 15:25 Surender Baswana and Shahbaz Khan. Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
  3. 15:50 Amihood Amir, Timothy M. Chan, Moshe Lewenstein and Noa Lewenstein. On Hardness of Jumbled Indexing
  4. 16:15 John Iacono and Özgür Özkan. Why some heaps support constant-amortized-time decrease-key operations, and others do not


Chair: Jiří Sgall

  1. 15:00 Samir Datta, William Hesse and Raghav Kulkarni. Dynamic Complexity of Directed Rechability and Other Problems
  2. 15:25 Jiri Fiala, Pavel Klavík, Jan Kratochvil and Roman Nedela. Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
  3. 15:50 Michael Elkin, Ofer Neiman and Shay Solomon. Light Spanners
  4. 16:15 Anupam Gupta, Kunal Talwar and Udi Wieder. Changing Bases: Multistage Optimization for Matroids and Matchings


Chair: David Woodruff

  1. 15:00 Ilya Volkovich. On Learning, Lower Bounds and (un)Keeping Promises
  2. 15:25 Clément Canonne and Ronitt Rubinfeld. Testing probability distributions underlying aggregated data
  3. 15:50 Karl Wimmer, Yi Wu and Peng Zhang. Optimal query complexity for estimating the trace of a matrix
  4. 16:15 Zeev Dvir, Rafael Mendes de Oliveira and Amir Shpilka. Testing Equivalence of Polynomials under Shifts

Friday 10.00–12.00


Chair: Giuseppe Persiano

  1. 10:00 Scott Aaronson, Andris Ambainis, Kaspars Balodis and Mohammad Bavarian. Weak Parity
  2. 10:25 Laura Mancinska and Thomas Vidick. Unbounded entanglement can be needed to achieve the optimal success probability
  3. 10:50 Richard Cleve and Rajat Mittal. Characterization of Binary Constraint System Games.
  4. 11:15 Andrew Childs, David Gosset and Zak Webb. The Bose-Hubbard model is QMA-complete
  5. 11:40 André Chailloux and Giannicola Scarpa. Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost


Chair: Virginia Williams

  1. 10:00 Iddo Tzameret. Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem
  2. 10:25 Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha and Aarthi Sundaram. On the complexity of trial and error for constraint satisfaction problems
  3. 10:50 Barnaby Martin, Petar Markovic and Petar Dapic. QCSP on semicomplete digraphs
  4. 11:15 Subhash Khot, Madhur Tulsiani and Pratik Worah. The Complexity of Somewhat Approximation Resistant Predicates
  5. 11:40 Timon Hertli. Breaking the PPSZ Barrier for Unique 3-SAT


Chair: Uri Zwick

  1. 10:00 George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis. Determining Majority in Networks with Local Interactions and very Small Local Memory
  2. 10:25 Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter and Henning Thomas. Internal DLA: Efficient Simulation of a Physical Growth Model
  3. 10:50 Omer Reingold, Ron Rothblum and Udi Wieder. Pseudorandom Graphs in Data Structures
  4. 11:15 Artur Czumaj and Berthold Voecking. Thorp Shuffling, Butterflies, and Non-Markovian Couplings
  5. 11:40 Kunal Talwar and Udi Wieder. Balanced Allocations: A Simple Proof for the Heavily Loaded Case

Friday 13.00–15.25


Chair: Elias Koutsoupias

  1. 13:00 Mrinal Kumar and Shubhangi Saraf. Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
  2. 13:25 Jelani Nelson and Huy Nguyen. Lower bounds for oblivious subspace embeddings
  3. 13:50 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
  4. 14:15 Chinmay Hegde, Piotr Indyk and Ludwig Schmidt. Nearly Linear-Time Model-Based Compressive Sensing
  5. 14:40 Peyman Afshani, Timothy M. Chan and Konstantinos Tsakalidis. Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
  6. 15:05 Mehdi Tibouchi and Pierre-Alain Fouque. Close to Uniform Prime Number Generation With Fewer Random Bits


Chair: Mike Fellows

  1. 13:00 Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil and Somnath Sikdar. A Faster Parameterized Algorithm for Treedepth
  2. 13:25 Michael Lampis. Parameterized Approximation Schemes using Graph Widths
  3. 13:50 Markus Sortland Dregi and Daniel Lokshtanov. Parameterized Complexity of Bandwidth on Trees
  4. 14:15 Ramanujan M. S., Saket Saurabh, Pranabendu Misra, Manu Basavaraju, Fedor Fomin and Petr Golovach. Parameterized Algorithms to Preserve Connectivity
  5. 14:40 Madur Tulsiani, John Wright and Yuan Zhou. Optimal strong parallel repetition for projection games on low threshold rank graphs


Chair: Bengt J. Nilsson

  1. 13:00 Jin-Yi Cai, Heng Guo and Tyson Williams. Holographic Algorithms Beyond Matchgates
  2. 13:25 Pinyan Lu, Menghui Wang and Chihao Zhang. FPTAS for Weighted Fibonacci Gates and Its Applications
  3. 13:50 Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams and Uri Zwick. Listing Triangles
  4. 14:15 Yitong Yin. Spatial Mixing of Coloring Random Graphs
  5. 14:40 Swastik Kopparty, Mrinal Kumar and Michael Saks. Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields

Find this page Online