Accepted Papers

Visualizer: Accepted Papers

Paper titles and author information appears as submitted.

Paper title and author changes will not be made to this page. The online program will reflect the most up-to-date presentation details, and is scheduled for posting in November.

ANACONDA: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing
Gautam Kamath and Christos Tzamos

A Fourier-Analytic Approach for the Discrepancy of Random Set Systems
Rebecca Hoberg and Thomas Rothvoss

Constructive Polynomial Partitioning for Algebraic Curves in R^3 with Applications
Boris Aronov, Esther Ezra and Josh Zahl

Fast Modular Subset Sum using Linear Sketching
Kyriakos Axiotis, Arturs Backurs and Christos Tzamos

Communication Complexity of Discrete Fair Division
Benjamin Plaut and Tim Roughgarden

A Faster External Memory Priority Queue with DecreaseKeys
Shunhua Jiang and Kasper Green Larsen

Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid
Niv Buchbinder, Moran Feldman and Mohit Garg

The Complexity of Approximately Counting Retractions
Jacob Focke, Leslie Ann Goldberg and Stanislav Živný

Distributed Maximal Independent Set using Small Messages
Mohsen Ghaffari

The threshold for SDP-refutation of random regular NAE-3SAT
Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm and Subhabrata Sen

New Lower Bounds for the Number of Pseudoline Arrangements
Adrian Dumitrescu and Ritankar Mandal

Optimal Ball Recycling
Michael A. Bender, Jake Christensen, Alexander Conway, Martin Farach-Colton, Rob Johnson and Meng-Tsung Tsai

A 1.5-Approximation for Path TSP
Rico Zenklusen

On $r$-Simple $k$-Path and Related Problems Parameterized by $k/r$
Gregory Gutin, Magnus Wahlstrom and Meirav Zehavi

Strategies for Stable Merge Sorting
Sam Buss and Alexander Knop

Oblivious resampling oracles and parallel algorithms for the Lopsided Lov\'{a}sz Local Lemma
David Harris

Polynomial bounds for centered colorings on proper minor-closed graph classes
Michał Pilipczuk and Sebastian Siebertz

Polynomial-time algorithm for Maximum Weight Independent Set on P_6 -free graphs
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk and Michał Pilipczuk

Deterministically Maintaining a $(2+\epsilon)$-Approximate Minimum Vertex Coverin $O(1/\epsilon^2)$ Amortized Update Time
Sayan Bhattacharya and Janardhan Kulkarni

Stochastic l_p Load Balancing and Moment Problems via the L-Function Method
Marco Molinaro

Analysis of Ward's Method
Anna Großwendt, Heiko Röglin and Melanie Schmidt

Flow-Cut Gaps and Face Covers in Planar Graphs
James R. Lee, Robert Krauthgamer and Havana Rika

Algorithms for #BIS-hard problems on expander graphs
Matthew Jenssen, Peter Keevash and Will Perkins

Spectral Sparsification of Hypergraphs
Tasuku Soma and Yuichi Yoshida

Vector clique decompositions
Raphael Yuster

Nash Flows Over Time with Spillback
Leon Sering and Laura Vargas Koch

Reproducibility and Pseudo-Determinism in Log-space
Ofer Grossman and Yang P. Liu

Towards Tight(er) Bounds for the Excluded Grid Theorem
Julia Chuzhoy and Zihan Tan

A Nearly-Linear Bound for Chasing Nested Convex Bodies
C.J. Argue, Sebastien Bubeck, Michael Cohen, Anupam Gupta and Yin Tat Lee

Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model
Shiri Chechik and Doron Mukhtar

Dynamic Double Auctions: Towards First Best
Santiago Balseiro, Vahab Mirrokni, Renato Paes Leme and Song Zuo

Maximum Integer Flows in Directed Planar Graphs with Multiple Sources and Sinks and Vertex Capacities
Yipu Wang

A sort of an adversary
Haim Kaplan, Or Zamir and Uri Zwick

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Aaron Bernstein, Sebastian Forster and Monika Henzinger

Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees
Amir Nayyeri and Benjamin Raichel

