| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Shi Li 0001, Bundit Laekhanukit |
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree.  |
SODA  |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Alberto Del Pia, Silvia Di Gregorio |
On the complexity of binary polynomial optimization over acyclic hypergraphs. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Joseph (Seffi) Naor, Niv Buchbinder (eds.) |
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022 |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | David G. Harris 0001 |
Deterministic algorithms for the Lovász Local Lemma: simpler, more general, and more parallel. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Dadush, László A. Végh, Giacomo Zambelli |
On finding exact solutions of linear programs in the oracle model. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Simkin, Zur Luria |
A Lower Bound for the n-queens Problem. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Alon Eden, Kira Goldner, Shuran Zheng |
Private Interdependent Valuations. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, Billy Jin |
Online Nash Social Welfare Maximization with Predictions. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Jungeblut, Laura Merker, Torsten Ueckerdt |
A Sublinear Bound on the Page Number of Upward Planar Graphs. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen, Shyamal Patel |
Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros |
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | John Kallaugher, Michael Kapralov, Eric Price 0001 |
Simulating Random Walks in Random Streams. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Kim-Manuel Klein, Janina Reuter |
Collapsing the Tower - On the Complexity of Multistage Stochastic IPs. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Kamesh Munagala, Yiheng Shen, Kangning Wang, Zhiyi Wang |
Approximate Core for Committee Selection via Multilinear Extension and Market Clearing. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Eden Chlamtác, Yury Makarychev, Ali Vakilian |
Approximating Fair Clustering with Cascaded Norm Objectives. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Joachim Gudmundsson, Sampson Wong |
Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Kent Quanrud, Manuel R. Torres |
Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Haitao Wang 0001 |
Constructing Many Faces in Arrangements of Lines and Segments. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Ganardi, Pawel Gawrychowski |
Pattern Matching on Grammar-Compressed Strings in Linear Time. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Bodwin, Michael Dinitz, Caleb Robelle |
Partially Optimal Edge Fault-Tolerant Spanners. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Sai Sandeep |
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Étienne Bamas, Marina Drygala, Andreas Maggiori |
An Improved Analysis of Greedy for Online Steiner Forest. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon |
Directed Tangle Tree-Decompositions and Applications. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Vera Traub, Rico Zenklusen |
Local Search for Weighted Tree Augmentation and Steiner Tree. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sukanya Pandey, Erik Jan van Leeuwen |
Planar Multiway Cut with Terminals on Few Faces. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Mehdi Soleimanifar, John Wright |
Testing matrix product states. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, Bettina Speckmann |
Preprocessing Imprecise Points for the Pareto Front. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiri Chechik, Tianyi Zhang 0008 |
Nearly 2-Approximate Distance Oracles in Subquadratic Time. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sally Dong, Yu Gao 0001, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Guanghao Ye |
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Joachim Gudmundsson, Martin P. Seybold |
A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Antares Chen, Jonathan Shi, Luca Trevisan |
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Mitchell Black, William Maxwell, Amir Nayyeri, Eli Winkelman |
Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Dimitrios Los, Thomas Sauerwald, John Sylvester 0001 |
Balanced Allocations: Caching and Packing, Twinning and Thinning. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Arun Jambulapati, Aaron Sidford |
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Jonah Brown-Cohen, Johan Håstad |
Optimal Inapproximability with Universal Factor Graphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Clément L. Canonne, Xi Chen 0001, Gautam Kamath 0001, Amit Levi, Erik Waingarten |
Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Gradwohl, Niklas Hahn, Martin Hoefer 0001, Rann Smorodinsky |
Algorithms for Persuasion with Limited Communication. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yanjun Han, Kirankumar Shiragur |
On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Karczmarz, Piotr Sankowski |
A Deterministic Parallel APSP Algorithm and its Applications. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pankaj K. Agarwal, Micha Sharir, Alex Steiger |
Decomposing the Complement of the Union of Cubes in Three Dimensions. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour |
Induced subgraphs of bounded treewidth and the container method. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiri Chechik, Tianyi Zhang 0008 |
Incremental Single Source Shortest Paths in Sparse Digraphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Johan Håstad |
Explicit two-deletion codes with redundancy matching the existential bound. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Roman Rabinovich 0001, Sebastian Siebertz |
Rankwidth meets stability. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Lokshtanov, Saket Saurabh 0001, Meirav Zehavi |
Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version). |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang Cai 0001, Kira Goldner, Steven Ma, Mingfei Zhao |
On Multi-Dimensional Gains from Trade Maximization. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski |
Shorter Labels for Routing in Trees. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Claire Mathieu, Rajmohan Rajaraman, Neal E. Young, Arman Yousefi |
Competitive Data-Structure Dynamization. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yiding Feng, Rad Niazadeh, Amin Saberi |
Two-stage Stochastic Matching with Application to Ride Hailing. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Santanu S. Dey, Yatharth Dubey, Marco Molinaro 0001 |
Branch-and-Bound Solves Random Binary IPs in Polytime. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Haotian Jiang |
Minimizing Convex Functions with Integral Minimizers. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Marco Molinaro 0001 |
Robust Algorithms for Online Convex Problems via Primal-Dual. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Diptarka Chakraborty, Debarati Das 0001, Robert Krauthgamer |
Approximating the Median under the Ulam Metric. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Balcer, Albert Cheu, Matthew Joseph, Jieming Mao |
Connecting Robust Shuffle Privacy and Pan-Privacy. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts |
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Bastide 0002, George Giakkoupis, Hayk Saribekyan |
Self-Stabilizing Clock Synchronization with 1-bit Messages. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Padraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn, Deryk Osthus |
Hamiltonicity of random subgraphs of the hypercube. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mehrdad Ghadiri, Richard Santiago, F. Bruce Shepherd |
Beyond Submodular Maximization via One-Sided Smoothness. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Naveen Garg 0001, Sanjeev Khanna, Amit Kumar 0001 |
Hardness of Approximation for Orienteering with Multiple Time Windows. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Isolde Adler, Noleen Köhler, Pan Peng 0001 |
On Testability of First-Order Properties in Bounded-Degree Graphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohsen Ghaffari 0001, Christoph Grunau, Václav Rozhon |
Improved Deterministic Network Decomposition. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Jatin Batra, Majid Farhadi, Prasad Tetali |
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang |
Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sarah Morell, Ina Seidel, Stefan Weltge |
Minimum-cost integer circulations in given homology classes. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nimrod Fiat, Dana Ron |
On Efficient Distance Approximation for Graph Properties. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-Yi Cai, Zhiguo Fu, Shuai Shao 0001 |
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Philip Wellnitz |
On Near-Linear-Time Algorithms for Dense Subset Sum. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Grohe, Pascal Schweitzer, Daniel Wiebking |
Deep Weisfeiler Leman. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Neeraj Kumar 0004, Daniel Lokshtanov, Saket Saurabh 0001, Subhash Suri |
A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Robinson 0002 |
Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Suprovat Ghoshal, Anand Louis |
Approximation Algorithms and Hardness for Strong Unique Games. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnold Filtser, Omrit Filtser |
Static and Streaming Data Structures for Fréchet Distance Queries. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuan Deng, Debmalya Panigrahi, Hanrui Zhang |
Online Combinatorial Auctions. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Jatin Batra |
Non-uniform Geometric Set Cover and Scheduling on Multiple Machines. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis |
Planar Reachability Under Single Vertex or Edge Failures. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Avni, Ismaël Jecker, Dorde Zikelic |
Infinite-Duration All-Pay Bidding Games. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Divesh Aggarwal, Yanlin Chen, Rajendra Kumar 0002, Zeyong Li, Noah Stephens-Davidowitz |
Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Krzysztof Nowicki 0002, Krzysztof Onak |
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Ron, Asaf Rosin |
Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Gilad Asharov, Wei-Kai Lin, Elaine Shi |
Sorting Short Keys in Circuits of Size o(n log n). |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey 0001, Frank-Olaf Schreyer |
On the Orbit Closure Containment Problem and Slice Rank of Tensors. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
Polynomial-time trace reconstruction in the smoothed complexity model. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz 0001 |
Vertex Sparsification for Edge Connectivity. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Chun-Hung Liu |
Asymptotic dimension of minor-closed families and beyond. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak |
Approximating Pathwidth for Graphs of Small Treewidth. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shi Li 0001 |
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohsen Ghaffari 0001, Bernhard Haeupler |
A Time-Optimal Randomized Parallel Algorithm for MIS. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | José Correa 0001, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, Alexandros Tsigonias-Dimitriadis |
The Secretary Problem with Independent Sampling. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf |
Tight Distributed Listing of Cliques. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yaowei Long, Seth Pettie |
Planar Distance Oracles with Better Time-Space Tradeoffs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Makis Arsenis, Odysseas Drosis, Robert Kleinberg |
Constrained-Order Prophet Inequalities. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noam Nisan |
The Demand Query Model for Bipartite Matching. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge |
Optimal Discretization is Fixed-parameter Tractable. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Viswanath Nagarajan, Lily Wang |
Online Generalized Network Design Under (Dis)Economies of Scale. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael T. Goodrich, Riko Jacob, Nodari Sitchinava |
Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Peyman Afshani |
A Lower Bound for Dynamic Fractional Cascading. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jasper C. H. Lee, Paul Valiant |
Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Itai Dinur |
Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li 0006 |
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license