default search action
31st SODA 2020: Salt Lake City, UT, USA
- Shuchi Chawla:
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020. SIAM 2020, ISBN 978-1-61197-599-4 - Front Matter.
- Maor Akav, Liam Roditty:
An almost 2-approximation for all-pairs of shortest paths in subquadratic time. 1-11 - Virginia Vassilevska Williams, Yinzhan Xu:
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications. 12-29 - Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams:
Equivalences between triangle and range query problems. 30-47 - Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. 48-61 - Pasin Manurangsi:
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem). 62-81 - Clément L. Canonne, Anindya De, Rocco A. Servedio:
Learning from satisfying assignments under continuous distributions. 82-101 - Ray Li, Percy Liang, Stephen Mussmann:
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree. 102-121 - Chiranjib Bhattacharyya, Ravindran Kannan:
Finding a latent k-simplex in O* (k · nnz(data)) time via Subset Smoothing. 122-140 - Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh:
Oblivious Sketching of High-Degree Polynomial Kernels. 141-160 - Prasad Raghavendra, Morris Yau:
List Decodable Learning via Sum of Squares. 161-180 - Heng Guo, Jingcheng Liu, Pinyan Lu:
Zeros of ferromagnetic 2-spin systems. 181-192 - Aram W. Harrow, Annie Y. Wei:
Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions. 193-212 - Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, Jialin Zhang:
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis. 213-229 - Daniel Wiebking:
Normalizers and permutational isomorphisms in simply-exponential time. 230-238 - Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon:
The Directed Flat Wall Theorem. 239-258 - Jan van den Brand:
A Deterministic Linear Program Solver in Current Matrix Multiplication Time. 259-278 - Rasmus Kyng, Di Wang, Peng Zhang:
Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard. 279-296 - Joshua Brakensiek, Venkatesan Guruswami:
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. 297-304 - Jonah Brown-Cohen, Prasad Raghavendra:
Extended Formulation Lower Bounds for Refuting Random CSPs. 305-324 - Yuri Faenza, Telikepalli Kavitha:
Quasi-popular Matchings, Optimality, and Extended Formulations. 325-344 - Omid Etesami, Saeed Mahloujifar, Mohammad Mahmoody:
Computational Concentration of Measure: Optimal Bounds, Reductions, and More. 345-363 - Joseph Anderson, Luis Rademacher:
Efficiency of the floating body as a robust measure of dispersion. 364-377 - Yonina C. Eldar, Jerry Li, Cameron Musco, Christopher Musco:
Sample Efficient Toeplitz Covariance Estimation. 378-397 - Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, Rina Panigrahy:
On the Learnability of Random Deep Networks. 398-410 - Timothy Chu, Gary L. Miller, Donald R. Sheehy:
Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph. 411-425 - Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. 426-445 - Marthe Bonamy, Cyril Gavoille, Michal Pilipczuk:
Shorter Labeling Schemes for Planar Graphs. 446-462 - Shiri Chechik, Tianyi Zhang:
Dynamic Low-Stretch Spanning Trees in Subpolynomial Time. 463-475 - Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak:
Coarse-Grained Complexity for Dynamic Algorithms. 476-494 - Keerti Choudhary, Omer Gold:
Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms. 495-514 - Matthew Joseph, Jieming Mao, Aaron Roth:
Exponential Separations in Local Differential Privacy. 515-527 - Rachel Cummings, David Durfee:
Individual Sensitivity Preprocessing for Data Privacy. 528-547 - Uri Stemmer:
Locally Private k-Means Clustering. 548-559 - Marek Eliás, Michael Kapralov, Janardhan Kulkarni, Yin Tat Lee:
Differentially Private Release of Synthetic Graphs. 560-578 - Amin Coja-Oghlan, Alperen Ali Ergür, Pu Gao, Samuel Hetterich, Maurice Rolvien:
The rank of sparse random matrices. 579-591 - Peyman Afshani, Ingo van Duijn, Rasmus Killmann, Jesper Sindahl Nielsen:
A Lower Bound for Jumbled Indexing. 592-606 - Or Birenzwige, Shay Golan, Ely Porat:
Locally Consistent Parsing for Text Indexing in Small Space. 607-626 - Timothy M. Chan, Yakov Nekrich:
Better Data Structures for Colored Orthogonal Range Reporting. 627-636 - Josh Alman, Timothy M. Chan, R. Ryan Williams:
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. 637-649 - Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, William Kuszmaul:
Flushing Without Cascades. 650-669 - Alan M. Frieze, Tomasz Tkocz:
A randomly weighted minimum spanning tree with a random cost constraint. 670-689 - Pu Gao, Mikhail Isaev, Brendan D. McKay:
Sandwiching random regular graphs between binomial random graphs. 690-701 - Hiêp Hàn, Jie Han, Patrick Morris:
Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs. 702-717 - Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, Michael Krivelevich:
Very fast construction of bounded-degree spanning graphs via the semi-random graph process. 718-737 - Theo McKenzie, Hermish Mehta, Luca Trevisan:
A New Algorithm for the Robust Semi-random Independent Set Problem. 738-746 - Hsien-Chih Chang, Arnaud de Mesmay:
Tightening Curves on Surfaces Monotonically with Applications. 747-766 - Marek Filakovský, Uli Wagner, Stephan Zhechev:
Embeddability of Simplicial Complexes is Undecidable. 767-785 - Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. 786-805 - Walter Didimo, Giuseppe Liotta, Giacomo Ortali, Maurizio Patrignani:
Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time. 806-825 - Ahmad Biniaz:
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios. 826-836 - Brian Axelrod, Yang P. Liu, Aaron Sidford:
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization. 837-853 - Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh:
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. 854-873 - Chris Jones, Matt McPartlon:
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere. 874-891 - Deeksha Adil, Sushant Sachdeva:
Faster p-norm minimizing flows, via smoothed q-norm problems. 892-910 - Jarno Alanko, Giovanna D'Agostino, Alberto Policriti, Nicola Prezza:
Regular Languages meet Prefix Sorting. 911-930 - Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos:
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. 931-950 - Julien Baste, Ignasi Sau, Dimitrios M. Thilikos:
A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. 951-970 - Jason Li, Jesper Nederlof:
Detecting Feedback Vertex Sets of Size k in O*(2.7k) Time. 971-989 - Ken-ichi Kawarabayashi, Bingkai Lin:
A nearly 5/3-approximation FPT Algorithm for Min-k-Cut. 990-999 - Zeev Nutov:
A 4 + ε approximation for k-connected subgraphs. 1000-1009 - Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh:
2-Approximating Feedback Vertex Set in Tournaments. 1010-1018 - Chandra Chekuri, Sariel Har-Peled, Kent Quanrud:
Fast LP-based Approximations for Geometric Packing and Covering Problems. 1019-1038 - Rohan Ghuge, Viswanath Nagarajan:
Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems. 1039-1048 - Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. 1049-1062 - Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer:
Labelings vs. Embeddings: On Distributed Representations of Distances. 1063-1075 - Noah Golowich, Madhu Sudan:
Round Complexity of Common Randomness Generation: The Amortized Setting. 1076-1095 - Moni Naor, Merav Parter, Eylon Yogev:
The Power of Distributed Verifiers in Interactive Proofs. 1096-115 - Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. 1116-1134 - Erica Blum, Aggelos Kiayias, Cristopher Moore, Saad Quader, Alexander Russell:
The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains. 1135-1154 - Chaya Keller, Shakhar Smorodinsky:
A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane. 1155-1169 - Anders Martinsson, Jara Uitto:
Navigating an Infinite Space with Unreliable Movements. 1170-1179 - Jaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, Sebastian Siebertz:
Linear rankwidth meets stability. 1180-1199 - Jenish C. Mehta, Leonard J. Schulman:
Edge Expansion and Spectral Gap of Nonnegative Matrices. 1200-1213 - Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams:
Combinatorial generation via permutation languages. 1214-1225 - Sidhanth Mohanty, Ryan O'Donnell:
X-Ramanujan graphs. 1226-1243 - Fabian Kuhn:
Faster Deterministic Distributed Coloring Through Recursive List Coloring. 1244-1259 - Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup:
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. 1260-1279 - John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider:
Shortest Paths in a Hybrid Network Model. 1280-1299 - Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, Xiaorui Sun:
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. 1300-1319 - Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Finding a Bounded-Degree Expander Inside a Dense One. 1320-1336 - Anand Kumar Narayanan, Matthew Weidner:
On Decoding Cohen-Haeupler-Schulman Tree Codes. 1337-1356 - Ori Sberlo, Amir Shpilka:
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures. 1357-1376 - Tom Gur, Oded Lachish:
On the Power of Relaxed Local Decoding Algorithms. 1377-1394 - Alessandro Chiesa, Tom Gur, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. 1395-1411 - Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani:
List Decoding of Direct Sum Codes. 1412-1425 - Marcin Wrochna, Stanislav Zivný:
Improved hardness for H-colourings of G-colourable graphs. 1426-1435 - Piotr Krysta, Mathieu Mari, Nan Zhi:
Ultimate greedy approximation of independent sets in subcubic graphs. 1436-1455 - Sarah Cannon, Will Perkins:
Counting independent sets in unbalanced bipartite graphs. 1456-1466 - Talya Eden, Dana Ron, C. Seshadhri:
Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. 1467-1478 - Per Austrin, Amey Bhangale, Aditya Potukuchi:
Improved Inapproximability of Rainbow Coloring. 1479-1495 - Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, Yuanzhi Li, Mark Sellke:
Chasing Nested Convex Bodies Nearly Optimally. 1496-1508 - Mark Sellke:
Chasing Convex Bodies Optimally. 1509-1518 - C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang:
Chasing Convex Bodies with Linear Competitive Ratio. 1519-1524 - Anupam Gupta, Roie Levin:
The Online Submodular Cover Problem. 1525-1537 - Yair Bartal, Nova Fandina, Seeun William Umboh:
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds. 1538-1557 - William Kuszmaul:
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game. 1558-1577 - Karolina Okrasa, Pawel Rzazewski:
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs. 1578-1590 - Aviad Rubinstein, Zhao Song:
Reducing approximate Longest Common Subsequence to approximate Edit Distance. 1591-1600 - Mahdi Boroujeni, Masoud Seddighin, Saeed Seddighin:
Improved Algorithms for Edit Distance and LCS: Beyond Worst Case. 1601-1620 - Sándor Kisfaludi-Bak:
Hyperbolic intersection graphs and (quasi)-polynomial time. 1621-1638 - Vincent Jugé:
Adaptive Shivers Sort: An Alternative Sorting Algorithm. 1639-1654 - Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. 1655-1674 - Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei:
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. 1675-1694 - Uri Ben-Levy, Merav Parter:
New (α, β) Spanners and Hopsets. 1695-1714 - Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang:
The Communication Complexity of Set Intersection and Multiple Equality Testing. 1715-1732 - Santosh S. Vempala, Ruosong Wang, David P. Woodruff:
The Communication Complexity of Optimization. 1733-1752 - Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos:
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples. 1753-1772 - Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, Ryan A. Rossi:
Approximate Maximum Matching in Random Streams. 1773-1785 - Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova:
Vertex Ordering Problems in Directed Graph Streams. 1786-1802 - Josh Alman, Huacheng Yu:
Faster Update Time for Turnstile Streaming Algorithms. 1803-1813 - Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos:
Fast and Space Efficient Spectral Sparsification in Dynamic Streams. 1814-1833 - Dhruv Rohatgi:
Near-Optimal Bounds for Online Caching with Machine Learned Advice. 1834-1845 - Ravi Kumar, Manish Purohit, Zoya Svitkina, Erik Vee:
Interleaved Caching with Access Graphs. 1846-1858 - Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii:
Online Scheduling via Learned Weights. 1859-1877 - Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman:
Competitive Online Search Trees on Trees. 1878-1891 - Christopher Jung, Sampath Kannan, Neil Lutz:
Quantifying the Burden of Exploration and the Unfairness of Free Riding. 1892-1904 - Guillaume Ducoffe, Michel Habib, Laurent Viennot:
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. 1905-1922 - Yutaro Yamaguchi:
A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs. 1923-1932 - Satoru Iwata, Yu Yokoi:
A Blossom Algorithm for Maximum Edge-Disjoint T-Paths. 1933-1944 - Arnold Filtser:
A face cover perspective to ℓ1 embeddings of planar graphs. 1945-1954 - Parinya Chalermsook, Samir Khuller, Pattara Sukprasert, Sumedha Uniyal:
Multi-transversals for Triangles and the Tuza's Conjecture. 1955-1974 - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions. 1975-1994 - Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten:
Approximating the Distance to Monotonicity of Boolean Functions. 1995-2009 - Xue Chen, Anindya De:
Reconstruction under outliers for Fourier-sparse functions. 2010-2029 - Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi:
Testing convexity of functions over finite domains. 2030-2045