Menu

Track A

Regular papers

Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen and Adi ShamirTight Bounds on Online Checkpointing Algorithms
Aditya Bhaskara, Samira Daruki and Suresh VenkatasubramanianSublinear Algorithms for MAXCUT and Correlation Clustering
Alexander Conway, Martin Farach-Colton and Philip ShilaneOptimal Hashing in External Memory
Alexandra Kolla, Ioannis Koutis, Vivek Madan and Ali Kemal SinopSpectrally Robust Graph Isomorphism
Amey BhangaleNP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
Amir Abboud and Karl BringmannTighter Connections Between Formula-SAT and Shaving Logs
Anders Aamand, Mathias Bæk Tejs Knudsen and Mikkel ThorupPower of d Choices with Simple Tabulation
Anders Aamand, Niklas Hjuler, Jacob Holm and Eva RotenbergOne-Way Trail Orientations
Andreas Schmid and Jens M. SchmidtComputing Tutte Paths
Andrei Romashchenko and Marius ZimandAn operational characterization of mutual information in algorithmic information theory
Andrej BogdanovSmall bias requires large formulas
Anna Adamaszek, Matthias Mnich and Katarzyna PaluchNew Approximation Algorithms for (1,2)-TSP
Anupam Gupta, Amit Kumar and Jason LiNon-Preemptive Flow-Time Minimization via Rejections
Anupam Gupta, Ruta Mehta and Marco MolinaroMaximizing Profit with Convex Costs in the Random-order Model
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S. and Pasin ManurangsiParameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang and Lin YangApproximate Convex Hull of Data Streams
Bartlomiej Dudek and Pawel GawrychowskiEdit Distance between Unrooted Trees in Cubic Time
Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček, Karel Král, Hagar Mosaad and Veronika SlívováARRIVAL: Next Stop in CLS
Bernhard Haeupler, Amirbehshad Shahrasbi and Ellen VitercikSynchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
Bernhard Haeupler, Amirbehshad Shahrasbi and Madhu SudanSynchronization Strings: List Decoding for Insertions and Deletions
Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers and David WajcFully-Dynamic Bin Packing with Little Repacking
Buddhima Gamlath, Sangxia Huang and Ola SvenssonSemi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
Chinmay Nirkhe, Umesh Vazirani and Henry YuenApproximate low-weight check codes and circuit lower bounds for noisy ground states
Christoph Lenzen and Reut LeviA Centralized Local Algorithm for the Sparse Spanning Graph Problem
Clemens Rösner and Melanie SchmidtPrivacy preserving clustering with constraints
Daniel Kane, Shachar Lovett and Shay MoranGeneralized comparison trees for point-location problems
Davide BilòNew algorithms for Steiner tree reoptimization
Deeparnab Chakrabarty and Chaitanya SwamyInterpolating between $k$-Median and $k$-Center: Approximation Algorithms for Ordered $k$-Median
Deeparnab Chakrabarty and Maryam NegahbaniGeneralized Center Problems with Outliers
Eduard Eiben and Iyad KanjHow to navigate through obstacles?
Elette Boyle, Abhishek Jain, Manoj Prabhakaran and Ching-Hua YuThe Bottleneck Complexity of Secure Multiparty Computation
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh and Michael RiabzevFast Reed-Solomon Interactive Oracle Proofs of Proximity
Fedor Fomin, Petr Golovach and Fahad PanolanParameterized Low-Rank Binary Matrix Approximation
Felix Reidl and Magnus WahlströmParameterized Algorithms for Zero Extension and Metric Labelling Problems
Friedrich Eisenbrand, Christoph Hunkenschröder and Kim-Manuel KleinFaster Algorithms for Integer Programs with Block Structure
Hao Fu, Jian Li and Pan XuA PTAS for a Class of Stochastic Dynamic Programs
Hendrik Fichtenberger, Reut Levi, Yadu Vasudev and Maximilian WötzelA Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
Heng Guo and Mark JerrumPerfect Simulation of the Hard Disks Model by Partial Rejection Sampling
Heng Guo and Mark JerrumA polynomial-time approximation algorithm for all-terminal network reliability
Holger Dell, Martin Grohe and Gaurav RattanLovász Meets Weisfeiler and Leman
Ilias Diakonikolas, Themis Gouleakis, John Peebles and Eric PriceSample-Optimal Identity Testing with High Probability
Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei and Nicole WeinFinding Cliques in Social Networks: A New Distribution-Free Model
Jarosław Byrka, Piotr Skowron and Krzysztof SornatProportional Approval Voting, Harmonic k-median, and Negative Association
Daniele Micciancio and Jessica SorrellRing packing and amortized FHEW bootstrapping
Jiehua Chen, Danny Hermelin, Manuel Sorge and Harel YedidsionHow hard is it to satisfy (almost) all roommates?
Jisu Jeong, Eun Jung Kim and Sang-Il OumFinding branch-decompositions of matroids, hypergraphs, and more
Julia Chuzhoy, David H.K. Kim and Rachit NimavatImproved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary
Koyo HayashiA Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes
Krzysztof Onak, Baruch Schieber, Shay Solomon and Nicole WeinFully Dynamic MIS in Uniformly Sparse Graphs
L. Elisa Celis, Damian Straszak and Nisheeth K. VishnoiRanking with Fairness Constraints
L. Sunil Chandran, Davis Issac and Yun Kuen CheungSpanning Tree Congestion and Computation of Generalized Gy\H{o}ri-Lov{\'{a}}sz Partition
Lech Duraj, Grzegorz Gutowski and Jakub KozikA note on two-colorability of nonuniform hypergraphs
Manoj Gupta and Aditi SinghGeneric Single Edge Fault Tolerant Exact Distance Oracle
Manuel Bodirsky and Marcello MaminoA polynomial-time algorithm for median-closed semilinear constraints
Marco Carmosino, Russel Impagliazzo and Manuel SabinFine-Grained Derandomization: From Problem-Centric Complexity to Resource-Centric Complexity
Martin Grohe, Daniel Neuen, Pascal Schweitzer and Daniel WiebkingAn improved isomorphism test for bounded-tree-width graphs
Martin Koutecky, Asaf Levin and Shmuel OnnA Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
Michael Forbes, Sumanta Ghosh and Nitin SaxenaTowards blackbox identity testing of log-variate circuits
Michael LampisFiner Tight Bounds for Coloring on Clique-Width
Miriam BackensA complete dichotomy for complex-valued Holant^c
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein and David WajcDynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
Moses Charikar and Shay SolomonFully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier
Moses Charikar, Ofir Geri, Michael Kim and William KuszmaulOn Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings
Nil Mamano, David Eppstein, Michael Goodrich and Gill BarequetStable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms
Pankaj Agarwal, Haim Kaplan and Micha SharirUnion of hypercubes and 3d Minkowski sums with random sizes
Pawel Gawrychowski and Adam KarczmarzImproved Bounds for Shortest Paths in Dense Distance Graphs
Pawel Gawrychowski and Przemysław UznańskiTowards Unified Approximate Pattern Matching for Hamming and $L_1$ Distance
Pawel Gawrychowski, Gad Landau, Wing-Kin Sung and Oren WeimannA Faster Construction of Greedy Consensus Tree
Pawel Gawrychowski, Liran Markin and Oren WeimannA Faster FPTAS for #Knapsack
Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada and Kaja WilleGray codes and symmetric chains
Piotr SankowskiNC Algorithms for Weighted Planar Perfect Matching and Related Problems
Prosenjit Bose, Paz Carmi, Vida Dujmovic, Saeed Mehrabi, Fabrizio Montecchiani, Pat Morin and Luis Fernando Schultz Xavier Da SilveiraGeodesic Obstacle Representation of Graphs
Rafail Ostrovsky, Yuval Rabani and Arman YousefiStrictly Balancing Matrices in Polynomial Time Using Osborne’s Iteration
Anand Louis and Rakesh VenkatSemi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
Ran Duan and Hanlin RenApproximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
Ran Duan, Kaifeng Lyu and Yuanhang XieSingle-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs
Ran Duan, Yong Gu and Le ZhangImproved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs
Rohit Gurjar, Thomas Thierauf and Nisheeth VishnoiIsolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
Rotem Arnon-Friedman and Henry YuenNoise-tolerant testing of high entanglement of formation
Sariel Har-Peled, Piotr Indyk and Sepideh MahabadiApproximate Sparse Linear Regression
Shashwat GargQuasi-PTAS for Scheduling with Precedences using LP Hierarchies
Shay Golan, Tsvi Kopelowitz and Ely PoratTowards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams
Siu-Wing Cheng and Yuchen MaoRestricted Max-Min Fair Allocation
Sixue LiuChain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
Stefan WalzerLoad Thresholds for Cuckoo Hashing with Overlapping Blocks
Sumit Ganguly and David WoodruffHigh Probability Frequency Moment Sketches
Suryajith Chillara, Nutan Limaye and Srikanth SrinivasanA Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas
Tasuku Soma and Yuichi YoshidaA New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity
Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka and Jeffrey ShallitRollercoasters and Caterpillars
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana and Marianne ThieffryEfficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
Timothy Johnson, Michael T. Goodrich, William E. Devanny, Juan Jose Besa Vial and David EppsteinOptimally Sorting Evolving Data
Timothy M. Chan, Yakov Nekrich, Saladi Rahul and Konstantinos TsakalidisOrthogonal Point Location and Rectangle Stabbing Queries in 3-d
Tom Gur, Yang Liu and Ron RothblumAn Exponential Separation Between MA and AM Proofs of Proximity
Uriel Feige, Boaz Patt-Shamir and Shai VardiOn the Probe Complexity of Local Computation Algorithms
Vasileios Nakos, Xiaofei Shi, David P. Woodruff and Hongyang ZhangImproved Algorithms for Adaptive Compressed Sensing
Vladimir Braverman, Emanuele Viola, David P. Woodruff and Lin YangRevisiting Frequency Moment Estimation in Random Order Streams
Zdenek Dvorak and Ken-Ichi KawarabayashiAdditive non-approximability of chromatic number in proper minor-closed classes
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu and Yuhao ZhangOnline Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals
Zhuan Khye Koh and Laura SanitàStabilizing Weighted Graphs

Brief announcements

Amy Babay, Michael Dinitz and Zeyu ZhangCharacterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network
Ben Berger and Zvika BrakerskiZero-Knowledge Protocols for Search Problems
Daniel Graf, Karim Labib and Przemysław UznańskiHamming distance completeness and sparse matrix multiplication
Daniel Lokshtanov, Ramanujan M. S., Saket Saurabh, Roohani Sharma and Meirav ZehaviTreewidth Modulator: Emergency Exit for DFVS
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu and Samson ZhouRelaxed Locally Correctable Codes in Computationally Bounded Channels
Jing Chen, Bo Li, Yingkai Li and Pinyan LuBayesian Auctions with Efficient Queries
Mingyu Xiao and Hiroshi NagamochiBounded-Degree Bipartition is Fixed-Parameter Tractable
Navneet Agarwal, Sanat Anand and Manoj PrabhakaranOn Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC
Sofya Raskhodnikova and Nithin VarmaErasure-Resilience Versus Tolerance to Errors
Steven Chaplick, Minati De, Alexander Ravsky and Joachim SpoerhaseApproximation Schemes for Geometric Coverage Problems

Track B

Regular papers

Achim Blumensath and Felix WolfBisimulation Invariant Monadic-Second Order Logic in the Finite
Albert Atserias, Stephan Kreutzer and Marc NoyOn Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface
Alejandro Aguirre, Gilles Barthe, Justin Hsu and Alexandra SilvaAlmost Sure Productivity
Anaël Grandjean, Benjamin Hellouin de Menibus and Pascal VanierAperiodic Points in $\mathbb{Z}^2$-subshifts
Antoine Amarilli and Charles PapermanConstrained Topological Sorting
Dietrich Kuske and Nicole SchweikardtGaifman normal forms for counting extensions of first-order logic
Dirk Nowotka and Aleksi SaarelaAn optimal bound on the solution sets of one-variable word equations and its consequences
Gaëtan Douéneau-TabotOn the complexity of infinite advice strings
Géraud Sénizergues and Armin WeissThe isomorphism problem for finite extensions of free groups is in PSPACE
Ines KlimannTo Infinity and Beyond
Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz and Szymon ToruńczykFirst-order interpretations of bounded expansion classes
Jérôme LerouxPolynomial Vector Addition Systems With States
John Fearnley, Martin Gairing, Matthias Mnich and Rahul SavaniReachability Switching Games
Laure Daviaud, Ranko Lazić, Marcin Jurdziński, Filip Mazowiecki, Guillermo Perez and James WorrellWhen is Containment Decidable for Probabilistic Automata?
Lorenzo Clemente and Sławomir LasotaBinary reachability of timed pushdown automata via quantifier elimination
María Emilia Descotte, Diego Figueira and Gabriele PuppisResynchronizing Classes of Word Relations
Martin Fränzle, Mahsa Shirmohammadi, Mani Swaminathan and James WorrellCosts and Rewards in Priced Timed Automata
Mathieu Hoyrup, Diego Nava Saucedo and Donald StullSemicomputable geometry
Michał SkrzypczakUnambiguous languages exhaust the index hierarchy
Mikhail RaskinA superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
Moses Ganardi, Danny Hucke and Markus LohreyRandomized sliding window algorithms for regular languages
Ramanujan M. S., Daniel Lokshtanov, Saket Saurabh and Meirav ZehaviReducing CMSO Model Checking to Highly Connected Graphs
Sam Staton, Dario Stein, Hongseok Yang, Nathanael Ackerman, Cameron Freer and Daniel RoyThe Beta-Bernoulli process and algebraic effects
Samir Datta, Anish Mukherjee, Nils Vortmeier and Thomas ZeumeReachability and Distances under Multiple Changes
Sang-Ki Ko, Reino Niskanen and Igor PotapovOn the Identity Problem for the Special Linear Group and the Heisenberg Group
Sarah WinterUniformization Problems for Synchronizations of Automatic Relations on Words
Shaull Almagor, Dmitry Chistikov, Joel Ouaknine and James WorrellO-Minimal Invariants for Linear Loops
Stefan KieferOn Computing the Total Variation Distance of Hidden Markov Models
Thomas Place and Marc ZeitounSeparating without any ambiguity
Wojciech Czerwiński, Piotr Hofman and Georg ZetzscheUnboundedness problems for languages of vector addition systems

Track C

Regular papers

Boris Aronov, Gali Bar-On and Matthew KatzResolving SINR Queries in a Dynamic Setting
Dariusz Kowalski and Miguel A. MosteiroPolynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations
Eleni C. Akrida, George Mertzios, Paul Spirakis and Viktor ZamaraevTemporal Vertex Covers and Sliding Time Windows
Flavio Chierichetti and Shahrzad HaddadanOn the Complexity of Sampling Vertices Uniformly from a Graph
Frederik Mallmann-Trenn, Cameron Musco and Christopher MuscoEigenvector Computation and Community Detection in Asynchronous Gossip Models
George Christodoulou, Martin Gairing, Yiannis Giannakopoulos and Paul SpirakisThe Price of Stability of Weighted Congestion Games
Magnus M. Halldorsson, Guy Kortsarz, Pradipta Mitra and Tigran TonoyanSpanning Trees With Edge Conflicts and Wireless Connectivity
Megumi Ando, Anna Lysyanskaya and Eli UpfalPractical and Provably Secure Onion Routing
Merav Parter$(\Delta+1)$ Coloring in the Congested Clique Model
Ofer Grossman, Bernhard Haeupler and Sidhanth MohantyImproved Algorithms for the Noisy Broadcast Model under Erasures
Orna Kupferman and Gal VardiThe Unfortunate-Flow Problem
Riccardo Colini-Baldeschi, Max Klimm and Marco ScarsiniDemand-Independent Optimal Tolls
Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid and Sebastian WiederrechtCongestion-Free Rerouting of Flows on DAGs
Sarvar Patel, Giuseppe Persiano and Kevin YeoCacheShuffle: A Family of Oblivious Shuffles
Sébastien Bouchard, Yoann Dieudonne and Anissa LamaniByzantine Gathering in Polynomial Time
Sina Dehghani, Soheil Ehsani, Mohammadtaghi Hajiaghayi, Vahid Liaghat and Saeed SeddighinGreedy Algorithms for Online Survivable Network Design
Thomas Kesselheim and Bojana KodricPrice of Anarchy for Mechanisms with Risk-Averse Agents
Tobias Harks, Martin Hoefer, Anja Huber and Manuel SurekEfficient Black-Box Reductions for Separable Cost Sharing
Vittorio Bilò, Luca Moscardelli and Cosimo VinciUniform Mixed Equilibria in Network Congestion Games with Link Failures

Brief announcements

Eli Ben-Sasson and Eden SaigCollaborative Discovery: A study of Guru-Follower dynamics
Mohammadhossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, Mohammadtaghi Hajiaghayi and Vahab MirrokniMapReduce Algorithms For Massive Trees
Ran Ben Basat, Gil Einziger and Roy FriedmanGive Me Some Slack: Efficient Network Measurements
Shantanu Das, Dariusz Dereniowski and Przemysław UznańskiEnergy Constrained Depth First Search