A New Path from Splay to Dynamic Optimality
Caleb Levy and Robert Tarjan

Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
David Eppstein and Bruce Reed

Binary Robust Positioning Patterns with Low Redundancy and Efficient Locating Algorithms
Yeow Meng Chee, Duc Tu Dao, Han Mao Kiah, San Ling and Hengjia Wei

A Polynomial Time Constant Approximation Algorithm For Minimizing Total Weighted Flow-time
Uriel Feige, Janardhan Kulkarni and Shi Li

A PTAS for Euclidean TSP with Hyperplane Neighborhoods
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma and Kevin Schewior

Cheeger Inequalities for Submodular Transformations
Yuichi Yoshida

A time- and space-optimal algorithm for the many-visits TSP
André Berger, László Kozma, Matthias Mnich and Roland Vincze

A Subquadratic Approximation Scheme for Partition
Marcin Mucha, Karol Wegrzycki and Michal Wlodarczyk

The streaming k-mismatch problem
Raphael Clifford, Tomasz Kociumaka and Ely Porat

On coalescence time in graphs--When is coalescing as fast as meeting?
Frederik Mallmann-Trenn, Varun Kanade and Thomas Sauerwald

The Andoni--Krauthgamer--Razenshteyn characterization of sketchable norms fails for sketchable metrics
Subhash Khot and Assaf Naor

Optimal Algorithm for Geodesic Nearest-point Geodesic Voronoi Diagrams in Simple Polygons
Eunjin Oh

Sublinear Algorithms for (∆ + 1) Vertex Coloring
Sepehr Assadi, Yu Chen and Sanjeev Khanna

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
Joshua Brakensiek and Venkatesan Guruswami

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Sepehr Assadi, Mohammadhossein Bateni, Aaron Bernstein, Vahab Mirrokni and Cliff Stein

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber and Shay Solomon

On the rank of a random binary matrix
Colin Cooper, Alan Frieze and Wesley Pegden

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
Jin-Yi Cai and Artsiom Hovarau

Can We Overcome the n log n Barrier for Oblivious Sorting?
Wei-Kai Lin, Elaine Shi and Tiancheng Xie

Stochastic Submodular Cover with Limited Adaptivity
Arpit Agarwal, Sepehr Assadi and Sanjeev Khanna

Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi and Michal Wlodarczyk

Exact Distance Oracles for Planar Graphs with Failing Vertices
Panagiotis Charalampopoulos, Shay Mozes and Benjamin Tebeka

I/O-Efficient Algorithms for Topological Sort and Related Problems
Nairen Cao, Jeremy Fineman, Katina Russell and Eugene Yang

k-Servers with a Smile: Projection-based Algorithms for Online Problems
Niv Buchbinder, Anupam Gupta, Marco Molinaro and Joseph Naor

Quantum algorithms and approximating polynomials for composed functions with shared inputs
Mark Bun, Robin Kothari and Justin Thaler

Minimizing Interference Potential Among Moving Entities
Daniel Busto, William Evans and David Kirkpatrick

Near Optimal Algorithms For The Single Source Replacement Paths Problem
Shiri Chechik and Sarel Cohen

Greedy spanners are optimal in doubling metrics
Hung Le, Glencora Borradaile and Christian Wulff-Nilsen

The Maximum Number of Minimal Dominating Sets in a Tree
Günter Rote

Tight Bounds for $\ell_p$ Oblivious Subspace Embeddings
Ruosong Wang and David P. Woodruff

Improving the smoothed complexity of FLIP for max cut problems
Charles Carlson, Ali Bibak and Karthekeyan Chandrasekaran

An Equivalence Class for Orthogonal Vectors
Lijie Chen and Ryan Williams

Pseudorandomness for read-k DNF formulas
Rocco Servedio and Li-Yang Tan

On Approximating (Sparse) Covering Integer Programs
Chandra Chekuri and Kent Quanrud

Optimal construction of compressed indices for highly repetitive texts with applications
Dominik Kempa

