Detailed Program -- Track A

See also the complete program, or the topics and PC of Track A.

Tuesday, July 6

10:30 session 1: Combinatorial Optimization

  • Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse and Ljubomir Perkovic. Plane spanners of maximum degree six
  • Jop Briet, Fernando Mario de Oliveira Filho and Frank Vallentin. The positive semidefinite Grothendieck problem with rank constraint
  • Amihood Amir, Estrella Eisenberg, Avivit Levy, Ely Porat and Natalie Shapira. Cycle Detection and Correction
  • Daniel Kral. Decomposition width of matroids

14:00 session 2a: Game Theory

  • MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica and Hamid Mahini. The cooperative game theory foundations of network bargaining games
  • Tobias Harks and Max Klimm. On the Existence of Pure Nash Equilibria in Weighted Congestion Games
  • Allan Borodin and Brendan Lucier. On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions
  • Albert Atserias and Elitza Maneva. Mean-payoff games and propositional proofs

14:00 session 2b: Security

  • Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi and Piotr Sankowski. Online Network Design with Outliers
  • Benoit Libert and Moti Yung. Efficient Completely Non-Malleable Public Key Encryption
  • Tsuyoshi Ito. Polynomial-Space Approximation of No-Signaling Provers
  • Benny Applebaum, Yuval Ishai and Eyal Kushilevitz. From Secrecy to Soundness: Efficient Verification via Secure Computation

16:30 session 3a: Data Structures

  • Ozgur Ozkan and John Iacono. Mergeable Dictionaries
  • Jittat Fakcharoenphol, Bundit Laekhanukit and Danupon Nanongkai. Faster Algorithms for Semi-Matching Problems
  • Mingji Xia. Holographic reduction: a domain changed application and its partial converse theorems
  • Ran Duan. New Data Structures for Subgraph Connectivity

16:30 session 3b: Sorting & Hashing

  • Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh and Michael Rink. Tight Thresholds for Cuckoo Hashing via XORSAT
  • Richard Cole and Vijaya Ramachandran. Resource Oblivious Sorting on Multicores
  • Rosa M. Jiménez and Conrado Martinez. Interval Sorting

Wednesday, July 7

10:30 session 4: Graphs, Nets and Optimization

  • Nikhil Bansal and Subhash Khot. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
  • Anupam Gupta, Viswanath Nagarajan and R Ravi. Thresholded Covering Algorithms for Robust and Max-Min Optimization
  • Jin-Yi Cai, Xi Chen and Pinyan Lu. Graph Homomorphisms with Complex Values: A Dichotomy Theorem
  • Nikhil Bansal, Niv Buchbinder and Seffi Naor. Metrical Task Systems and the k-Server Problem on HSTs

14:00 session 5a: Scheduling

  • Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, José Verschae and Andreas Wiese. Scheduling periodic tasks in a hard real-time environment
  • Anupam Gupta, Ravishankar Krishnaswamy and Kirk Pruhs. Scalably Scheduling Power-Heterogeneous Processors
  • Nikhil Bansal, Ravishankar Krishnaswamy and Viswanath Nagarajan. Better Scalable Algorithms for Broadcast Scheduling
  • Leah Epstein, Asaf Levin and Rob van Stee. Max-min online allocations with a reordering buffer

14:00 session 5b: Graphs & Hypergraphs

  • Nikolaos Fountoulakis and Konstantinos Panagiotou. Orientability of Random Hypergaphs and the Power of Multiple Choices
  • Venkatesan Guruswami and Rishi Saket. On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
  • Juanjo Rué, Ignasi Sau and Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces
  • Johannes Koebler, Sebastian Kuhnert, Bastian Laubner and Oleg Verbitsky. Interval Graphs: Canonical Representation in Logspace

Chair: Burkhard Monien

  • Leslie Ann Goldberg and Mark Jerrum. Approximating the Partition Function of the Ferromagnetic Potts Model
  • George B. Mertzios, Ignasi Sau, Mordechai Shalom and Shmuel Zaks. Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests
  • Yijia Chen and Jörg Flum. On optimal proof systems and logics for PTIME

Thursday, July 8

10:30 session 7: Algebraic Problems

  • Amir Shpilka and Ilya Volkovich. On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
  • Bruce Litow. On Sums of Roots of Unity
  • Holger Dell, Thore Husfeldt and Martin Wahlén. Exponential Time Complexity of the Permanent and the Tutte Polynomial
  • Amitabha Bhattacharya, Bhaskar DasGupta, Dhruv Mubayi and Gyrogy Turan. On Approximate Horn Formula Minimization

Friday, July 9

10:30 session 8: Networks & Communication Complexity

  • Amos Beimel, Sebastian Ben Daniel, Eyal Kushilevitz and Enav Weinreb. Choosing, Agreeing, and Eliminating in Communication Complexity
  • David Woodruff. Additive Spanners in Nearly Quadratic Time
  • Troy Lee and Shengyu Zhang. Composition theorems in communication complexity
  • Fabrizio Grandoni and Thomas Rothvoss. Network Design via Core Detouring for Problems Without a Core

16:30 session 9a: Complexity & Automata

  • Klaus Ambos-Spies and Timur Bakibayev. Weak Completeness Notions for Exponential Time
  • Mikołaj Bojańczyk and Paweł Parys. Efficient Evaluation of Nondeterministic Automata Using Factorization Forests
  • Tobias Jacobs, Ferdinando Cicalese, Eduardo Laber and Marco Molinaro. On the Complexity of Searching in Trees: Average-case Minimization

16:30 session 9b: Finding & Testing

  • Hari Krovi, Frederic Magniez, Maris Ozols and Jérémie Roland. Finding is as easy as detecting for quantum walks
  • Mahdi Cheraghchi. Improved Constructions for Non-adaptive Threshold Group Testing
  • Ronitt Rubinfeld and Ning Xie. Testing Non-uniform k-wise Independent Distributions over Product Spaces

Saturday, July 10

10:30 session 10a: Approximations

  • Danny Segev and Iftah Gamzu. A Sublogarithmic Approximation for Highway and Tollbooth Pricing
  • Konstantin Makarychev, Rajsekar Manokaran and Maxim Sviridenko. Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
  • Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen and Jakob Truelsen. Cell Probe Lower Bounds and Approximations for Range Mode
  • Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani and Yi Wu. SDP gaps for 2-to-1 and other Label-Cover variants

10:30 session 10b: Streaming & Preprocessing

  • Atri Rudra and Steve Uurtamo. Data Stream Algorithms for Codeword Testing
  • Bjarni Halldorsson, Magnus M. Halldorsson, Elena Losievskaja and Mario Szegedy. Streaming algorithms for independent sets
  • Stefan Kratsch and Magnus Wahlström. Preprocessing of Min Ones Problems: A Dichotomy
  • Jian Li, Ke Yi and Qin Zhang. Clustering with Diversity

14:00 session 11a: Adaptive, Knowledge & Optimality

  • Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan and R Ravi. Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
  • Andrew C. Yao, Moti Yung and Yunlei Zhao. Concurrent Knowledge Extraction in the Public-Key Model

14:00 session 11b: Covering, Graphs & Independence

  • Mihai Patrascu and Mikkel Thorup. On the k-Independence Required by Linear Probing and Minwise Independence
  • Andreas Björklund, Thore Husfeldt, Mikko Koivisto and Petteri Kaski. Covering and Packing in Linear Space
  • Loukas Georgiadis. Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs


Conference Information


Blix theme adapted by David Gilbert, powered by PmWiki