Skip to content

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

Abstracts

 

Find this page Online

https://icalp2014.itu.dk/Conference/Accepted-Papers