Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, Michael Krivelevich |
Very fast construction of bounded-degree spanning graphs via the semi-random graph process. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Deeksha Adil, Sushant Sachdeva |
Faster p-norm minimizing flows, via smoothed q-norm problems. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu |
Instance-Optimality in the Noisy Value-and Comparison-Model. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Hadley Black, Deeparnab Chakrabarty, C. Seshadhri 0001 |
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Walter Didimo, Giuseppe Liotta, Giacomo Ortali, Maurizio Patrignani |
Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Maximilian Probst Gutenberg, Christian Wulff-Nilsen |
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Moshe Babaioff, Kira Goldner, Yannai A. Gonczarowski |
Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Shuchi Chawla 0001 (eds.) |
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Michele Conforti, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Stefan Weltge |
The stable set problem in graphs with bounded genus and bounded odd cycle packing number. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Uli Wagner 0001, Emo Welzl |
Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips). |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Marthe Bonamy, Cyril Gavoille, Michal Pilipczuk |
Shorter Labeling Schemes for Planar Graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Haim Kaplan, David Naori, Danny Raz |
Competitive Analysis with a Sample and the Secretary Problem. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Amit Chakrabarti, Prantar Ghosh, Andrew McGregor 0001, Sofya Vorotnikova |
Vertex Ordering Problems in Directed Graph Streams. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Or Birenzwige, Shay Golan 0001, Ely Porat |
Locally Consistent Parsing for Text Indexing in Small Space. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich |
Reconstruction of Depth-4 Multilinear Circuits. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Yair Bartal, Nova Fandina, Seeun William Umboh |
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Alessandro Chiesa, Tom Gur, Igor Shinkar |
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Zdenek Dvorák 0001 |
Baker game and polynomial-time approximation schemes. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Santosh S. Vempala, Ruosong Wang, David P. Woodruff |
The Communication Complexity of Optimization. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Yutaro Yamaguchi 0001 |
A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Josh Alman, Timothy M. Chan, R. Ryan Williams |
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Sepehr Abbasi Zadeh, Nikhil Bansal 0001, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz 0002, Mohit Singh |
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Mahdi Boroujeni, Masoud Seddighin, Saeed Seddighin |
Improved Algorithms for Edit Distance and LCS: Beyond Worst Case. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Wiebking |
Normalizers and permutational isomorphisms in simply-exponential time. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh 0001 |
2-Approximating Feedback Vertex Set in Tournaments. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Chih-Hung Liu 0001 |
Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brakensiek, Venkatesan Guruswami |
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Michal Debski, Stefan Felsner, Piotr Micek, Felix Schröder |
Improved bounds for centered colorings. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Hung Le |
A PTAS for subset TSP in minor-free graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Max Klimm, Philipp Warode |
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos |
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Vincent Cohen-Addad |
Approximation Schemes for Capacitated Clustering in Doubling Metrics. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Holger Dell, John Lapinskas, Kitty Meeks |
Approximately counting and sampling small witnesses using a colourful decision oracle. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jan van den Brand |
A Deterministic Linear Program Solver in Current Matrix Multiplication Time. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Theo McKenzie, Hermish Mehta, Luca Trevisan |
A New Algorithm for the Robust Semi-random Independent Set Problem. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman |
Competitive Online Search Trees on Trees. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jiaqing Jiang, Xiaoming Sun 0001, Shang-Hua Teng, Bujiao Wu, Kewen Wu 0001, Jialin Zhang 0001 |
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Josh Alman, Huacheng Yu |
Faster Update Time for Turnstile Streaming Algorithms. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Yiling Chen 0001, Haifeng Xu, Shuran Zheng |
Selling Information Through Consulting. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Mark Sellke |
Chasing Convex Bodies Optimally. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Aram W. Harrow, Annie Y. Wei |
Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Peyman Afshani, Ingo van Duijn, Rasmus Killmann, Jesper Sindahl Nielsen |
A Lower Bound for Jumbled Indexing. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jarno Alanko, Giovanna D'Agostino, Alberto Policriti, Nicola Prezza |
Regular Languages meet Prefix Sorting. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Rediet Abebe, Richard Cole 0001, Vasilis Gkatzelis, Jason D. Hartline |
A Truthful Cardinal Mechanism for One-Sided Matching. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Uri Ben-Levy, Merav Parter |
New (α, β) Spanners and Hopsets. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Joseph Anderson, Luis Rademacher |
Efficiency of the floating body as a robust measure of dispersion. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Satoru Iwata 0001, Yu Yokoi |
A Blossom Algorithm for Maximum Edge-Disjoint T-Paths. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon |
The Directed Flat Wall Theorem. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Rohan Ghuge, Viswanath Nagarajan |
Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Chris Jones, Matt McPartlon |
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Xi Chen 0001, Amit Levi, Erik Waingarten |
Nearly optimal edge estimation with independent set queries. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Parinya Chalermsook, Samir Khuller, Pattara Sukprasert, Sumedha Uniyal |
Multi-transversals for Triangles and the Tuza's Conjecture. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Omid Etesami, Saeed Mahloujifar, Mohammad Mahmoody |
Computational Concentration of Measure: Optimal Bounds, Reductions, and More. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jose Balanza-Martinez, Timothy Gomez, David Caballero, Austin Luchsinger, Angel A. Cantu, Rene Reyes, Mauricio Flores, Robert T. Schweller, Tim Wylie |
Hierarchical Shape Construction and Complexity for Slidable Polyominoes under Uniform External Forces. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Sally Dong, Yin Tat Lee, Kent Quanrud |
Computing Circle Packing Representations of Planar Graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos |
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | José R. Correa, Andrés Cristi, Boris Epstein 0001, José A. Soto |
The Two-Sided Game of Googol and Sample-Based Prophet Inequalities. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Xi Chen 0001, Tim Randolph 0001, Rocco A. Servedio, Timothy Sun |
A Lower Bound on Cycle-Finding in Sparse Digraphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, William Kuszmaul |
Flushing Without Cascades. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Clément L. Canonne, Anindya De, Rocco A. Servedio |
Learning from satisfying assignments under continuous distributions. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Radoslav Fulek, Csaba D. Tóth |
Atomic Embeddability, Clustered Planarity, and Thickenability. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Emanuele Viola, Omri Weinstein, Huacheng Yu |
How to Store a Random Walk. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Maor Akav, Liam Roditty |
An almost 2-approximation for all-pairs of shortest paths in subquadratic time. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Sayan Bhattacharya, Janardhan Kulkarni |
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Mohsen Ghaffari 0001, Krzysztof Nowicki 0002, Mikkel Thorup |
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Zeev Nutov |
A 4 + ε approximation for k-connected subgraphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan |
Finding a Bounded-Degree Expander Inside a Dense One. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Ray Li, Percy Liang, Stephen Mussmann |
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Chaya Keller, Shakhar Smorodinsky |
A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Tom Gur, Oded Lachish |
On the Power of Relaxed Local Decoding Algorithms. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jonah Brown-Cohen, Prasad Raghavendra |
Extended Formulation Lower Bounds for Refuting Random CSPs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Vojtech Kaluza, Martin Tancer |
Even maps, the Colin de Verdière number and representations of graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Timothy Chu, Gary L. Miller, Donald R. Sheehy |
Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jenish C. Mehta, Leonard J. Schulman |
Edge Expansion and Spectral Gap of Nonnegative Matrices. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Lokshtanov, M. S. Ramanujan 0001, Saket Saurabh 0001, Meirav Zehavi |
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jacob Holm, Eva Rotenberg |
Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei 0001 |
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Yuqing Kong |
Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Marek Eliás 0001, Michael Kapralov, Janardhan Kulkarni, Yin Tat Lee |
Differentially Private Release of Synthetic Graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jaroslav Nesetril, Roman Rabinovich 0001, Patrice Ossona de Mendez, Sebastian Siebertz |
Linear rankwidth meets stability. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Aviad Rubinstein, Zhao Song 0002 |
Reducing approximate Longest Common Subsequence to approximate Edit Distance. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi |
Testing convexity of functions over finite domains. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Ravi Kumar 0001, Manish Purohit, Zoya Svitkina, Erik Vee |
Interleaved Caching with Access Graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Artur Czumaj, Christian Sohler |
Sublinear time approximation of the cost of a metric k-nearest neighbor graph. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, Alkmini Sgouritsa |
A Little Charity Guarantees Almost Envy-Freeness. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Fotis Iliopoulos, Alistair Sinclair |
Efficiently list-edge coloring multigraphs asymptotically optimally. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Yuri Faenza, Telikepalli Kavitha |
Quasi-popular Matchings, Optimality, and Extended Formulations. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh |
Oblivious Sketching of High-Degree Polynomial Kernels. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Chandra Chekuri, Sariel Har-Peled, Kent Quanrud |
Fast LP-based Approximations for Geometric Packing and Covering Problems. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jie Han, Peter Keevash |
Finding Perfect Matchings in Dense Hypergraphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Karolina Okrasa, Pawel Rzazewski |
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Chiranjib Bhattacharyya, Ravindran Kannan |
Finding a latent k-simplex in O* (k · nnz(data)) time via Subset Smoothing. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Alan M. Frieze, Tomasz Tkocz |
A randomly weighted minimum spanning tree with a random cost constraint. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Matthew Joseph, Jieming Mao, Aaron Roth 0001 |
Exponential Separations in Local Differential Privacy. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Amin Coja-Oghlan, Alperen Ali Ergür, Pu Gao, Samuel Hetterich, Maurice Rolvien |
The rank of sparse random matrices. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Rachel Cummings, Nikhil R. Devanur, Zhiyi Huang 0002, Xiangning Wang |
Algorithmic Price Discrimination. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Jugal Garg, Pooja Kulkarni, Rucha Kulkarni |
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
1 | Yu Cheng 0002, Ilias Diakonikolas, Rong Ge 0001 |
High-Dimensional Robust Mean Estimation in Nearly-Linear Time. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Eunjin Oh 0001 |
Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|