Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Parinya Chalermsook, Manoj Gupta 0002, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, Sorrachai Yingchareonthawornchai |
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Xin Lyu 0003, Weihao Zhu |
Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Shimon Kogan, Merav Parter |
Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | 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 |
DBLP DOI BibTeX RDF |
|
1 | 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 |
DBLP DOI BibTeX RDF |
|
1 | Akanksha Agrawal 0001, Dániel Marx, Daniel Neuen, Jasper Slusallek |
Computing Square Colorings on Bounded-Treewidth and Planar Graphs. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto |
Optimal Deterministic Massively Parallel Connectivity on Forests. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Dor Minzer, Kai Zheng |
Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Benjamin Bergougnoux, Jan Dreier, Lars Jaffke |
A logic-based algorithmic meta-theorem for mim-width. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Chaitanya Nalam, Thatchaphol Saranurak |
Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen |
Fully Dynamic Exact Edge Connectivity in Sublinear Time. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian |
Private Convex Optimization in General Norms. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Kasper Green Larsen |
Fast Discrepancy Minimization with Hereditary Guarantees. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Hao Chung, Elaine Shi |
Foundations of Transaction Fee Mechanism Design. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Timothy M. Chan, Da Wei Zheng |
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Chen, Shivam Nadimpalli, Henry Yuen |
Testing and Learning Quantum Juntas Nearly Optimally. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Yi Li 0002, Honghao Lin, David P. Woodruff |
The ℓp-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Ashish Chiplunkar, Monika Henzinger, Sagar Sudhir Kale, Maximilian Vötsch |
Online Min-Max Paging. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie |
A half-integral Erdős-Pósa theorem for directed odd cycles. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar 0001, Ashutosh Shankar |
Algorithmizing the Multiplicity Schwartz-Zippel Lemma. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta 0001, Linda Kleist |
Online Sorting and Translational Packing of Convex Polygons. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang |
Optimal Pricing Schemes for an Impatient Buyer. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Zongchen Chen, Nitya Mani |
From Algorithms to Connectivity and Back: Finding a Giant Component in Random k-SAT. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Beaglehole, Max Hopkins, Daniel Kane 0001, Sihan Liu, Shachar Lovett |
Sampling Equilibria: Fast No-Regret Learning in Structured Games. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Reza Gheissari, Alistair Sinclair |
Spatial mixing and the random-cluster dynamics on lattices. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick |
Improved girth approximation in weighted undirected graphs. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Pan Peng 0001, Yuichi Yoshida |
Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Vishesh Jain, Ashwin Sah, Mehtaab Sawhney |
Spencer's theorem in nearly input-sparsity time. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang |
Constant Approximating Parameterized k-SETCOVER is W[2]-hard. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Shuta Nakajima, Nike Sun |
Sharp threshold sequence and universality for Ising perceptron models. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Lokshtanov, Fahad Panolan, Saket Saurabh 0001, Jie Xue 0003, Meirav Zehavi |
A Framework for Approximation Schemes on Disk Graphs. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | 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. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Raghuvansh R. Saxena, Noah Singer, Madhu Sudan 0001, Santhoshini Velusamy |
Streaming complexity of CSPs with randomly ordered constraints. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Kirill Simonov, Giannos Stamoulis |
Fixed-Parameter Tractability of Maximum Colored Path and Beyond. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Vincent Cohen-Addad, Fabrizio Grandoni 0001, Euiwoong Lee, Chris Schwiegelshohn |
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Kesselheim, Marco Molinaro 0001, Sahil Singla 0001 |
Online and Bandit Algorithms Beyond ℓp Norms. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Allen Liu, Ankur Moitra |
Robust Voting Rules from Algorithmic Robust Statistics. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
Economical Convex Coverings and Applications. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Xiaoyu Chen, Xinyuan Zhang |
A Near-Linear Time Sampler for the Ising Model with External Field. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Penny Haxell, Tibor Szabó |
Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Kun He 0011, Kewen Wu 0001, Kuan Yang |
Improved Bounds for Sampling Solutions of Random CNF Formulas. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Theophile Thiery, Justin Ward |
An Improved Approximation for Maximum Weighted k-Set Packing. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Gábor Ivanyos, Youming Qiao |
On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Niklas Schlomberg, Hanjo Thiele, Jens Vygen |
Packing cycles in planar and bounded-genus graphs. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Manuel Stoeckl |
Streaming algorithms for the missing item finding problem. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, Haifeng Xu |
Competitive Information Design for Pandora's Box. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh |
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Yiding Feng, Jason D. Hartline, Yingkai Li |
Simple Mechanisms for Non-linear Agents. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Caleb Koch, Carmen Strassle, Li-Yang Tan |
Superpolynomial lower bounds for decision tree learning and testing. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Haim Kaplan, David Naori, Danny Raz |
Almost Tight Bounds for Online Facility Location in the Random-Order Model. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Ruoxu Cen, William He, Jason Li 0006, Debmalya Panigrahi |
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Stefan Göller, Pawel Parys |
Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Thijs van der Horst, Marc J. van Kreveld, Tim Ophelders, Bettina Speckmann |
A Subquadratic nε-approximation for the Continuous Fréchet Distance. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | 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. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Eldon Chung, Kasper Green Larsen |
Stronger 3SUM-Indexing Lower Bounds. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Niv Buchbinder, Joseph (Seffi) Naor, David Wajc |
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility). |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc |
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Yu Chen 0039, Sanjeev Khanna, Zihan Tan |
Query Complexity of the Metric Steiner Tree Problem. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | David P. Woodruff, Taisuke Yasuda 0002 |
Online Lewis Weight Sampling. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Yaonan Jin, Daogao Liu, Zhao Song 0002 |
Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Ivan Hu, Dieter van Melkebeek, Andrew Morgan |
Query Complexity of Inversion Minimization on Trees. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon, Jakub Tetek |
A Nearly Tight Analysis of Greedy k-means++. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Sander Borst, Daniel Dadush, Dan Mikulincer |
Integrality Gaps for Random Integer Programs via Discrepancy. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak |
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Mong-Jen Kao |
On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Kim-Manuel Klein, Adam Polak 0001, Lars Rohwedder |
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh |
Improved Bi-point Rounding Algorithms and a Golden Barrier for k-Median. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Lijie Chen 0001, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song 0002, Huacheng Yu |
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Sepehr Assadi, Martin Farach-Colton, William Kuszmaul |
Tight Bounds for Monotone Minimal Perfect Hashing. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Mohit Garg 0003, Fabrizio Grandoni 0001, Afrouz Jabal Ameli |
Improved Approximation for Two-Edge-Connectivity. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Tsuyoshi Hirayama, Yuhao Liu 0003, Kazuhisa Makino, Ke Shi, Chao Xu 0002 |
A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang |
"Who is Next in Line?" On the Significance of Knowing the Arrival Order in Bayesian Online Settings. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan |
Single-Pass Streaming Algorithms for Correlation Clustering. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Alexander E. Black |
Small Shadows of Lattice Polytopes. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Justin Y. Chen, Badih Ghazi, Ravi Kumar 0001, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu |
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Peter Gartland, Daniel Lokshtanov |
Graph Classes with Few Minimal Separators. II. A Dichotomy. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Dimitrios Los, Thomas Sauerwald, John Sylvester 0001 |
Balanced Allocations with Heterogeneous Bins: The Power of Memory. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Meike Neuwohner |
Passing the Limits of Pure Local Search for Weighted k-Set Packing. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Christian Ikenmeyer, Igor Pak, Greta Panova |
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Zongchen Chen, Elchanan Mossel, Ilias Zadik |
Almost-Linear Planted Cliques Elude the Metropolis Process. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Mahsa Derakhshan, Alireza Farhadi 0001 |
Beating (1 - 1/e)-Approximation for Weighted Stochastic Matching. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Goutham Rajendran, Madhur Tulsiani |
Concentration of polynomial random matrices via Efron-Stein inequalities. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Vitaly Feldman, Audra McMillan, Kunal Talwar |
Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Aaron Bernstein, Nicole Wein |
Closing the Gap Between Directed Hopsets and Shortcut Sets. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Sariel Har-Peled, Da Wei Zheng |
Halving by a Thousand Cuts or Punctures. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Shichuan Deng, Jian Li 0015, Yuval Rabani |
Generalized Unrelated Machine Scheduling Problem. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Kun He 0011, Chunyang Wang, Yitong Yin |
Deterministic counting Lovász local lemma beyond linear programming. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Corwin Sinnamon, Robert E. Tarjan |
A Nearly-Tight Analysis of Multipass Pairing Heaps. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou |
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Gaurav Rattan, Tim Seppelt |
Weisfeiler-Leman and Graph Spectra. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Soheil Behnezhad |
Dynamic Algorithms for Maximum Matching Size. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos |
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | 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. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Da Qi Chen, Lin An, Aidin Niaparast, R. Ravi 0001, Oleksandr Rudenko |
Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Fang Kong 0002, Shuai Li 0010 |
Player-optimal Stable Regret for Bandit Learning in Matching Markets. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Guillaume Chapuy, Guillem Perarnau |
Short Synchronizing Words for Random Automata. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Ferenc Bencs, Péter Csikvári, Piyush Srivastava 0001, Jan Vondrák |
On complex roots of the independence polynomial. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy |
Fair allocation of a multiset of indivisible items. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Magnus Wahlström |
Almost Consistent Systems of Linear Equations. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|
1 | Anthony Leverrier, Gilles Zémor |
Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes. |
SODA |
2023 |
DBLP DOI BibTeX RDF |
|