Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Nathaniel Lahn, Sharath Raghvendra |
An O(n5/4) Time ∊-Approximation Algorithm for RMS Matching in a Plane. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis |
A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jiehua Chen 0001, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski 0002, Anna Zych-Pawlewicz |
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Patrick Morris 0001 |
A tight condition for triangle factors in pseudorandom graphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Arvind V. Mahankali, David P. Woodruff |
Optimal ℓ1 Column Subset Selection and a Fast PTAS for Low Rank Approximation. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | William Lochet |
A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga |
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices? |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jin-Yi Cai, Tianyu Liu 0002 |
An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Haitao Wang 0001 |
Shortest Paths Among Obstacles in the Plane Revisited. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Chaoping Xing, Chen Yuan 0003 |
Beating the probabilistic lower bound on perfect hashing. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Nicola Cotumaccio, Nicola Prezza |
On Indexing and Compressing Finite Automata. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Sebastian Forster, Gramoz Goranci, Monika Henzinger |
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Allen Liu, Renato Paes Leme, Jon Schneider |
Optimal Contextual Pricing and Extensions. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan |
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick |
On the Mysteries of MAX NAE-SAT. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Daniel M. Kane |
Robust Learning of Mixtures of Gaussians. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Nemanja Draganic, Michael Krivelevich, Rajko Nenadov |
Rolling backwards can move you forward: on embedding problems in sparse expanders. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Kristine Vitting Klinkby, Pranabendu Misra, Saket Saurabh 0001 |
Strong Connectivity Augmentation is FPT. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz |
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Sayan Bhattacharya, Fabrizio Grandoni 0001, David Wajc |
Online Edge Coloring Algorithms via the Nibble Method. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jess Banks, Sidhanth Mohanty, Prasad Raghavendra |
Local Statistics, Semidefinite Programming, and Community Detection. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Timothy M. Chan |
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Yossi Azar, Runtian Ren, Danny Vainstein |
The Min-Cost Matching with Concave Delays Problem. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Pawel Gawrychowski, Shay Mozes, Oren Weimann |
Planar Negative k-Cycle. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
Approximate Nearest Neighbors Beyond Space Partitions. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Nick Gravin, Siyao Guo, Tsz Chiu Kwok, Pinyan Lu |
Concentration bounds for almost k-wise independence with applications to non-uniform security. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Joachim Gudmundsson, Sampson Wong |
Improving the dilation of a metric graph by adding edges. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Anupam Gupta 0001, Euiwoong Lee, Jason Li 0006 |
The Connectivity Threshold for Dense Graphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Lap Chi Lau, Hong Zhou 0001 |
A Local Search Framework for Experimental Design. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Guy Blanc, Jane Lange, Li-Yang Tan |
Query strategies for priced information, revisited. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Huacheng Yu |
Tight Distributed Sketching Lower Bound for Connectivity. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Arnold Filtser, Michael Kapralov, Navid Nouri |
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Roie Levin, David Wajc |
Streaming Submodular Matching Meets the Primal-Dual Method. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Weiming Feng 0001, Thomas P. Hayes, Yitong Yin |
Distributed Metropolis Sampler with Optimal Parallelism. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein |
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Eduard Eiben, Fedor V. Fomin, Petr A. Golovach, William Lochet, Fahad Panolan, Kirill Simonov |
EPTAS for k-means Clustering of Affine Subspaces. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu 0002 |
Coresets for Clustering in Excluded-minor Graphs and Beyond. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschröder, Lars Rohwedder, Robert Weismantel |
Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Yang Cai 0001, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao |
An Efficient ∊-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani |
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu 0001 |
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Miguel Romero 0001, Marcin Wrochna, Stanislav Zivný |
Treewidth-Pliability and PTAS for Max-CSPs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Michael A. Bender, William Kuszmaul |
Randomized Cup Game Algorithms Against Strong Adversaries. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jacob D. Abernethy, Kevin A. Lai, Andre Wibisono |
Fast Convergence of Fictitious Play for Diagonal Payoff Matrices. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Shuichi Hirahara, Nobutaka Shimizu |
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Wegrzycki |
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato |
Tight Bounds for Parallel Paging and Green Paging. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Weiming Feng 0001, Heng Guo 0001, Yitong Yin, Chihao Zhang 0001 |
Rapid Mixing from Spectral Independence beyond the Boolean Domain. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Richard Peng, Santosh S. Vempala |
Solving Sparse Linear Systems Faster than Matrix Multiplication. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Andreas Björklund, Petteri Kaski |
The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Suman K. Bera 0001, Noujan Pashanasangi, C. Seshadhri 0001 |
Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari |
Strongly refuting all semi-random Boolean CSPs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Matthieu Rosenfeld |
The Growth Rate Over Trees Of Any Family Of Sets Defined By A Monadic Second Order Formula Is Semi-computable. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Kuan Cheng, Xin Li 0006 |
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Ziyun Huang, Qilong Feng, Jianxin Wang 0001, Jinhui Xu 0001 |
PTAS for Minimum Cost Multi-covering with Disks. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | James B. Orlin, László A. Végh |
Directed Shortest Paths via Approximate Cost Balancing. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Zhengfeng Ji, Zhihan Jin, Pinyan Lu |
Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jan Dreier, Peter Rossmanith |
Approximate Evaluation of First-Order Counting Queries. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Dániel Marx (eds.) |
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Sepehr Assadi, Thomas Kesselheim, Sahil Singla 0001 |
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Julia Chuzhoy, Thatchaphol Saranurak |
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Parinya Chalermsook, Bartosz Walczak |
Coloring and Maximum Weight Independent Set of Rectangles. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Ran Duan, Yong Gu, Hanlin Ren |
Approximate Distance Oracles Subject to Multiple Vertex Failures. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Michael Kapralov |
Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Fabrizio Grandoni 0001, Giuseppe F. Italiano, Aleksander Lukasiewicz, Nikos Parotsidis, Przemyslaw Uznanski |
All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Ainesh Bakshi, Pravesh K. Kothari |
List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Mahsa Derakhshan, David M. Pennock, Aleksandrs Slivkins |
Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný |
Counting Homomorphisms to K4-minor-free Graphs, modulo 2. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Maike Buchin, Anne Driemel, Dennis Rohde |
Approximating (k, ℓ-Median Clustering for Polygonal Curves. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Karthekeyan Chandrasekaran, Chandra Chekuri |
Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Ce Jin 0001, Nikhil Vyas 0001, Ryan Williams 0001 |
Fast Low-Space Algorithms for Subset Sum. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee |
On Approximability of Clustering Problems Without Candidate Centers. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Troy Lee, Miklos Santha, Shengyu Zhang 0002 |
Quantum algorithms for graph problems with cut queries. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Josh Alman, Virginia Vassilevska Williams |
A Refined Laser Method and Faster Matrix Multiplication. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Wenzheng Li, Jan Vondrák |
Estimating the Nash Social Welfare for coverage and other submodular valuations. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Michael Mitzenmacher, Saeed Seddighin |
Improved Sublinear Time Algorithm for Longest Increasing Subsequence. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta |
Competitive Allocation of a Mixed Manna. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Kent Quanrud |
Spectral Sparsification of Metrics and Kernels. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Shyam Narayanan |
Improved Algorithms for Population Recovery from the Deletion Channel. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Shyam Narayanan |
On Tolerant Distribution Testing in the Conditional Sampling Model. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Eoin Hurley, Rémi de Joannis de Verclos, Ross J. Kang |
An improved procedure for colouring graphs of bounded local density. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Atul Singh Arora, Jérémie Roland, Chrysoula Vlachou |
Analytic quantum weak coin flipping protocols with arbitrarily small bias. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Yakov Nekrich |
New Data Structures for Orthogonal Range Reporting and Range Minima Queries. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Erin Wolf Chambers, Jeff Erickson 0001, Patrick Lin 0001, Salman Parsa |
How to Morph Graphs on the Torus. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Dale Koenig, Anastasiia Tsvietkova |
Unlinking, splitting, and some other NP-hard problems in knot theory. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Alessandra Graf, David G. Harris 0001, Penny Haxell |
Algorithms for weighted independent transversals and strong colouring. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
Rapid Mixing for Colorings via Spectral Independence. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Nithin Varma, Yuichi Yoshida |
Average Sensitivity of Graph Algorithms. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Yash Kanoria, Seungki Min, Pengyu Qian |
In which matching markets does the short side enjoy an advantage? |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Zahra Jafargholi, Kasper Green Larsen, Mark Simkin 0001 |
Optimal Oblivious Priority Queues. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Nikhil Bansal 0001, Haotian Jiang, Raghu Meka, Sahil Singla 0001, Makrand Sinha |
Online Discrepancy Minimization for Stochastic Arrivals. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Monika Henzinger, Stefan Neumann 0003, Harald Räcke, Stefan Schmid 0001 |
Tight Bounds for Online Graph Partitioning. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Shiri Chechik, Gur Lifshitz |
Optimal Girth Approximation for Dense Directed Graphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Karl Bringmann, Vasileios Nakos |
A Fine-Grained Perspective on Approximating Subset Sum and Partition. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Jie Han, Xichao Shu, Guanghui Wang |
Non-linear Hamilton cycles in linear quasi-random hypergraphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin |
On Two-Handed Planar Assembly Partitioning with Connectivity Constraints. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Greg Bodwin, Michael Dinitz, Caleb Robelle |
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Alexander Kozachinskiy |
Polyhedral Value Iteration for Discounted Games and Energy Games. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Karthik C. S., Merav Parter |
Deterministic Replacement Path Covering. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
1 | Robert Cummings, Matthew Fahrbach, Animesh Fatehpuria |
A Fast Minimum Degree Algorithm and Matching Lower Bound. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|