Testing Matrix Rank, Optimally
Maria-Florina Balcan, Yi Li, David P. Woodruff and Hongyang Zhang

On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
Rohit Gurjar and Nisheeth Vishnoi

Every Collinear Set Is Free
Vida Dujmovic, Fabrizio Frati, Daniel Goncalves, Pat Morin and Günter Rote

Beating Greedy for Stochastic Bipartite Matching
Buddhima Gamlath, Sagar Kale and Ola Svensson

Metrical task systems on trees via mirror descent and unfair gluing
Sébastien Bubeck, Michael B. Cohen, James R. Lee and Yin Tat Lee

Tight Revenue Gaps among Simple Mechanisms
Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang and Tao Xiao

On the Structure of Unique Shortest Paths in Graphs
Greg Bodwin

Submodular Function Maximization in Parallel via the Multilinear Relaxation
Chandra Chekuri and Kent Quanrud

Computing Height Persistence and Homology Generators in R^3 Efficiently
Tamal Dey

A tight Erdős-Pósa function for planar minors
Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret and Jean-Florent Raymond

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
Martin Nägele and Rico Zenklusen

Optimal lower bounds for distributed and streaming spanning forest computation
Jelani Nelson and Huacheng Yu

Zeros of Holant problems: locations and algorithms
Heng Guo, Chao Liao, Pinyan Lu and Chihao Zhang

Computing all Wardrop Equilibria parametrized by the Flow Demand
Max Klimm and Philipp Warode

The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain
Monaldo Mastrolilli

SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
Amir Abboud, Karl Bringmann, Danny Hermelin and Dvir Shabtay

Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity
Fahad Panolan, Saket Saurabh and Meirav Zehavi

Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design
Aleksandar Nikolov, Mohit Singh and Uthaipon Tantipongpipat

Four-coloring $P_6$-free graphs
Maria Chudnovsky, Sophie Spirkl and Mingxian Zhong

Relative Error Tensor Low Rank Approximation
Zhao Song, David P. Woodruff and Peilin Zhong

Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
Karl Bringmann, Marvin Künnemann and André Nusser

How to guess an $n$-digit number
Zilin Jiang and Nikita Polyanskii

Approximability of the Six-vertex Model
Jin-Yi Cai, Tianyu Liu and Pinyan Lu

A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials
Anurag Pandey, Gorav Jindal, Markus Bläser and Vishwas Bhargava

Foundations of Differentially Oblivious Algorithms
T-H. Hubert Chan, Chung Kai-Min, Maggs Bruce and Elaine Shi

Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić and Paweł Parys

The I/O complexity of Toom-Cook integer multiplication
Gianfranco Bilardi and Lorenzo De Stefani

Derandomized Balanced Allocation
Xue Chen

Approximating LCS in linear time: Beating the \sqrt{n} Barrier
Mohammadtaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin and Xiaorui Sun

Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence
Mohammadtaghi Hajiaghayi, Saeed Seddighin and Xiaorui Sun

Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities
Sivakanth Gopi, Venkatesan Guruswami and Sergey Yekhanin

A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
Nathaniel Lahn and Sharath Raghvendra

A φ-Competitive Algorithm for Scheduling Packets with Deadlines
Pavel Veselý, Marek Chrobak, Łukasz Jeż and Jiří Sgall

Towards Instance-Optimal Private Query Release
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov and Thomas Steinke

On Facility Location with General Lower Bounds
Shi Li

Optimal Lower Bounds for Sketching Graph Cuts
Charles Carlson, Alexandra Kolla, Nikhil Srivastava and Luca Trevisan

