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