Skip to content

Last updated on 2020-08-20Conference > 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