| 2023 | "Who is Next in Line?" On the Significance of Knowing the Arrival Order in Bayesian Online Settings. Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang |
| 2023 | 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time. Yakov Nekrich, Saladi Rahul |
| 2023 | A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems. Julia Chuzhoy |
| 2023 | A Framework for Approximation Schemes on Disk Graphs. Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi |
| 2023 | A Near-Linear Time Sampler for the Ising Model with External Field. Xiaoyu Chen, Xinyuan Zhang |
| 2023 | A Nearly Tight Analysis of Greedy k-means++. Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon, Jakub Tetek |
| 2023 | A Nearly Time-Optimal Distributed Approximation of Minimum Cost Michal Dory, Mohsen Ghaffari |
| 2023 | A Nearly-Tight Analysis of Multipass Pairing Heaps. Corwin Sinnamon, Robert E. Tarjan |
| 2023 | A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs. Lawrence Li, Sushant Sachdeva |
| 2023 | A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function. Tsuyoshi Hirayama, Yuhao Liu, Kazuhisa Makino, Ke Shi, Chao Xu |
| 2023 | A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games. Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis |
| 2023 | A Sublinear-Time Quantum Algorithm for Approximating Partition Functions. Arjan Cornelissen, Yassine Hamoudi |
| 2023 | A Subquadratic Thijs van der Horst, Marc J. van Kreveld, Tim Ophelders, Bettina Speckmann |
| 2023 | A Tight Analysis of Slim Heaps and Smooth Heaps. Corwin Sinnamon, Robert E. Tarjan |
| 2023 | A half-integral Erdős-Pósa theorem for directed odd cycles. Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie |
| 2023 | A logic-based algorithmic meta-theorem for mim-width. Benjamin Bergougnoux, Jan Dreier, Lars Jaffke |
| 2023 | A simple and sharper proof of the hypergraph Moore bound. Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty |
| 2023 | A tight quasi-polynomial bound for Global Label Min-Cut. Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza |
| 2023 | Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank. Taihei Oki, Tasuku Soma |
| 2023 | Algorithmizing the Multiplicity Schwartz-Zippel Lemma. Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar |
| 2023 | Almost Consistent Systems of Linear Equations. Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Magnus Wahlström |
| 2023 | Almost Tight Bounds for Online Facility Location in the Random-Order Model. Haim Kaplan, David Naori, Danny Raz |
| 2023 | Almost Tight Error Bounds on Differentially Private Continual Counting. Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay |
| 2023 | Almost-Linear Planted Cliques Elude the Metropolis Process. Zongchen Chen, Elchanan Mossel, Ilias Zadik |
| 2023 | An Improved Approximation for Maximum Weighted Theophile Thiery, Justin Ward |
| 2023 | Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test. Dor Minzer, Kai Zheng |
| 2023 | Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency. Hung Le |
| 2023 | Approximate Graph Colouring and Crystals. Lorenzo Ciardo, Stanislav Zivný |
| 2023 | Approximate Trace Reconstruction from a Single Trace. Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
| 2023 | Approximating Knapsack and Partition via Dense Subset Sums. Mingyang Deng, Ce Jin, Xiao Mao |
| 2023 | Approximation Algorithms for Steiner Tree Augmentation Problems. R. Ravi, Weizhong Zhang, Michael Zlatin |
| 2023 | Balanced Allocations with Heterogeneous Bins: The Power of Memory. Dimitrios Los, Thomas Sauerwald, John Sylvester |
| 2023 | Beating (1 - 1/e)-Approximation for Weighted Stochastic Matching. Mahsa Derakhshan, Alireza Farhadi |
| 2023 | Beating Greedy Matching in Sublinear Time. Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi |
| 2023 | Bidder Subset Selection Problem in Auction Design. Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang |
| 2023 | Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn |
| 2023 | Breaking the 𝒪( Dominik Kempa, Tomasz Kociumaka |
| 2023 | Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. Shang-En Huang, Seth Pettie, Leqi Zhu |
| 2023 | Closing the Gap Between Directed Hopsets and Shortcut Sets. Aaron Bernstein, Nicole Wein |
| 2023 | Competitive Information Design for Pandora's Box. Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, Haifeng Xu |
| 2023 | Computing Square Colorings on Bounded-Treewidth and Planar Graphs. Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek |
| 2023 | Concentration of polynomial random matrices via Efron-Stein inequalities. Goutham Rajendran, Madhur Tulsiani |
| 2023 | Conflict-free hypergraph matchings. Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, Lyuben Lichev |
| 2023 | Constant Approximating Parameterized Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang |
| 2023 | Cubic Goldreich-Levin. Dain Kim, Anqi Li, Jonathan Tidor |
| 2023 | Curve Simplification and Clustering under Fréchet Distance. Siu-Wing Cheng, Haoqiang Huang |
| 2023 | Deterministic counting Lovász local lemma beyond linear programming. Kun He, Chunyang Wang, Yitong Yin |
| 2023 | Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu |
| 2023 | Discrepancy Minimization via Regularization. Lucas Pesenti, Adrian Vladu |
| 2023 | Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti |
| 2023 | Dynamic Algorithms for Maximum Matching Size. Soheil Behnezhad |
| 2023 | Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates. Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak |
| 2023 | Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc |
| 2023 | Economical Convex Coverings and Applications. Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
| 2023 | Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes. Anthony Leverrier, Gilles Zémor |
| 2023 | Efficient resilient functions. Peter Ivanov, Raghu Meka, Emanuele Viola |
| 2023 | Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit |
| 2023 | Equivalence Test for Read-Once Arithmetic Formulas. Nikhil Gupta, Chandan Saha, Bhargav Thankey |
| 2023 | Exact Flow Sparsification Requires Unbounded Size. Robert Krauthgamer, Ron Mosenzon |
| 2023 | Excluding Single-Crossing Matching Minors in Bipartite Graphs. Archontia C. Giannopoulou, Dimitrios M. Thilikos, Sebastian Wiederrecht |
| 2023 | Fair allocation of a multiset of indivisible items. Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy |
| 2023 | Fast Discrepancy Minimization with Hereditary Guarantees. Kasper Green Larsen |
| 2023 | Fast Distributed Brooks' Theorem. Manuela Fischer, Magnús M. Halldórsson, Yannic Maus |
| 2023 | Fast algorithms for solving the Hamilton Cycle problem with high probability. Michael Anastos |
| 2023 | Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth. Krishnendu Chatterjee, Tobias Meggendorfer, Raimundo Saona, Jakub Svoboda |
| 2023 | Faster Computation of 3-Edge-Connected Components in Digraphs. Loukas Georgiadis, Evangelos Kipouridis, Charis Papadopoulos, Nikos Parotsidis |
| 2023 | Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths. Shiri Chechik, Tianyi Zhang |
| 2023 | Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers. Shimon Kogan, Merav Parter |
| 2023 | Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. Timothy M. Chan |
| 2023 | Fixed-Parameter Tractability of Maximum Colored Path and Beyond. Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Kirill Simonov, Giannos Stamoulis |
| 2023 | Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge |
| 2023 | Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström |
| 2023 | Foundations of Transaction Fee Mechanism Design. Hao Chung, Elaine Shi |
| 2023 | From Algorithms to Connectivity and Back: Finding a Giant Component in Random Zongchen Chen, Nitya Mani |
| 2023 | Fully Dynamic Exact Edge Connectivity in Sublinear Time. Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen |
| 2023 | Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours. François Dross, Krzysztof Fleszar, Karol Wegrzycki, Anna Zych-Pawlewicz |
| 2023 | Generalized Unrelated Machine Scheduling Problem. Shichuan Deng, Jian Li, Yuval Rabani |
| 2023 | Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs. Peter Gartland, Daniel Lokshtanov |
| 2023 | Graph Classes with Few Minimal Separators. II. A Dichotomy. Peter Gartland, Daniel Lokshtanov |
| 2023 | Halving by a Thousand Cuts or Punctures. Sariel Har-Peled, Da Wei Zheng |
| 2023 | Hierarchies of Minion Tests for PCSPs through Tensors. Lorenzo Ciardo, Stanislav Zivný |
| 2023 | Higher degree sum-of-squares relaxations robust against oblivious outliers. Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer |
| 2023 | Improved Approximation for Two-Edge-Connectivity. Mohit Garg, Fabrizio Grandoni, Afrouz Jabal Ameli |
| 2023 | Improved Approximations for Unrelated Machine Scheduling. Sungjin Im, Shi Li |
| 2023 | Improved Bi-point Rounding Algorithms and a Golden Barrier for Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh |
| 2023 | Improved Bounds for Sampling Solutions of Random CNF Formulas. Kun He, Kewen Wu, Kuan Yang |
| 2023 | Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring. Peter Davies |
| 2023 | Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon |
| 2023 | Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole. Penny Haxell, Tibor Szabó |
| 2023 | Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition. Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, Sorrachai Yingchareonthawornchai |
| 2023 | Improved girth approximation in weighted undirected graphs. Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick |
| 2023 | Instability of backoff protocols with arbitrary arrival rates. Leslie Ann Goldberg, John Lapinskas |
| 2023 | Integrality Gaps for Random Integer Programs via Discrepancy. Sander Borst, Daniel Dadush, Dan Mikulincer |
| 2023 | Interactive Coding with Small Memory. Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena |
| 2023 | Interdependent Public Projects. Avi Cohen, Michal Feldman, Divyarthi Mohan, Inbal Talgam-Cohen |
| 2023 | Kernelization for Graph Packing Problems via Rainbow Matching. Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos, Sebastian Wiederrecht |
| 2023 | Learning Hierarchical Cluster Structure of Graphs in Sublinear Time. Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar |
| 2023 | Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond. Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, Václav Rozhon |
| 2023 | Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility). Niv Buchbinder, Joseph (Seffi) Naor, David Wajc |
| 2023 | Low Degree Testing over the Reals. Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida |
| 2023 | Maintaining Expander Decompositions via Sparse Cuts. Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu |
| 2023 | Map matching queries on realistic input graphs under the Fréchet distance. Joachim Gudmundsson, Martin P. Seybold, Sampson Wong |
| 2023 | Massively Parallel Computation on Embedded Planar Graphs. Jacob Holm, Jakub Tetek |
| 2023 | Maximal Chaitanya Nalam, Thatchaphol Saranurak |
| 2023 | Mean estimation when you have the source code; or, quantum Monte Carlo methods. Robin Kothari, Ryan O'Donnell |
| 2023 | Minimizing Completion Times for Stochastic Jobs via Batched Free Times. Anupam Gupta, Benjamin Moseley, Rudy Zhou |
| 2023 | Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos |
| 2023 | Moser-Tardos Algorithm: Beyond Shearer's Bound. Kun He, Qian Li, Xiaoming Sun |
| 2023 | Near-Linear Sample Complexity for Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou |
| 2023 | Near-Linear Time Approximations for Cut Problems via Fair Cuts. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak |
| 2023 | Non-Stochastic CDF Estimation Using Threshold Queries. Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg |
| 2023 | Nonlinear codes exceeding the Gilbert-Varshamov and Tsfasman-Vlăduţ-Zink bounds. Shu Liu, Tingyi Wu, Chaoping Xing |
| 2023 | On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs. Calum MacRury, Will Ma, Nathaniel Grammel |
| 2023 | On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs. Kim-Manuel Klein, Adam Polak, Lars Rohwedder |
| 2023 | On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach. Mingyang Deng, Xiao Mao, Ziqian Zhong |
| 2023 | On complex roots of the independence polynomial. Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák |
| 2023 | On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem. Mong-Jen Kao |
| 2023 | On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings. Timothy M. Chan, Sariel Har-Peled |
| 2023 | On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions. Gábor Ivanyos, Youming Qiao |
| 2023 | Online Lewis Weight Sampling. David P. Woodruff, Taisuke Yasuda |
| 2023 | Online Min-Max Paging. Ashish Chiplunkar, Monika Henzinger, Sagar Sudhir Kale, Maximilian Vötsch |
| 2023 | Online Prediction in Sub-linear Space. Binghui Peng, Fred Zhang |
| 2023 | Online Sorting and Translational Packing of Convex Polygons. Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, Linda Kleist |
| 2023 | Online and Bandit Algorithms Beyond ℓ Thomas Kesselheim, Marco Molinaro, Sahil Singla |
| 2023 | Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou |
| 2023 | Optimal Deterministic Massively Parallel Connectivity on Forests. Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto |
| 2023 | Optimal Fully Dynamic MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, Andreas Wiese |
| 2023 | Optimal Pricing Schemes for an Impatient Buyer. Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang |
| 2023 | Optimal Square Detection Over General Alphabets. Jonas Ellert, Pawel Gawrychowski, Garance Gourdel |
| 2023 | Packing cycles in planar and bounded-genus graphs. Niklas Schlomberg, Hanjo Thiele, Jens Vygen |
| 2023 | Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth. Nairen Cao, Jeremy T. Fineman |
| 2023 | Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in Kyungjin Cho, Eunjin Oh, Seunghyeok Oh |
| 2023 | Parameterized Approximation Scheme for Biclique-free Max Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, Anannya Upasana |
| 2023 | Passing the Limits of Pure Local Search for Weighted Meike Neuwohner |
| 2023 | Player-optimal Stable Regret for Bandit Learning in Matching Markets. Fang Kong, Shuai Li |
| 2023 | Polynomial formulations as a barrier for reduction-based hardness proofs. Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov |
| 2023 | Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. Christian Ikenmeyer, Igor Pak, Greta Panova |
| 2023 | Pricing Query Complexity of Revenue Maximization. Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah |
| 2023 | Private Convex Optimization in General Norms. Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian |
| 2023 | Private Query Release via the Johnson-Lindenstrauss Transform. Aleksandar Nikolov |
| 2023 | Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 Nikhil Bansal, Viswanath Nagarajan |
| 2023 | Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and Ce Jin, Jakob Nogler |
| 2023 | Quantum tomography using state-preparation unitaries. Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, Giacomo Nannicini |
| 2023 | Query Complexity of Inversion Minimization on Trees. Ivan Hu, Dieter van Melkebeek, Andrew Morgan |
| 2023 | Query Complexity of the Metric Steiner Tree Problem. Yu Chen, Sanjeev Khanna, Zihan Tan |
| 2023 | Robust Voting Rules from Algorithmic Robust Statistics. Allen Liu, Ankur Moitra |
| 2023 | Sampling Equilibria: Fast No-Regret Learning in Structured Games. Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett |
| 2023 | Secretary Problems: The Power of a Single Sample. Pranav Nuti, Jan Vondrák |
| 2023 | Sharp threshold sequence and universality for Ising perceptron models. Shuta Nakajima, Nike Sun |
| 2023 | Short Synchronizing Words for Random Automata. Guillaume Chapuy, Guillem Perarnau |
| 2023 | Shortest Cycles With Monotone Submodular Costs. Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Daniel Lokshtanov, Giannos Stamoulis |
| 2023 | Shrunk subspaces via operator Sinkhorn iteration. Cole Franks, Tasuku Soma, Michel X. Goemans |
| 2023 | Simple Mechanisms for Non-linear Agents. Yiding Feng, Jason D. Hartline, Yingkai Li |
| 2023 | Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. Michal Koucký, Michael E. Saks |
| 2023 | Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. Timothy M. Chan, Da Wei Zheng |
| 2023 | Single-Pass Streaming Algorithms for Correlation Clustering. Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan |
| 2023 | Small Shadows of Lattice Polytopes. Alexander E. Black |
| 2023 | Small subgraphs with large average degree. Oliver Janzer, Benny Sudakov, István Tomon |
| 2023 | Smaller Low-Depth Circuits for Kronecker Powers. Josh Alman, Yunfeng Guan, Ashwin Padaki |
| 2023 | Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. Marthe Bonamy, Edouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek |
| 2023 | Spatial mixing and the random-cluster dynamics on lattices. Reza Gheissari, Alistair Sinclair |
| 2023 | Spencer's theorem in nearly input-sparsity time. Vishesh Jain, Ashwin Sah, Mehtaab Sawhney |
| 2023 | Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows. Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi |
| 2023 | Streaming algorithms for the missing item finding problem. Manuel Stoeckl |
| 2023 | Streaming complexity of CSPs with randomly ordered constraints. Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy |
| 2023 | Stronger 3SUM-Indexing Lower Bounds. Eldon Chung, Kasper Green Larsen |
| 2023 | Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy. Vitaly Feldman, Audra McMillan, Kunal Talwar |
| 2023 | Subexponential mixing for partition chains on grid-like graphs. Alan M. Frieze, Wesley Pegden |
| 2023 | Sublinear-Time Algorithms for Max Cut, Max E2Lin( Pan Peng, Yuichi Yoshida |
| 2023 | Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity. Yaonan Jin, Daogao Liu, Zhao Song |
| 2023 | Superpolynomial lower bounds for decision tree learning and testing. Caleb Koch, Carmen Strassle, Li-Yang Tan |
| 2023 | Testing Convex Truncation. Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2023 | Testing and Learning Quantum Juntas Nearly Optimally. Thomas Chen, Shivam Nadimpalli, Henry Yuen |
| 2023 | The Exact Bipartite Matching Polytope Has Exponential Extension Complexity. Xinrui Jia, Ola Svensson, Weiqiang Yuan |
| 2023 | The Need for Seed (in the abstract Tile Assembly Model). Andrew Alseth, Matthew J. Patitz |
| 2023 | The Power of Clairvoyance for Multi-Level Aggregation and Set Cover with Delay. Ngoc Mai Le, Seeun William Umboh, Ningyuan Xie |
| 2023 | The Price of Stability for First Price Auction. Yaonan Jin, Pinyan Lu |
| 2023 | The complete classification for quantified equality constraints. Dmitriy Zhuk, Barnaby Martin, Michal Wrona |
| 2023 | The ℓ Yi Li, Honghao Lin, David P. Woodruff |
| 2023 | Tight Bounds for Monotone Minimal Perfect Hashing. Sepehr Assadi, Martin Farach-Colton, William Kuszmaul |
| 2023 | Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs. Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz |
| 2023 | Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness. Xin Lyu, Weihao Zhu |
| 2023 | Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models. Da Qi Chen, Lin An, Aidin Niaparast, R. Ravi, Oleksandr Rudenko |
| 2023 | Tiny Pointers. Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini |
| 2023 | Toeplitz Low-Rank Approximation with Sublinear Query Complexity. Michael Kapralov, Hannah Lawrence, Mikhail Makarov, Cameron Musco, Kshiteej Sheth |
| 2023 | Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu |
| 2023 | Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh |
| 2023 | Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality. Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, John Wright |
| 2023 | Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete. Stefan Göller, Pawel Parys |
| 2023 | Weisfeiler-Leman and Graph Spectra. Gaurav Rattan, Tim Seppelt |
| 2023 | Zigzagging through acyclic orientations of chordal graphs and hypergraphs. Jean Cardinal, Hung Phuc Hoang, Arturo Merino, Torsten Mütze |