SODA

Keyphrases

Publications

2023

Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
Improved girth approximation in weighted undirected graphs. SODA (2023)
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
Fully Dynamic Exact Edge Connectivity in Sublinear Time. SODA (2023)
Kasper Green Larsen
Fast Discrepancy Minimization with Hereditary Guarantees. SODA (2023)
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming complexity of CSPs with randomly ordered constraints. SODA (2023)
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, Sorrachai Yingchareonthawornchai
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition. SODA (2023)
Vishesh Jain, Ashwin Sah, Mehtaab Sawhney
Spencer's theorem in nearly input-sparsity time. SODA (2023)
Ashish Chiplunkar, Monika Henzinger, Sagar Sudhir Kale, Maximilian Vötsch
Online Min-Max Paging. SODA (2023)
Yi Li, Honghao Lin, David P. Woodruff
-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. SODA (2023)
Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge
Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. SODA (2023)
Shimon Kogan, Merav Parter
Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers. SODA (2023)
Thomas Kesselheim, Marco Molinaro, Sahil Singla
Norms. SODA (2023)
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida
Low Degree Testing over the Reals. SODA (2023)
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn
-Median. SODA (2023)
Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang
-SETCOVER is W[2]-hard. SODA (2023)
Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit
) over all Finite Fields. SODA (2023)
Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, Linda Kleist
Online Sorting and Translational Packing of Convex Polygons. SODA (2023)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar
Algorithmizing the Multiplicity Schwartz-Zippel Lemma. SODA (2023)
Hao Chung, Elaine Shi
Foundations of Transaction Fee Mechanism Design. SODA (2023)
Reza Gheissari, Alistair Sinclair
Spatial mixing and the random-cluster dynamics on lattices. SODA (2023)
Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza
A tight quasi-polynomial bound for Global Label Min-Cut. SODA (2023)
Dor Minzer, Kai Zheng
Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test. SODA (2023)
Xin Lyu, Weihao Zhu
Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness. SODA (2023)
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
A logic-based algorithmic meta-theorem for mim-width. SODA (2023)
Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, Lyuben Lichev
Conflict-free hypergraph matchings. SODA (2023)
Krishnendu Chatterjee, Tobias Meggendorfer, Raimundo Saona, Jakub Svoboda
Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth. SODA (2023)
Allen Liu, Ankur Moitra
Robust Voting Rules from Algorithmic Robust Statistics. SODA (2023)
Lorenzo Ciardo, Stanislav Zivný
Approximate Graph Colouring and Crystals. SODA (2023)
Sunil Arya, Guilherme Dias da Fonseca, David M. Mount
Economical Convex Coverings and Applications. SODA (2023)
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Kirill Simonov, Giannos Stamoulis
Fixed-Parameter Tractability of Maximum Colored Path and Beyond. SODA (2023)
Xiaoyu Chen, Xinyuan Zhang
A Near-Linear Time Sampler for the Ising Model with External Field. SODA (2023)
Shuta Nakajima, Nike Sun
Sharp threshold sequence and universality for Ising perceptron models. SODA (2023)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
A Framework for Approximation Schemes on Disk Graphs. SODA (2023)
Pan Peng, Yuichi Yoshida
), and Unique Label Cover on Expanders. SODA (2023)
Penny Haxell, Tibor Szabó
Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole. SODA (2023)
Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang
Optimal Pricing Schemes for an Impatient Buyer. SODA (2023)
Zongchen Chen, Nitya Mani
-SAT. SODA (2023)
Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie
A half-integral Erdős-Pósa theorem for directed odd cycles. SODA (2023)
Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett
Sampling Equilibria: Fast No-Regret Learning in Structured Games. SODA (2023)
Timothy M. Chan, Da Wei Zheng
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. SODA (2023)
Thomas Chen, Shivam Nadimpalli, Henry Yuen
Testing and Learning Quantum Juntas Nearly Optimally. SODA (2023)
Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian
Private Convex Optimization in General Norms. SODA (2023)
Kun He, Kewen Wu, Kuan Yang
Improved Bounds for Sampling Solutions of Random CNF Formulas. SODA (2023)
Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek
Computing Square Colorings on Bounded-Treewidth and Planar Graphs. SODA (2023)
Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
Optimal Deterministic Massively Parallel Connectivity on Forests. SODA (2023)
Gábor Ivanyos, Youming Qiao
On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions. SODA (2023)
Theophile Thiery, Justin Ward
-Set Packing. SODA (2023)
Chaitanya Nalam, Thatchaphol Saranurak
-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction. SODA (2023)
Pranav Nuti, Jan Vondrák
Secretary Problems: The Power of a Single Sample. SODA (2023)
Shu Liu, Tingyi Wu, Chaoping Xing
Nonlinear codes exceeding the Gilbert-Varshamov and Tsfasman-Vlăduţ-Zink bounds. SODA (2023)
Lawrence Li, Sushant Sachdeva
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs. SODA (2023)