SODA

Publications

2024

Ariel D. Procaccia, Isaac Robinson, Jamie Tucker-Foltz
School Redistricting: Wiping Unfairness Off the Map. SODA (2024)
Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA (2024)
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
Cactus Representation of Minimum Cuts: Derandomize and Speed up. SODA (2024)
Christian Konrad, Kheeran K. Naidu
An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation. SODA (2024)
Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi
Arborescences, Colorful Forests, and Popularity. SODA (2024)
David Rasmussen Lolck, Rasmus Pagh
Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy. SODA (2024)
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Dynamic Dictionary with Subconstant Wasted Bits per Key. SODA (2024)
Simina Brânzei, Davin Choo, Nicholas J. Recker
The Sharp Power Law of Local Search on Expanders. SODA (2024)
Yu Chen, Zihan Tan
On (1 + ɛ)-Approximate Flow Sparsifiers. SODA (2024)
Will Perkins, Yuzhou Wang
On the hardness of finding balanced independent sets in random bipartite graphs. SODA (2024)
Julia Gaudio, Xiaochun Niu, Ermin Wei
Exact Community Recovery in the Geometric SBM. SODA (2024)
Vasilis Livanos, Ruta Mehta
Minimization is Harder in the Prophet World. SODA (2024)
Guru Guruganesh, Aranyak Mehta, Di Wang, Kangning Wang
Prior-Independent Auctions for Heterogeneous Bidders. SODA (2024)
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
Dynamic Algorithms for Matroid Submodular Maximization. SODA (2024)
Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros
Learning Hard-Constrained Models with One Sample. SODA (2024)
Anish Hebbar, Arindam Khan, K. V. N. Sreenivas
Bin Packing under Random-Order: Breaking the Barrier of 3/2. SODA (2024)
Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations. SODA (2024)
Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, Peilin Zhong
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. SODA (2024)
Cameron Musco, Kshiteej Sheth
Sublinear Time Low-Rank Approximation of Toeplitz Matrices. SODA (2024)
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts. SODA (2024)
Itay Safran, Daniel Reichman, Paul Valiant
How Many Neurons Does it Take to Approximate the Maximum? SODA (2024)
Christopher Trevisan
Sorting and Selection in Rounds with Adversarial Comparisons. SODA (2024)
Abhishek Dhawan
Edge-Coloring Algorithms for Bounded Degree Multigraphs. SODA (2024)
Jan van den Brand, Sebastian Forster, Yasamin Nazari, Adam Polak
On Dynamic Graph Algorithms with Predictions. SODA (2024)
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
The Time Complexity of Fully Sparse Matrix Multiplication. SODA (2024)
Shiri Ron
Impossibilities for Obviously Strategy-Proof Mechanisms. SODA (2024)
Rajat De, Dominik Kempa
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data. SODA (2024)
Arun Jambulapati, Victor Reis, Kevin Tian
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory. SODA (2024)
Songsong Li, Chaoping Xing
Fast Fourier transform via automorphism groups of rational function fields. SODA (2024)
Fatima Elsheimy, Giorgos Tsimos, Charalampos Papamanthou
) Communication. SODA (2024)
Moses Charikar, Michael Kapralov, Erik Waingarten
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. SODA (2024)
Vida Dujmovic, Robert Hickingbotham, Jedrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, David R. Wood
The Grid-Minor Theorem Revisited. SODA (2024)
Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michal Pilipczuk, Adam Polak
Parameterized algorithms for block-structured integer programs with large entries. SODA (2024)
Natan Rubin
Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions. SODA (2024)
Lap Chi Lau, Kam Chuen Tung, Robert Wang
Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues. SODA (2024)
Jana Cslovjecsek, Michal Pilipczuk, Karol Wegrzycki
-approximation algorithm for maximum independent set of connected subgraphs in a planar graph. SODA (2024)
Anupam Gupta, Gregory Kehne, Roie Levin
Set Covering with Our Eyes Wide Shut. SODA (2024)
Timothy M. Chan, Pingan Cheng, Da Wei Zheng
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism. SODA (2024)
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov
Tree Containment Above Minimum Degree is FPT. SODA (2024)
Barna Saha, Christopher Ye
Faster Approximate All Pairs Shortest Paths. SODA (2024)
Adam Karczmarz
-Flow Oracles and Negative Cycle Detection in Planar Digraphs. SODA (2024)
Vishesh Jain, Huy Tuan Pham
Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings. SODA (2024)
Moses Charikar, Ruiquan Gao
Improved Approximations for Ultrametric Violation Distance. SODA (2024)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time. SODA (2024)
Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth
Oracle Efficient Online Multicalibration and Omniprediction. SODA (2024)
Eduard Eiben, Tomohiro Koana, Magnus Wahlström
Determinantal Sieving. SODA (2024)
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
-Low Rank Approximation: Solving Dense CSPs over Reals. SODA (2024)
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis
Smoothed Complexity of SWAP in Local Graph Partitioning. SODA (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Code Sparsification and its Applications. SODA (2024)
Yannai A. Gonczarowski, Nicole Immorlica, Yingkai Li, Brendan Lucier
Revenue Maximization for Buyers with Costly Participation. SODA (2024)