default search action
31st SODA 2020: Salt Lake City, UT, USA
- Shuchi Chawla:
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020. SIAM 2020, ISBN 978-1-61197-599-4 - Front Matter.
- Maor Akav, Liam Roditty:
An almost 2-approximation for all-pairs of shortest paths in subquadratic time. 1-11 - Virginia Vassilevska Williams, Yinzhan Xu:
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications. 12-29 - Lech Duraj, Krzysztof Kleiner, Adam Polak
, Virginia Vassilevska Williams:
Equivalences between triangle and range query problems. 30-47 - Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. 48-61 - Pasin Manurangsi:
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem). 62-81 - Clément L. Canonne, Anindya De, Rocco A. Servedio:
Learning from satisfying assignments under continuous distributions. 82-101 - Ray Li, Percy Liang, Stephen Mussmann:
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree. 102-121 - Chiranjib Bhattacharyya, Ravindran Kannan:
Finding a latent k-simplex in O* (k · nnz(data)) time via Subset Smoothing. 122-140 - Thomas D. Ahle, Michael Kapralov
Oblivious Sketching of High-Degree Polynomial Kernels. 141-160 - Prasad Raghavendra, Morris Yau:
List Decodable Learning via Sum of Squares. 161-180 - Heng Guo, Jingcheng Liu, Pinyan Lu:
Zeros of ferromagnetic 2-spin systems. 181-192 - Aram W. Harrow
Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions. 193-212 - Jiaqing Jiang, Xiaoming Sun
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis. 213-229 - Daniel Wiebking:
Normalizers and permutational isomorphisms in simply-exponential time. 230-238 - Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon:
The Directed Flat Wall Theorem. 239-258 - Jan van den Brand
A Deterministic Linear Program Solver in Current Matrix Multiplication Time. 259-278 - Rasmus Kyng, Di Wang, Peng Zhang:
Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard. 279-296 - Joshua Brakensiek, Venkatesan Guruswami:
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. 297-304 - Jonah Brown-Cohen, Prasad Raghavendra:
Extended Formulation Lower Bounds for Refuting Random CSPs. 305-324 - Yuri Faenza, Telikepalli Kavitha:
Quasi-popular Matchings, Optimality, and Extended Formulations. 325-344 - Omid Etesami, Saeed Mahloujifar, Mohammad Mahmoody:
Computational Concentration of Measure: Optimal Bounds, Reductions, and More. 345-363 - Joseph Anderson, Luis Rademacher
Efficiency of the floating body as a robust measure of dispersion. 364-377 - Yonina C. Eldar, Jerry Li, Cameron Musco, Christopher Musco:
Sample Efficient Toeplitz Covariance Estimation. 378-397 - Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, Rina Panigrahy:
On the Learnability of Random Deep Networks. 398-410 - Timothy Chu, Gary L. Miller, Donald R. Sheehy:
Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph. 411-425 - Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. 426-445 - Marthe Bonamy, Cyril Gavoille, Michal Pilipczuk:
Shorter Labeling Schemes for Planar Graphs. 446-462 - Shiri Chechik, Tianyi Zhang:
Dynamic Low-Stretch Spanning Trees in Subpolynomial Time. 463-475 - Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
Coarse-Grained Complexity for Dynamic Algorithms. 476-494 - Keerti Choudhary
Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms. 495-514 - Matthew Joseph, Jieming Mao, Aaron Roth:
Exponential Separations in Local Differential Privacy. 515-527 - Rachel Cummings, David Durfee:
Individual Sensitivity Preprocessing for Data Privacy. 528-547 - Uri Stemmer:
Locally Private k-Means Clustering. 548-559 - Marek Eliás, Michael Kapralov
Differentially Private Release of Synthetic Graphs. 560-578 - Amin Coja-Oghlan, Alperen Ali Ergür, Pu Gao, Samuel Hetterich, Maurice Rolvien:
The rank of sparse random matrices. 579-591 - Peyman Afshani, Ingo van Duijn, Rasmus Killmann, Jesper Sindahl Nielsen:
A Lower Bound for Jumbled Indexing. 592-606 - Or Birenzwige, Shay Golan
Locally Consistent Parsing for Text Indexing in Small Space. 607-626 - Timothy M. Chan, Yakov Nekrich
Better Data Structures for Colored Orthogonal Range Reporting. 627-636 - Josh Alman, Timothy M. Chan, R. Ryan Williams:
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. 637-649 - Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, William Kuszmaul:
Flushing Without Cascades. 650-669 - Alan M. Frieze, Tomasz Tkocz:
A randomly weighted minimum spanning tree with a random cost constraint. 670-689 - Pu Gao, Mikhail Isaev, Brendan D. McKay:
Sandwiching random regular graphs between binomial random graphs. 690-701 - Hiêp Hàn, Jie Han, Patrick Morris:
Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs. 702-717 - Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, Michael Krivelevich:
Very fast construction of bounded-degree spanning graphs via the semi-random graph process. 718-737 - Theo McKenzie, Hermish Mehta, Luca Trevisan:
A New Algorithm for the Robust Semi-random Independent Set Problem. 738-746 - Hsien-Chih Chang, Arnaud de Mesmay:
Tightening Curves on Surfaces Monotonically with Applications. 747-766 - Marek Filakovský
Embeddability of Simplicial Complexes is Undecidable. 767-785 - Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, David M. Mount
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. 786-805 - Walter Didimo, Giuseppe Liotta, Giacomo Ortali, Maurizio Patrignani:
Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time. 806-825 - Ahmad Biniaz:
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios. 826-836 - Brian Axelrod, Yang P. Liu, Aaron Sidford:
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization. 837-853 - Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh:
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. 854-873 - Chris Jones, Matt McPartlon:
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere. 874-891 - Deeksha Adil, Sushant Sachdeva:
Faster p-norm minimizing flows, via smoothed q-norm problems. 892-910 - Jarno Alanko
Regular Languages meet Prefix Sorting. 911-930 - Petr A. Golovach, Giannos Stamoulis
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. 931-950 - Julien Baste
A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. 951-970 - Jason Li, Jesper Nederlof:
Detecting Feedback Vertex Sets of Size k in O*(2.7k) Time. 971-989 - Ken-ichi Kawarabayashi, Bingkai Lin
A nearly 5/3-approximation FPT Algorithm for Min-k-Cut. 990-999 - Zeev Nutov:
A 4 + ε approximation for k-connected subgraphs. 1000-1009 - Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan
2-Approximating Feedback Vertex Set in Tournaments. 1010-1018 - Chandra Chekuri, Sariel Har-Peled
Fast LP-based Approximations for Geometric Packing and Covering Problems. 1019-1038 - Rohan Ghuge, Viswanath Nagarajan:
Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems. 1039-1048 - Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. 1049-1062 - Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer:
Labelings vs. Embeddings: On Distributed Representations of Distances. 1063-1075 - Noah Golowich, Madhu Sudan:
Round Complexity of Common Randomness Generation: The Amortized Setting. 1076-1095 - Moni Naor, Merav Parter, Eylon Yogev:
The Power of Distributed Verifiers in Interactive Proofs. 1096-115 - Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. 1116-1134 - Erica Blum
The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains. 1135-1154 - Chaya Keller
A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane. 1155-1169 - Anders Martinsson, Jara Uitto:
Navigating an Infinite Space with Unreliable Movements. 1170-1179 - Jaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez
Linear rankwidth meets stability. 1180-1199 - Jenish C. Mehta, Leonard J. Schulman
Edge Expansion and Spectral Gap of Nonnegative Matrices. 1200-1213 - Elizabeth Hartung
Combinatorial generation via permutation languages. 1214-1225 - Sidhanth Mohanty, Ryan O'Donnell:
X-Ramanujan graphs. 1226-1243 - Fabian Kuhn:
Faster Deterministic Distributed Coloring Through Recursive List Coloring. 1244-1259 - Mohsen Ghaffari, Krzysztof Nowicki
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. 1260-1279 - John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider:
Shortest Paths in a Hybrid Network Model. 1280-1299 - Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, Xiaorui Sun:
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. 1300-1319 - Luca Becchetti
Finding a Bounded-Degree Expander Inside a Dense One. 1320-1336 - Anand Kumar Narayanan, Matthew Weidner:
On Decoding Cohen-Haeupler-Schulman Tree Codes. 1337-1356 - Ori Sberlo, Amir Shpilka
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures. 1357-1376 - Tom Gur
On the Power of Relaxed Local Decoding Algorithms. 1377-1394 - Alessandro Chiesa, Tom Gur
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. 1395-1411 - Vedat Levi Alev
List Decoding of Direct Sum Codes. 1412-1425 - Marcin Wrochna, Stanislav Zivný:
Improved hardness for H-colourings of G-colourable graphs. 1426-1435 - Piotr Krysta, Mathieu Mari, Nan Zhi:
Ultimate greedy approximation of independent sets in subcubic graphs. 1436-1455 - Sarah Cannon, Will Perkins:
Counting independent sets in unbalanced bipartite graphs. 1456-1466 - Talya Eden, Dana Ron, C. Seshadhri:
Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. 1467-1478 - Per Austrin, Amey Bhangale, Aditya Potukuchi:
Improved Inapproximability of Rainbow Coloring. 1479-1495 - Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, Yuanzhi Li, Mark Sellke:
Chasing Nested Convex Bodies Nearly Optimally. 1496-1508 - Mark Sellke
Chasing Convex Bodies Optimally. 1509-1518 - C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang:
Chasing Convex Bodies with Linear Competitive Ratio. 1519-1524 - Anupam Gupta, Roie Levin:
The Online Submodular Cover Problem. 1525-1537 - Yair Bartal, Nova Fandina, Seeun William Umboh
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds. 1538-1557 - William Kuszmaul:
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game. 1558-1577 - Karolina Okrasa
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs. 1578-1590 - Aviad Rubinstein, Zhao Song:
Reducing approximate Longest Common Subsequence to approximate Edit Distance. 1591-1600 - Mahdi Boroujeni, Masoud Seddighin, Saeed Seddighin:
Improved Algorithms for Edit Distance and LCS: Beyond Worst Case. 1601-1620 - Sándor Kisfaludi-Bak
Hyperbolic intersection graphs and (quasi)-polynomial time. 1621-1638 - Vincent Jugé:
Adaptive Shivers Sort: An Alternative Sorting Algorithm. 1639-1654 - Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. 1655-1674 - Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei:
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. 1675-1694 - Uri Ben-Levy, Merav Parter:
New (α, β) Spanners and Hopsets. 1695-1714 - Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang
The Communication Complexity of Set Intersection and Multiple Equality Testing. 1715-1732 - Santosh S. Vempala, Ruosong Wang, David P. Woodruff:
The Communication Complexity of Optimization. 1733-1752 - Michael Kapralov
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples. 1753-1772 - Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, Ryan A. Rossi:
Approximate Maximum Matching in Random Streams. 1773-1785 - Amit Chakrabarti, Prantar Ghosh
Vertex Ordering Problems in Directed Graph Streams. 1786-1802 - Josh Alman, Huacheng Yu:
Faster Update Time for Turnstile Streaming Algorithms. 1803-1813 - Michael Kapralov
Fast and Space Efficient Spectral Sparsification in Dynamic Streams. 1814-1833 - Dhruv Rohatgi:
Near-Optimal Bounds for Online Caching with Machine Learned Advice. 1834-1845 - Ravi Kumar, Manish Purohit, Zoya Svitkina, Erik Vee:
Interleaved Caching with Access Graphs. 1846-1858 - Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii:
Online Scheduling via Learned Weights. 1859-1877 - Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman:
Competitive Online Search Trees on Trees. 1878-1891 - Christopher Jung, Sampath Kannan, Neil Lutz:
Quantifying the Burden of Exploration and the Unfairness of Free Riding. 1892-1904 - Guillaume Ducoffe, Michel Habib, Laurent Viennot:
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. 1905-1922 - Yutaro Yamaguchi:
A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs. 1923-1932 - Satoru Iwata, Yu Yokoi:
A Blossom Algorithm for Maximum Edge-Disjoint T-Paths. 1933-1944 - Arnold Filtser:
A face cover perspective to ℓ1 embeddings of planar graphs. 1945-1954 - Parinya Chalermsook, Samir Khuller, Pattara Sukprasert
Multi-transversals for Triangles and the Tuza's Conjecture. 1955-1974 - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions. 1975-1994 - Ramesh Krishnan S. Pallavoor
Approximating the Distance to Monotonicity of Boolean Functions. 1995-2009 - Xue Chen, Anindya De:
Reconstruction under outliers for Fourier-sparse functions. 2010-2029 - Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi:
Testing convexity of functions over finite domains. 2030-2045 - Sebastian Forster
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. 2046-2065 - José R. Correa, Andrés Cristi
The Two-Sided Game of Googol and Sample-Based Prophet Inequalities. 2066-2081 - Haim Kaplan, David Naori, Danny Raz:
Competitive Analysis with a Sample and the Secretary Problem. 2082-2095 - Rediet Abebe, Richard Cole, Vasilis Gkatzelis, Jason D. Hartline:
A Truthful Cardinal Mechanism for One-Sided Matching. 2096-2113 - Xiaohui Bei
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol. 2114-2123 - Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu:
Instance-Optimality in the Noisy Value-and Comparison-Model. 2124-2143 - Vishwas Bhargava
Reconstruction of Depth-4 Multilinear Circuits. 2144-2160 - Marc Roth
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory. 2161-2180 - Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi:
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. 2181-2200 - Holger Dell, John Lapinskas
Approximately counting and sampling small witnesses using a colourful decision oracle. 2201-2211 - Michal Debski, Stefan Felsner, Piotr Micek, Felix Schröder
Improved bounds for centered colorings. 2212-2226 - Zdenek Dvorák:
Baker game and polynomial-time approximation schemes. 2227-2240 - Vincent Cohen-Addad:
Approximation Schemes for Capacitated Clustering in Doubling Metrics. 2241-2259 - Maria Chudnovsky, Marcin Pilipczuk
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. 2260-2278 - Hung Le:
A PTAS for subset TSP in minor-free graphs. 2279-2298 - Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi:
Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs. 2299-2318 - Fotis Iliopoulos, Alistair Sinclair:
Efficiently list-edge coloring multigraphs asymptotically optimally. 2319-2336 - Victor Reis, Thomas Rothvoss:
Linear Size Sparsifier and the Geometry of the Operator Norm Ball. 2337-2348 - T.-H. Hubert Chan, Zhibin Liang, Antigoni Polychroniadou, Elaine Shi:
Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels. 2349-2365 - Jie Han, Peter Keevash:
Finding Perfect Matchings in Dense Hypergraphs. 2366-2377 - Jacob Holm, Eva Rotenberg
Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity. 2378-2397 - Yuqing Kong:
Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks. 2398-2411 - Yiling Chen, Haifeng Xu, Shuran Zheng:
Selling Information Through Consulting. 2412-2431 - Rachel Cummings, Nikhil R. Devanur, Zhiyi Huang, Xiangning Wang:
Algorithmic Price Discrimination. 2432-2451 - Moshe Babaioff, Kira Goldner
Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets. 2452-2471 - Jason D. Hartline, Aleck C. Johnsen, Denis Nekipelov, Zihe Wang:
Inference from Auction Prices. 2472-2491 - Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni:
Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time. 2492-2508 - Sayan Bhattacharya, Janardhan Kulkarni:
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs. 2509-2521 - Maximilian Probst Gutenberg
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler. 2522-2541 - Maximilian Probst Gutenberg
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary. 2542-2561 - Maximilian Probst Gutenberg
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds. 2562-2574 - Adrian Dumitrescu, Csaba D. Tóth:
On the Cover of the Rolling Stone. 2575-2586 - Tamal K. Dey, Tao Hou, Sayan Mandal:
Computing Minimal Persistent Cycles: Polynomial and Hard Cases. 2587-2606 - Daniel Hader, Aaron Koch, Matthew J. Patitz
The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model. 2607-2624 - 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. 2625-2641 - Vojtech Kaluza
Even maps, the Colin de Verdière number and representations of graphs. 2642-2657 - Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, Alkmini Sgouritsa:
A Little Charity Guarantees Almost Envy-Freeness. 2658-2672 - Jugal Garg, Pooja Kulkarni, Rucha Kulkarni:
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. 2673-2687 - Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen:
The Complexity of Contracts. 2688-2707 - Haifeng Xu:
On the Tractability of Public Persuasion with No Externalities. 2708-2727 - Max Klimm, Philipp Warode
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians. 2728-2747 - Sami Davies, Thomas Rothvoss, Yihao Zhang:
A Tale of Santa Claus, Hypergraphs and Matroids. 2748-2757 - Antonios Antoniadis, Naveen Garg, Gunjan Kumar, Nikhil Kumar:
Parallel Machine Scheduling to Minimize Energy Consumption. 2758-2769 - Janardhan Kulkarni, Shi Li, Jakub Tarnawski, Minwei Ye:
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints. 2770-2789 - Sungjin Im, Maryam Shadloo:
Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution. 2790-2809 - Claire Mathieu, Simon Mauras:
How to aggregate Top-lists: Approximation algorithms via scores and average ranks. 2810-2822 - Uli Wagner, Emo Welzl:
Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips). 2823-2841 - Chih-Hung Liu:
Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions. 2842-2859 - Sally Dong, Yin Tat Lee, Kent Quanrud:
Computing Circle Packing Representations of Planar Graphs. 2860-2875 - Radoslav Fulek
Atomic Embeddability, Clustered Planarity, and Thickenability. 2876-2895 - 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. 2896-2915 - Xi Chen, Amit Levi
Nearly optimal edge estimation with independent set queries. 2916-2935 - Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. 2936-2952 - Pan Peng:
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs. 2953-2972 - Artur Czumaj, Christian Sohler
Sublinear time approximation of the cost of a metric k-nearest neighbor graph. 2973-2992 - Christoph Grunau
Improved Local Computation Algorithm for Set Cover via Sparsification. 2993-3011
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 2024-11-26 20:32 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: