default search action
34th SODA 2023: Florence, Italy
- Nikhil Bansal, Viswanath Nagarajan:
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023. SIAM 2023, ISBN 978-1-61197-755-4 - Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak:
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates. 1-47 - Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg
, Zihang Wu:
Maintaining Expander Decompositions via Sparse Cuts. 48-69 - Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup
Fully Dynamic Exact Edge Connectivity in Sublinear Time. 70-86 - Shiri Chechik, Tianyi Zhang:
Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths. 87-99 - Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc:
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. 100-128 - Soheil Behnezhad:
Dynamic Algorithms for Maximum Matching Size. 129-162 - Aaron Bernstein, Nicole Wein:
Closing the Gap Between Directed Hopsets and Shortcut Sets. 163-182 - Chaitanya Nalam, Thatchaphol Saranurak:
Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction. 183-211 - Shimon Kogan, Merav Parter:
Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers. 212-239 - Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak:
Near-Linear Time Approximations for Cut Problems via Fair Cuts. 240-275 - Kasper Green Larsen:
Fast Discrepancy Minimization with Hereditary Guarantees. 276-289 - 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. 290-303 - Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy
Fair allocation of a multiset of indivisible items. 304-331 - Yaonan Jin, Pinyan Lu:
The Price of Stability for First Price Auction. 332-352 - Bolin Ding, Yiding Feng
Competitive Information Design for Pandora's Box. 353-381 - Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang:
Optimal Pricing Schemes for an Impatient Buyer. 382-398 - Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah:
Pricing Query Complexity of Revenue Maximization. 399-415 - Avi Cohen, Michal Feldman, Divyarthi Mohan, Inbal Talgam-Cohen:
Interdependent Public Projects. 416-443 - Eldon Chung
Stronger 3SUM-Indexing Lower Bounds. 444-455 - Sepehr Assadi, Martin Farach-Colton, William Kuszmaul:
Tight Bounds for Monotone Minimal Perfect Hashing. 456-476 - Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini:
Tiny Pointers. 477-508 - Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition. 509-534 - Corwin Sinnamon, Robert E. Tarjan:
A Nearly-Tight Analysis of Multipass Pairing Heaps. 535-548 - Corwin Sinnamon, Robert E. Tarjan:
A Tight Analysis of Slim Heaps and Smooth Heaps. 549-567 - Lorenzo Ciardo, Stanislav Zivný:
Hierarchies of Minion Tests for PCSPs through Tensors. 568-580 - Guillaume Chapuy, Guillem Perarnau:
Short Synchronizing Words for Random Automata. 581-604 - Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Approximate Trace Reconstruction from a Single Trace. 605-637 - Shuta Nakajima, Nike Sun:
Sharp threshold sequence and universality for Ising perceptron models. 638-674 - Ferenc Bencs, Péter Csikvári, Piyush Srivastava
On complex roots of the independence polynomial. 675-699 - Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit:
Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time O(n log n) over all Finite Fields. 700-737 - Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida:
Low Degree Testing over the Reals. 738-792 - Manuel Stoeckl:
Streaming algorithms for the missing item finding problem. 793-818 - Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Single-Pass Streaming Algorithms for Correlation Clustering. 819-849 - Yi Li, Honghao Lin, David P. Woodruff:
The ℓp-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. 850-877 - Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu:
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. 878-924 - Michael Kapralov
Learning Hierarchical Cluster Structure of Graphs in Sublinear Time. 925-939 - Vincent Cohen-Addad, Fabrizio Grandoni
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. 940-986 - Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh:
Improved Bi-point Rounding Algorithms and a Golden Barrier for k-Median. 987-1011 - Christoph Grunau
A Nearly Tight Analysis of Greedy k-means++. 1012-1070 - Mong-Jen Kao:
On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem. 1071-1089 - Meike Neuwohner
Passing the Limits of Pure Local Search for Weighted k-Set Packing. 1090-1137 - Theophile Thiery, Justin Ward:
An Improved Approximation for Maximum Weighted k-Set Packing. 1138-1162 - Thomas Chen, Shivam Nadimpalli, Henry Yuen:
Testing and Learning Quantum Juntas Nearly Optimally. 1163-1185 - Robin Kothari, Ryan O'Donnell:
Mean estimation when you have the source code; or, quantum Monte Carlo methods. 1186-1215 - Anthony Leverrier, Gilles Zémor:
Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes. 1216-1244 - Arjan Cornelissen, Yassine Hamoudi
A Sublinear-Time Quantum Algorithm for Approximating Partition Functions. 1245-1264 - Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, Giacomo Nannicini:
Quantum tomography using state-preparation unitaries. 1265-1318 - Yeongwoo Hwang, Joe Neeman, Ojas Parekh
Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality. 1319-1384 - Sariel Har-Peled
Halving by a Thousand Cuts or Punctures. 1385-1397 - Timothy M. Chan, Sariel Har-Peled
On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings. 1398-1413 - Siu-Wing Cheng, Haoqiang Huang
Curve Simplification and Clustering under Fréchet Distance. 1414-1432 - François Dross, Krzysztof Fleszar
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours. 1433-1463 - Joachim Gudmundsson, Martin P. Seybold
Map matching queries on realistic input graphs under the Fréchet distance. 1464-1492 - Timothy M. Chan, Da Wei Zheng
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. 1493-1511 - Fang Kong, Shuai Li:
Player-optimal Stable Regret for Bandit Learning in Matching Markets. 1512-1522 - Haim Kaplan, David Naori, Danny Raz:
Almost Tight Bounds for Online Facility Location in the Random-Order Model. 1523-1544 - Ashish Chiplunkar, Monika Henzinger, Sagar Sudhir Kale
Online Min-Max Paging. 1545-1565 - Thomas Kesselheim, Marco Molinaro, Sahil Singla:
Online and Bandit Algorithms Beyond ℓp Norms. 1566-1593 - Ngoc Mai Le, Seeun William Umboh
The Power of Clairvoyance for Multi-Level Aggregation and Set Cover with Delay. 1594-1610 - Binghui Peng, Fred Zhang:
Online Prediction in Sub-linear Space. 1611-1634 - Xinrui Jia, Ola Svensson, Weiqiang Yuan:
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity. 1635-1654 - Cole Franks, Tasuku Soma
Shrunk subspaces via operator Sinkhorn iteration. 1655-1668 - Alexander E. Black:
Small Shadows of Lattice Polytopes. 1669-1679 - Tsuyoshi Hirayama, Yuhao Liu, Kazuhisa Makino, Ke Shi, Chao Xu:
A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function. 1680-1691 - Sander Borst, Daniel Dadush, Dan Mikulincer:
Integrality Gaps for Random Integer Programs via Discrepancy. 1692-1733 - Lucas Pesenti
Discrepancy Minimization via Regularization. 1734-1758 - Thijs van der Horst
A Subquadratic nε-approximation for the Continuous Fréchet Distance. 1759-1776 - Timothy M. Chan:
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. 1777-1805 - Anders Aamand, Mikkel Abrahamsen
Online Sorting and Translational Packing of Convex Polygons. 1806-1833 - Sunil Arya, Guilherme Dias da Fonseca, David M. Mount
Economical Convex Coverings and Applications. 1834-1861 - Yakov Nekrich, Saladi Rahul:
4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time. 1862-1876 - Hung Le:
Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency. 1877-1904 - Anupam Gupta, Benjamin Moseley, Rudy Zhou:
Minimizing Completion Times for Stochastic Jobs via Batched Free Times. 1905-1930 - Mahsa Derakhshan, Alireza Farhadi:
Beating (1 - 1/e)-Approximation for Weighted Stochastic Matching. 1931-1961 - Caleb Koch, Carmen Strassle, Li-Yang Tan:
Superpolynomial lower bounds for decision tree learning and testing. 1962-1994 - Calum MacRury, Will Ma, Nathaniel Grammel:
On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs. 1995-2014 - Pranav Nuti, Jan Vondrák:
Secretary Problems: The Power of a Single Sample. 2015-2029 - Niv Buchbinder, Joseph (Seffi) Naor, David Wajc:
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility). 2030-2068 - Niklas Schlomberg, Hanjo Thiele, Jens Vygen:
Packing cycles in planar and bounded-genus graphs. 2069-2086 - Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek:
Computing Square Colorings on Bounded-Treewidth and Planar Graphs. 2087-2110 - Archontia C. Giannopoulou, Dimitrios M. Thilikos, Sebastian Wiederrecht
Excluding Single-Crossing Matching Minors in Bipartite Graphs. 2111-2121 - Julia Chuzhoy:
A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems. 2122-2213 - Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen
Shortest Cycles With Monotone Submodular Costs. 2214-2227 - Daniel Lokshtanov, Fahad Panolan
A Framework for Approximation Schemes on Disk Graphs. 2228-2241 - Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick:
Improved girth approximation in weighted undirected graphs. 2242-2255 - Lorenzo Ciardo, Stanislav Zivný:
Approximate Graph Colouring and Crystals. 2256-2267 - Gaurav Rattan
Weisfeiler-Leman and Graph Spectra. 2268-2285 - Michael Anastos:
Fast algorithms for solving the Hamilton Cycle problem with high probability. 2286-2323 - Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty:
A simple and sharper proof of the hypergraph Moore bound. 2324-2344 - Oliver Janzer, Benny Sudakov, István Tomon:
Small subgraphs with large average degree. 2345-2353 - Robert Krauthgamer, Ron Mosenzon:
Exact Flow Sparsification Requires Unbounded Size. 2354-2367 - Mohit Garg, Fabrizio Grandoni
Improved Approximation for Two-Edge-Connectivity. 2368-2410 - Da Qi Chen, Lin An, Aidin Niaparast, R. Ravi, Oleksandr Rudenko:
Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models. 2411-2428 - R. Ravi, Weizhong Zhang, Michael Zlatin:
Approximation Algorithms for Steiner Tree Augmentation Problems. 2429-2448 - Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi:
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows. 2449-2488 - Loukas Georgiadis, Evangelos Kipouridis, Charis Papadopoulos
Faster Computation of 3-Edge-Connected Components in Digraphs. 2489-2531 - Mohsen Ghaffari, Christoph Grunau
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. 2532-2566 - Manuela Fischer, Magnús M. Halldórsson, Yannic Maus:
Fast Distributed Brooks' Theorem. 2567-2588 - Alkida Balliu
Optimal Deterministic Massively Parallel Connectivity on Forests. 2589-2631 - Alkida Balliu
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. 2632-2676 - MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, Andreas Wiese:
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries. 2677-2727 - Lawrence Li, Sushant Sachdeva:
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs. 2728-2745 - Dmitriy Zhuk, Barnaby Martin, Michal Wrona:
The complete classification for quantified equality constraints. 2746-2760 - Dor Minzer, Kai Zheng:
Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test. 2761-2776 - Stefan Göller, Pawel Parys
Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete. 2777-2815 - Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar:
Algorithmizing the Multiplicity Schwartz-Zippel Lemma. 2816-2835 - Ivan Hu, Dieter van Melkebeek, Andrew Morgan:
Query Complexity of Inversion Minimization on Trees. 2836-2866 - Peter Ivanov, Raghu Meka, Emanuele Viola:
Efficient resilient functions. 2867-2874 - Penny Haxell, Tibor Szabó:
Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole. 2875-2897 - Shichuan Deng
Generalized Unrelated Machine Scheduling Problem. 2898-2916 - Sungjin Im, Shi Li:
Improved Approximations for Unrelated Machine Scheduling. 2917-2946 - Kim-Manuel Klein, Adam Polak
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs. 2947-2960 - Mingyang Deng, Ce Jin, Xiao Mao:
Approximating Knapsack and Partition via Dense Subset Sums. 2961-2979 - Mingyang Deng, Xiao Mao, Ziqian Zhong:
On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach. 2980-2990 - Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, Lyuben Lichev:
Conflict-free hypergraph matchings. 2991-3005 - Marthe Bonamy, Edouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek:
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. 3006-3028 - Jean Cardinal, Hung Phuc Hoang, Arturo Merino, Torsten Mütze:
Zigzagging through acyclic orientations of chordal graphs and hypergraphs. 3029-3042 - Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie:
A half-integral Erdős-Pósa theorem for directed odd cycles. 3043-3062 - Peter Gartland, Daniel Lokshtanov:
Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs. 3063-3097 - Peter Gartland, Daniel Lokshtanov:
Graph Classes with Few Minimal Separators. II. A Dichotomy. 3098-3178 - Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Magnus Wahlström:
Almost Consistent Systems of Linear Equations. 3179-3217 - Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. 3218-3228 - 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. 3229-3244 - Tatiana Belova
Polynomial formulations as a barrier for reduction-based hardness proofs. 3245-3281 - Benjamin Bergougnoux, Jan Dreier, Lars Jaffke:
A logic-based algorithmic meta-theorem for mim-width. 3282-3304 - Bingkai Lin
Constant Approximating Parameterized k-SETCOVER is W[2]-hard. 3305-3316 - Alan M. Frieze, Wesley Pegden
Subexponential mixing for partition chains on grid-like graphs. 3317-3329 - Kun He, Kewen Wu, Kuan Yang:
Improved Bounds for Sampling Solutions of Random CNF Formulas. 3330-3361 - Kun He, Qian Li, Xiaoming Sun
Moser-Tardos Algorithm: Beyond Shearer's Bound. 3362-3387 - Kun He, Chunyang Wang
Deterministic counting Lovász local lemma beyond linear programming. 3388-3425 - Leslie Ann Goldberg, John Lapinskas
Instability of backoff protocols with arbitrary arrival rates. 3426-3436 - Zongchen Chen, Nitya Mani:
From Algorithms to Connectivity and Back: Finding a Giant Component in Random k-SAT. 3437-3470 - Allen Liu, Ankur Moitra:
Robust Voting Rules from Algorithmic Robust Statistics. 3471-3512 - Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer
Higher degree sum-of-squares relaxations robust against oblivious outliers. 3513-3550 - Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg:
Non-Stochastic CDF Estimation Using Threshold Queries. 3551-3572 - Christian Ikenmeyer, Igor Pak, Greta Panova:
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. 3573-3586 - Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena:
Interactive Coding with Small Memory. 3587-3613 - Goutham Rajendran, Madhur Tulsiani:
Concentration of polynomial random matrices via Efron-Stein inequalities. 3614-3653 - Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos, Sebastian Wiederrecht
Kernelization for Graph Packing Problems via Rainbow Matching. 3654-3663 - Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz:
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs. 3664-3683 - Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos:
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. 3684-3699 - Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen
Fixed-Parameter Tractability of Maximum Colored Path and Beyond. 3700-3712 - Pallavi Jain, Lawqueen Kanesh, Fahad Panolan
Parameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max Coverage. 3713-3733 - Kyungjin Cho, Eunjin Oh, Seunghyeok Oh:
Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in k2 and Linear in n. 3734-3758 - Tomer Ezra
"Who is Next in Line?" On the Significance of Knowing the Arrival Order in Bayesian Online Settings. 3759-3776 - Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis:
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games. 3777-3787 - Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang:
Bidder Subset Selection Problem in Auction Design. 3788-3801 - Yiding Feng
Simple Mechanisms for Non-linear Agents. 3802-3816 - Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett:
Sampling Equilibria: Fast No-Regret Learning in Structured Games. 3817-3855 - Hao Chung, Elaine Shi:
Foundations of Transaction Fee Mechanism Design. 3856-3899 - Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Beating Greedy Matching in Sublinear Time. 3900-3945 - Vishesh Jain, Ashwin Sah, Mehtaab Sawhney:
Spencer's theorem in nearly input-sparsity time. 3946-3958 - Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Near-Linear Sample Complexity for Lp Polynomial Regression. 3959-4025 - Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. 4026-4049 - Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Testing Convex Truncation. 4050-4082 - Raghuvansh R. Saxena, Noah Singer
Streaming complexity of CSPs with randomly ordered constraints. 4083-4103 - Shu Liu, Tingyi Wu, Chaoping Xing:
Nonlinear codes exceeding the Gilbert-Varshamov and Tsfasman-Vlăduţ-Zink bounds. 4104-4114 - Gábor Ivanyos, Youming Qiao:
On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions. 4115-4126 - Michael Kapralov
Toeplitz Low-Rank Approximation with Sublinear Query Complexity. 4127-4158 - Josh Alman, Yunfeng Guan, Ashwin Padaki:
Smaller Low-Depth Circuits for Kronecker Powers. 4159-4187 - Taihei Oki, Tasuku Soma
Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank. 4188-4204 - Nikhil Gupta, Chandan Saha, Bhargav Thankey:
Equivalence Test for Read-Once Arithmetic Formulas. 4205-4272 - Peter Davies:
Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring. 4273-4295 - Michal Dory, Mohsen Ghaffari:
A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph. 4296-4334 - Shang-En Huang, Seth Pettie, Leqi Zhu:
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. 4335-4353 - Nairen Cao, Jeremy T. Fineman:
Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth. 4354-4372 - Jacob Holm, Jakub Tetek:
Massively Parallel Computation on Embedded Planar Graphs. 4373-4408 - Salwa Faour, Mohsen Ghaffari, Christoph Grunau
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond. 4409-4447 - Dimitrios Los, Thomas Sauerwald, John Sylvester
Balanced Allocations with Heterogeneous Bins: The Power of Memory. 4448-4477 - Xiaoyu Chen, Xinyuan Zhang:
A Near-Linear Time Sampler for the Ising Model with External Field. 4478-4503 - Zongchen Chen, Elchanan Mossel, Ilias Zadik:
Almost-Linear Planted Cliques Elude the Metropolis Process. 4504-4539 - Andrew Alseth, Matthew J. Patitz
The Need for Seed (in the abstract Tile Assembly Model). 4540-4589 - Krishnendu Chatterjee, Tobias Meggendorfer, Raimundo Saona
Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth. 4590-4605 - Reza Gheissari, Alistair Sinclair:
Spatial mixing and the random-cluster dynamics on lattices. 4606-4621 - David P. Woodruff, Taisuke Yasuda
Online Lewis Weight Sampling. 4622-4666 - Yaonan Jin, Daogao Liu, Zhao Song:
Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity. 4667-4767 - Karl Bringmann, Michael Kapralov
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. 4768-4845 - Dain Kim
Cubic Goldreich-Levin. 4846-4892 - Yu Chen, Sanjeev Khanna, Zihan Tan:
Query Complexity of the Metric Steiner Tree Problem. 4893-4935 - Pan Peng, Yuichi Yoshida:
Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders. 4936-4965 - Vitaly Feldman, Audra McMillan, Kunal Talwar:
Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy. 4966-4981 - Aleksandar Nikolov:
Private Query Release via the Johnson-Lindenstrauss Transform. 4982-5002 - Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay:
Almost Tight Error Bounds on Differentially Private Continual Counting. 5003-5039 - Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu:
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. 5040-5067 - Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian:
Private Convex Optimization in General Norms. 5068-5089 - Ce Jin, Jakob Nogler
Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching. 5090-5121 - Dominik Kempa
Breaking the 𝒪(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees. 5122-5202 - Michal Koucký
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. 5203-5219 - Jonas Ellert, Pawel Gawrychowski, Garance Gourdel:
Optimal Square Detection Over General Alphabets. 5220-5242 - Xin Lyu, Weihao Zhu:
Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness. 5243-5281
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-15 20:33 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: