SODA20 Accepted Papers | SIAM
 

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.

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