A (1+1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists
Chi-Kit Lam and C. Gregory Plaxton

Fine-grained Complexity Meets IP = PSPACE
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy Rothblum and Aviad Rubinstein

Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
Zachary Friggstad, Kamyar Khodamoradi and Mohammad Salavatipour

Efficiently Approximating Edit Distance Between Psuedorandom Strings
William Kuszmaul

Fully Polynomial-Time Approximation Schemes for Fair Rent Division
Eshwar Ram Arunachaleswaran, Siddharth Barman and Nidhi Rathi

Multi-unit Supply-monotone Auctions with Bayesian valuations
Yuan Deng and Debmalya Panigrahi

Improved bounds for sampling colorings via linear programming
Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau and Luke Postle

XOR Codes and Sparse Random Linear Equations with Noise
Andrej Bogdanov, Manuel Sabin and Prashant Nalini Vasudevan

Interval Vertex Deletion Admits a Polynomial Kernel
Akanksha Agrawal, Pranabendu Misra, Saket Saurabh and Meirav Zehavi

On the Spanning and Routing Ratio of Theta-Four
Prosenjit Bose, Jean-Lou De Carufel, Hill Darryl and Michiel Smid

Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
Mrinal Kumar, Ramprasad Saptharishi and Anamay Tengse

Lift and Project Algorithm for Precedence Constrained Scheduling to Minimize Weighted Completion Time
Shashwat Garg, Janardhan Kulkarni and Shi Li

Communication-Round Tradeoffs for Common Randomness and Secret Key Generation
Mitali Bafna, Badih Ghazi, Noah Golowich and Madhu Sudan

Approximability of p -> q matrix norms: Generalized Krivine rounding and hypercontractive hardness
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani

Elastic Caching
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar and Debmalya Panigrahi

Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu and Yuhao Zhang

Theorems of Caratheodory, Helly, and Tverberg without dimension
Karim Adiprasito, Imre Barany and Nabil Mustafa

Dynamic Edge Coloring with Improved Approximation
Ran Duan, Haoqing He and Tianyi Zhang

Planar Steiner Tree with Terminals on Few Faces
Sándor Kisfaludi-Bak, Jesper Nederlof and Erik Jan van Leeuwen

Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
Mohsen Ghaffari and Jara Uitto

(1 + eps)-Approximate Incremental Matching in Constant Deterministic Amortized Time
Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon

SETH Says: Weak Fr\'echet Distance is Faster, but only if it is Continuous and in One Dimension
Kevin Buchin, Tim Ophelders and Bettina Speckmann

Colored range closest-pair problem under general distance functions
Jie Xue

Quantum Speedups for Exact Exponential Dynamic Programming Algorithms
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis and Jevgēnijs Vihrovs

Lower Bounds for Oblivious Data Structures
Riko Jacob, Kasper Green Larsen and Jesper Buus Nielsen

Dimension-independent Sparse Fourier Transform
Michael Kapralov, Ameya Velingker and Amir Zandieh

An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem
Rebecca Reiffenhäuser

Improved Topological Approximations by Digitization
Aruni Choudhary, Michael Kerber and Sharath Raghvendra

Non-Empty Bins with Simple Tabulation Hashing
Anders Aamand and Mikkel Thorup

Probabilistic tensors and opportunistic Boolean matrix multiplication
Matti Karppa and Petteri Kaski

A PTAS for $\ell_p$-Low Rank Approximation
Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee and David P. Woodruff

Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems
Eli Fox-Epstein, Philip N. Klein and Aaron Schild

High-Dimensional Robust Mean Estimation in Nearly-Linear Time
Yu Cheng, Ilias Diakonikolas and Rong Ge

Efficient Algorithms and Lower Bounds for Robust Linear Regression
Ilias Diakonikolas, Weihao Kong and Alistair Stewart

Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
Irit Dinur, Yuval Filmus and Prahladh Harsha

List Decoding with Double Samplers
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon and Amnon Tashma

Polynomial Planar Directed Grid Theorem
Meike Hatzel, Ken-Ichi Kawarabayashi and Stephan Kreutzer

Correlation-Robust Analysis of Single Item Auction
Xiaohui Bei, Nick Gravin, Pinyan Lu and Zhihao Gavin Tang

Low Congestion Cycle Covers and Their Applications
Merav Parter and Eylon Yogev

Distributed Algorithms Made Secure: A Graph Theoretic Approach
Merav Parter and Eylon Yogev

Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices
Georgios Amanatidis and Pieter Kleer

Lower bounds for text indexing with mismatches and differences
Vincent Cohen-Addad, Laurent Feuilloley and Tatiana Starikovskaya

Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets
Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi and Ke Wu

Seeded Graph Matching via Large Neighborhood Statistics
Elchanan Mossel and Jiaming Xu

Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
Hendrik Fichtenberger, Pan Peng and Christian Sohler

Optimal Las Vegas Approximate Near Neighbors in l_p
Alexander Wei

Hierarchical Clustering Better Than Average-Linkage
Vaggos Chatziafratis, Moses Charikar and Rad Niazadeh

Pricing for Online Resource Allocation: Intervals and Paths
Shuchi Chawla, Benjamin Miller and Yifeng Teng

Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
Ahmed Abdelkader, Sunil Arya, Guilherme D. Da Fonseca and David Mount

Approximating (k,l)-center clustering for curves
Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler and Martijn Struijs

Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions
Kyle Fox, Debmalya Panigrahi and Fred Zhang

Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Thatchaphol Saranurak and Di Wang

Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts
Karl Bringmann, Marvin Künnemann and Philip Wellnitz

On the discrepancy of random low degree set systems
Nikhil Bansal and Raghu Meka

Optimizing quantum optimization algorithms via faster quantum gradient computation
Andras Pal Gilyen, Srinivasan Arunachalam and Nathan Wiebe

Short Cycles via Low-Diameter Decompositions
Yang P. Liu, Sushant Sachdeva and Zejun Yu

Prophet Secretary Through Blind Strategies
Jose Correa, Raimundo Saona and Bruno Ziliotto

Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
Amirmahdi Ahmadinejad, Arun Jambulapati, Amin Saberi and Aaron Sidford

Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
Mohammadhossein Bateni, Alireza Farhadi and Mohammadtaghi Hajiaghayi

Adaptive Sparse Recovery with Limited Adaptivity
Akshay Kamath and Eric Price

From Local to Central Differential Privacy
Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar and Abhradeep Thakurta

Fast greedy for linear matroids
Huy Nguyen

Hardness of Approximation for Morse Matching
Ulrich Bauer and Abhishek Rathod

Distributed Triangle Detection via Expander Decomposition
Yi-Jun Chang, Seth Pettie and Hengjie Zhang

On constant multi-commodity flow-cut gaps for families of directed minor-free graphs
Ario Salmasi, Anastasios Sidiropoulos and Vijay Sridhar

Iterative Refinement for l_p-norm Regression
Deeksha Adil, Rasmus Kyng, Richard Peng and Sushant Sachdeva

Testing Halfspaces over Rotation-Invariant Distributions
Nathaniel Harms

Assignment Mechanisms under Distributional Constraints
Itai Ashlagi, Amin Saberi and Ali Shameli

Stochastic Matching with Few Queries: New Algorithms and Tools
Soheil Behnezhad, Alireza Farhadi, Mohammadtaghi Hajiaghayi and Nima Reyhani

Extremal and probabilistic results for order types
Jie Han, Yoshiharu Kohayakawa, Marcelo Sales and Henrique Stagni

Exponential lower bounds on spectrahedral representations of hyperbolicity cones
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava and Benjamin Weitz

Full Tilt: Universal Constructors for General Shapes with Uniform External Forces
Austin Luchsinger, Angel Cantu, Jose Balanza Martinez, David Caballero, Rene Reyes, Robert Schweller and Tim Wylie

Popular Matchings and Limits to Tractability
Yuri Faenza, Telikepalli Kavitha, Vladlena Powers and Xingyu Zhang

Popular Matching in Roommates Setting is NP-hard
Sushmita Gupta, Pranabendu Misra, Saket Saurabh and Meirav Zehavi

Submodular Maximization with Optimal Approximation, Adaptivity and Query Complexity
Matthew Fahrbach, Vahab Mirrokni and Morteza Zadimoghaddam

Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
Alina Ene and Huy Nguyen

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Eric Balkanski, Aviad Rubinstein and Yaron Singer