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.
Faster Deterministic Distributed Coloring Through Recursive List Coloring
Fabian Kuhn
Connectivity of Triangulation Flip Graphs in the Plane
Uli Wagner, Emo Welzl
Computing Minimal Persistent Cycles: Polynomial and Hard Cases
Tamal K. Dey, Tao Hou, Sayan Mandal
A randomly weighted minimum tree with a random cost constraint
Alan Frieze, Tomasz Tkocz
Learning from satisfying assignments under continuous distributions
Clement Canonne, Anindya De, Rocco A. Servedio
Normalizers and permutational isomorphisms in simply-exponential time
Daniel Wiebking
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos
A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs
Yutaro Yamaguchi
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri
The rank of sparse random matrices
Amin Coja-Oghlan, Alperen A. Ergür, Pu Gao, Samuel Hetterich, Maurice Rolvien
Reconstruction of Depth-$4$ Multilinear Circuits
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
A Nearly Optimal Data Structure for the k Nearest Neighbor Problem in the Plane under General Distance Functions
Chih-Hung Liu
2-Approximating Feedback Vertex Set in Tournaments
Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
Brian Axelrod, Yang P. Liu, Aaron Sidford
Quasi-popular Matchings, Optimality, and Extended Formulations
Yuri Faenza, Kavitha Telikepalli
Exponential Separations in Local Differential Privacy Through Communication Complexity
Matthew Joseph, Jieming Mao, Aaron Roth
Baker game and polynomial-time approximation schemes
Zdenek Dvorak
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
Maximilian Probst, Christian Wulff-Nilsen
Worst-case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity
Jacob Holm, Eva Rotenberg
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
Ray Li, Percy Liang, Stephen Mussmann
Dynamic Low-Stretch Spanning Trees in Subpolynomial Time
Shiri Chechik, Tianyi Zhang
Sandwiching random regular graphs between binomial random graphs
Pu Gao, Mikhail Isaev, Brendan McKay
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
Karolina Okrasa, Paweł Rzążewski
Improved hardness for H-colourings of G-colourable graphs
Marcin Wrochna, Stanislav Živný
The Online Submodular Cover Problem
Anupam Gupta, Roie Levin
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
Christian Wulff-Nilsen, Maximilian Probst
Online Scheduling via Learned Weights
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
Janardhan Kulkarni, Shi Li, Jakub Tarnawski, Minwei Ye
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
Yair Bartal, Nova Fandina, Seeun William Umboh
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
Christian Wulff-Nilsen, Maximilian Probst
Finding Perfect Matchings in Dense Hypergraphs
Jie Han, Peter Keevash
Lossless Prioritized Embeddings
Michael Elkin, Ofer Neiman
On the Tractability of Public Persuasion with No Externalities
Haifeng Xu
Tightening Curves on Surfaces Monotonically with Applications
Hsien-Chih Chang, Arnaud de Mesmay
List Decodable Learning via Sum of Squares
Prasad Raghavendra, Morris Yau
Navigating an Infinite Space with Unreliable Movements
Jara Uitto, Anders Martinsson
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
Joshua Brakensiek, Venkatesan Guruswami
A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
Fully Dynamic Matching: Beating 2-Approximation in $\Delta^\epsilon$ Update Time
Soheil Behnezhad, Jakub Łącki, Vahab Mirrokni
Detecting Feedback Vertex Sets of Size k in O^*(2.7^k) Time
Jason Li, Jesper Nederlof
Nearly optimal edge estimation with independent set queries
Xi Chen, Amit Levi, Erik Waingarten
A Deterministic Linear Program Solver in Current Matrix Multiplication Time
Jan van den Brand
Computational Concentration of Measure: Optimal Bounds, Reductions, and More
Omid Etesami, Saeed Mahloujifar, Mohammad Mahmoody
Flushing without Cascades
William Kuszmaul, Michael A. Bender, Rathish Das, Rob Johnson, Martin Farach-Colton
Quantifying the Burden of Exploration and the Unfairness of Free Riding
Christopher Jung, Neil Lutz, Sampath Kannan
Selling Information Through Consulting
Yiling Chen, Haifeng Xu, Shuran Zheng
A Tale of Santa Claus, Hypergraphs and Matroids
Yihao Zhang, Sami Davies, Thomas Rothvoss
Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets
Moshe Babaioff, Kira Goldner, Yannai A. Gonczarowski
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Marc Roth, Philip Wellnitz
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
Yinzhan Xu, Virginia Williams
Chasing Convex Bodies Optimally
Mark Sellke
Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs
Fedor Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
Equivalences between triangle and range query problems
Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams
Chasing Nested Convex Bodies Nearly Optimally
Mark Sellke, Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, Yuanzhi Li
Better Sample -- Random Subset Sum in $2^{0.255n}$ and its Impact on Decoding Random Linear Codes
Andre Esser, Alexander May
Efficiently list-edge coloring multigraphs asymptotically optimally
Fotis Iliopoulos, Alistair Sinclair
On Decoding Cohen-Haeupler-Schulman Tree Codes
Anand Kumar Narayanan, Matthew Weidner
An almost 2-approximation for all-pairs of shortest paths in subquadratic time
Maor Akav, Liam Roditty
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
Linear rankwidth meets stability
Sebastian Siebertz, Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Finding a Bounded-Degree Expander Inside a Dense One
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
The Power of Distributed Verifiers in Interactive Proofs
Merav Parter, Moni Naor, Eylon Yogev
A Lower Bound on Cycle-Finding in Sparse Digraphs
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
Parallel Machine Scheduling to Minimize Energy Consumption
Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar
The Communication Complexity of Optimization
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
Labelings vs. Embeddings: On Distributed Representations of Distances
Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Jakab Tardos, Slobodan Mitrović, Ashkan Norouzi-Fard, Michael Kapralov
Individual Sensitivity Preprocessing for Data Privacy
Rachel Cummings, David Durfee
Lower Bounds for Oblivious Near-Neighbor Search
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs
Patrick Morris, Hiep Han, Jie Han
A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane
Chaya Keller, Shakhar Smorodinsky
Near-Optimal Bounds for Online Caching with Machine Learned Advice
Dhruv Rohatgi
Zeros of ferromagnetic two-spin systems
Heng Guo, Jingcheng Liu, Pinyan Lu
Round Complexity of Common Randomness Generation: The Amortized Setting
Noah Golowich, Madhu Sudan
Embeddability of simplicial complexes is undecidable
Marek Filakovský, Uli Wagner, Stephan Zhechev
Ultimate greedy approximation of independent sets in subcubic graphs
Piotr Krysta, Mathieu Mari, Nan Zhi
Edge Expansion and Second Eigenvalue of Nonnegative Matrices
Jenish C. Mehta, Leonard J. Schulman
Approximation Schemes for Capacitated Clustering in Doubling Metrics
Vincent Cohen-Addad
Shorter Labeling Schemes for Planar Graphs
Marthe Bonamy, Cyril Gavoille, Michał Pilipczuk
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stephan Thomasse
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures
Ori Sberlo, Amir Shpilka
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
M. S. Ramanujan, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
Very fast construction of bounded degree spanning graphs via the semi-random graph process
Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, Michael Krivelevich
Circle Packing on Planar Graphs
Sally Dong, Yin Tat Lee, Kent Quanrud
The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model
Matthew Patitz, Daniel Hader, Aaron Koch, Michael Sharp
Linear Size Sparsifier and the Geometry of the Operator Norm Ball
Victor Reis, Thomas Rothvoss
Counting independent sets in unbalanced bipartite graphs
Sarah Cannon, Will Perkins
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
Xiaohui Bei, Xiaoming Sun, Hao Wu, Jialin Zhang, Zhijie Zhang, Wei Zi
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
Sayan Bhattacharya, Janardhan Kulkarni
A PTAS for subset TSP in minor-free graphs
Hung Le
A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
Ken-Ichi Kawarabayashi, Bingkai Lin
Efficiency of the floating body as a robust measure of dispersion
Joseph Anderson, Luis Rademacher
A Blossom Algorithm for Maximum Edge-Disjoint $T$-Paths
Satoru Iwata, Yu Yokoi
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians
Max Klimm, Philipp Warode
Extended Formulation Lower Bounds for Refuting Random CSPs
Jonah Brown-Cohen, Prasad Raghavendra
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game
William Kuszmaul
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Zhao Song, Aviad Rubinstein
The Directed Flat Wall Theorem
Archontia Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon
A face cover perspective to $\ell_1$ embeddings of planar graphs
Arnold Filtser
Coarse-Grained Complexity for Dynamic Algorithms
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
Rohan Ghuge, Viswanath Nagarajan
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, David M. Mount
Atomic Embeddability, Clustered Planarity, and Thickenability
Radoslav Fulek, Csaba D. Tóth
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup
Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External Forces
Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Mauricio Flores, Timothy Gomez, Austin Luchsinger, Rene Reyes, Robert Schweller, Tim Wylie
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Stefan Weltge
Faster Update Time for Turnstile Streaming Algorithms
Josh Alman, Huacheng Yu
Interleaved Caching with Access Graphs
Ravi Kumar, Manish Purohit, Zoya Svitkina, Erik Vee
Optimal Orthogonal Drawings in Linear Time
Walter Didimo, Giuseppe Liotta, Giacomo Ortali, Maurizio Patrignani
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai
Approximating the Distance to Monotonicity of Boolean Functions
Ramesh Krishnan Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Shortest Paths in a Hybrid Network Model
John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider
Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
Omer Gold, Keerti Choudhary
On the Learnability of Random Deep Networks
Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, Rina Panigrahy
Instance-Optimality in the Noisy Value-and Comparison-Model
Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
The Communication Complexity of Set Intersection and Multiple Equality Testing
Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang
How to aggregate top-lists: Approximation algorithms via scores and average ranks
Claire Mathieu, Simon Mauras
Fast and Space Efficient Spectral Sparsification in Dynamic Streams
Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos
Differentially Private Release of Synthetic Graphs
Marek Elias, Michael Kapralov, Janardhan Kulkarni, Yin Tat Lee, Jana Kulkarni
Locally Private k-Means Clustering
Uri Stemmer
Faster sublinear approximations of $k$-cliques for low arboricity graphs
Talya Eden, Dana Ron, C. Seshadhri
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
Guillaume Ducoffe, Laurent Viennot, Michel Habib
Even maps, the Colin de Verdière number and representations of graphs
Vojtěch Kaluža, Martin Tancer
Combinatorial Generation via Permutation Languages
Elizabeth Hartung, Hung P. Hoang, Torsten Mütze, Aaron Williams
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems(via t-Wise Agreement Testing Theorem)
Pasin Manurangsi
New $(\alpha, \beta)$ Spanners and Hop-Sets
Uri Ben-Levy, Merav Parter
Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
Aram Harrow, Annie Wei
Reconstruction under outliers for Fourier sparse functions
Xue Chen, ANINDYA DE
The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
José A. Soto, José Correa, Andrés Cristi, Boris Epstein
Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels
T-H. Hubert Chan, Zhibin Liang, Antigoni Polychroniadou, Elaine Shi
A Little Charity Guarantees Almost Envy-Freeness
Bhaskar Ray Chaudhury, Tellikepalli Kavitha, Kurt Mehlhorn, Alkmini Sgouritsa
Improved Inapproximability of Rainbow Coloring
Per Austrin, Amey Bhangale, Aditya Potukuchi
Multi-transversals for Triangles and the Tuza Conjecture
Parinya Chalermsook, Samir Khuller, Pattara Sukprasert, Sumedha Uniyal
Hyperbolic intersection graphs and (quasi)-polynomial time
Sándor Kisfaludi-Bak
Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph
Gary L. Miller, Timothy Chu, Donald Sheehy
Dominantly Truthful Multi-task Peer Prediction, with Constant Number of Tasks
Yuqing Kong
X-Ramanujan graphs
Sidhanth Mohanty, Ryan O'Donnell
Tight Bounds for the Subspace Sketch Problem with Applications
Yi Li, Ruosong Wang, David P. Woodruff
Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
Sungjin Im, Maryam Shadloo
A $4+\epsilon$ approximation for $k$-connected subgraphs
Zeev Nutov
Chasing Convex Bodies with Linear Competitive Ratio
Guru Guruganesh, Anupam Gupta, C. J. Argue, Ziye Tang
The Complexity of Contracts
Paul Duetting, Tim Roughgarden, Inbal Talgam-Cohen
Finding a latent $k-$polytope in $O^{*}\left(k \cdot \mbox{{\tt nnz(data)}}\right)$ time via Subset Smoothing
Chiranjib Bhattacharyya, Ravindran Kannan
A Lower Bound for Jumbled Indexing
Rasmus Killmann, Peyman Afshani, Ingo van Duijn, Jesper Sindahl Nielsen
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Ahmad Biniaz
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
Chris Jones, Matt McPartlon
Adaptive Shivers sort: an alternative sorting algorithm
Vincent Jugé
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
Pan Peng
How to Store a Random Walk
Emanuele Viola, Omri Weinstein, Huacheng Yu
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
Jugal Garg, Pooja Kulkarni, Rucha Kulkarni
Competitive Online Search Trees on Trees
Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman
Testing convexity of functions over finite domains
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
Competitive Analysis with a Sample and the Secretary Problem
David Naori, Haim Kaplan, Danny Raz
A Truthful Cardinal Mechanism for One-Sided Matching
Rediet Abebe, Richard Cole, Vasilis Gkatzelis, Jason Hartline
Algorithmic Price Discrimination
Rachel Cummings, Nikhil R. Devanur, Zhiyi Huang, Xiangning Wang
Regular Languages meet Prefix Sorting
Jarno Alanko, Giovanna D'Agostino, Alberto Policriti, Nicola Prezza
The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains
Erica Blum, Aggelos Kiayias, Cristopher Moore, Saad Quader, Alexander Russell
Approximately counting and sampling small witnesses using a colourful decision oracle
Holger Dell, John Lapinskas, Kitty Meeks
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
JIAQING JIANG, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, Jialin Zhang
Fast LP-based Approximations for Geometric Packing and Covering Problems
Chandra Chekuri, Sariel Har-Peled, Kent Quanrud
Locally Consistent Parsing for Text Indexing in Small Space
Or Birenzwige, Shay Golan, Ely Porat
Smoothed Algorithms for Edit Distance and Longest Common Subsequence
Mahdi Boroujeni, Masoud Seddighin, Saeed Seddighin
On the Power of Relaxed Local Decoding Algorithms
Tom Gur, Oded Lachish
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
Alessandro Chiesa, Tom Gur, Igor Shinkar
Oblivious Sketching of High-Degree Polynomial Kernels
Amir Zandieh, Thomas D. Ahle, Michael Kapralov, Jakob B. T. Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff
Vertex Ordering Problems in Directed Graph Streams
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
A New Algorithm for the Robust Semi-random Independent Set Problem
Theo McKenzie, Hermish Mehta, Luca Trevisan
On the Cover of the Rolling Stone
Adrian Dumitrescu, Csaba D. Tóth
Better Data Structures for Colored Orthogonal Range Reporting
Timothy M. Chan, Yakov Nekrich
Improved bounds for centered colorings
Michał Dębski, Stefan Felsner, Piotr Micek, Felix Schröder
Inference from Auction Price
saleck johnsen, Jason Hartline, Denis Nekipelov, Zihe Wang
Faster p-norm minimizing flows, via smoothed q-norm problems
Deeksha Adil, Sushant Sachdeva
List Decoding of Direct Sum Codes
Fernando Granha Jeronimo, Madhur Tulsiani, Vedat Levi Alev, Dylan Quintana, Shashank Srivastava
Improved Local Computation Algorithm for Set Cover via Sparsification
Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, Ali Vakilian
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
Josh Alman, Timothy M. Chan, Ryan Williams
Parallel Batch-Dynamic Graphs: Constant Round Algorithms and Lower Bounds
David Durfee, Laxman Dhulipala, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, Xiaorui Sun
Approximate Maximum Matching in Random Streams
Alireza Farhadi, MohammadTaghi Hajiaghayi, Tung Mai, Anup B. Rao, Ryan A. Rossi
Sublinear time approximation of the cost of a metric k-nearest neighbor graph
Artur Czumaj, Christian Sohler
Sample Efficient Toeplitz Covariance Estimation
Yonina Eldar, Jerry Li, Cameron Musco, Christopher Musco
Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard
Rasmus Kyng, Di Wang, Peng Zhang