Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Vishwas Bhargava, Markus Bläser, Gorav Jindal, Anurag Pandey 0001 |
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sophie Spirkl, Maria Chudnovsky, Mingxian Zhong |
Four-coloring P6-free graphs. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Kuan Cheng, Bernhard Haeupler, Xin Li 0006, Amirbehshad Shahrasbi, Ke Wu 0001 |
Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Amir Nayyeri, Benjamin Raichel |
Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Greg Bodwin |
On the Structure of Unique Shortest Paths in Graphs. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma |
List Decoding with Double Samplers. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Itai Ashlagi, Amin Saberi, Ali Shameli |
Assignment Mechanisms under Distributional Constraints. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Elchanan Mossel, Jiaming Xu |
Seeded Graph Matching via Large Neighborhood Statistics. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Fahad Panolan, Saket Saurabh 0001, Meirav Zehavi |
Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | William Kuszmaul |
Efficiently Approximating Edit Distance Between Pseudorandom Strings. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Anupam Gupta 0001, Euiwoong Lee, Jason Li 0006, Pasin Manurangsi, Michal Wlodarczyk 0001 |
Losing Treewidth by Separating Subsets. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Niv Buchbinder, Anupam Gupta 0001, Marco Molinaro 0001, Joseph (Seffi) Naor |
k-Servers with a Smile: Online Algorithms via Projections. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Karim A. Adiprasito, Imre Bárány, Nabil H. Mustafa |
Theorems of Carathéodory, Helly, and Tverberg without dimension. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Robert Krauthgamer, James R. Lee, Havana Rika |
Flow-Cut Gaps and Face Covers in Planar Graphs. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Eli Fox-Epstein, Philip N. Klein, Aaron Schild |
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke 0002 |
Towards Instance-Optimal Private Query Release. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Jin-Yi Cai, Tianyu Liu 0002, Pinyan Lu |
Approximability of the Six-vertex Model. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Yeow Meng Chee, Duc Tu Dao, Han Mao Kiah, San Ling, Hengjia Wei |
Binary Robust Positioning Patterns with Low Redundancy and Efficient Locating Algorithms. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Aaron Bernstein, Sebastian Forster, Monika Henzinger |
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Gregory Z. Gutin, Magnus Wahlström, Meirav Zehavi |
On r-Simple k-Path and Related Problems Parameterized by k/r. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Max Klimm, Philipp Warode |
Computing all Wardrop Equilibria parametrized by the Flow Demand. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Rocco A. Servedio, Li-Yang Tan |
Pseudorandomness for read-k DNF formulas. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Yuichi Yoshida |
Cheeger Inequalities for Submodular Transformations. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna |
Stochastic Submodular Cover with Limited Adaptivity. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | MohammadTaghi Hajiaghayi, Saeed Seddighin, Xiaorui Sun |
Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Heng Guo 0001, Chao Liao, Pinyan Lu, Chihao Zhang 0001 |
Zeros of Holant problems: locations and algorithms. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Matthew Fahrbach, Vahab S. Mirrokni, Morteza Zadimoghaddam |
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer |
Polynomial Planar Directed Grid Theorem. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Wei-Kai Lin, Elaine Shi, Tiancheng Xie |
Can We Overcome the n log n Barrier for Oblivious Sorting? |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Hendrik Fichtenberger, Pan Peng 0001, Christian Sohler |
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Tasuku Soma, Yuichi Yoshida |
Spectral Sparsification of Hypergraphs. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Yang P. Liu, Sushant Sachdeva, Zejun Yu |
Short Cycles via Low-Diameter Decompositions. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Ran Duan, Haoqing He, Tianyi Zhang 0008 |
Dynamic Edge Coloring with Improved Approximation. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Jie Xue 0003 |
Colored range closest-pair problem under general distance functions. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Matti Karppa, Petteri Kaski |
Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Matthew Jenssen, Peter Keevash, Will Perkins 0001 |
Algorithms for #BIS-hard problems on expander graphs. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | |
Front Matter. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Timothy M. Chan (eds.) |
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Niv Buchbinder, Moran Feldman, Mohit Garg 0003 |
Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Akanksha Agrawal 0001, Pranabendu Misra, Saket Saurabh 0001, Meirav Zehavi |
Interval Vertex Deletion Admits a Polynomial Kernel. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Anupam Gupta 0001, Ravishankar Krishnaswamy, Amit Kumar 0001, Debmalya Panigrahi |
Elastic Caching. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sayan Bhattacharya, Janardhan Kulkarni |
Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan |
XOR Codes and Sparse Learning Parity with Noise. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Mohsen Ghaffari 0001 |
Distributed Maximal Independent Set using Small Messages. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Gianfranco Bilardi, Lorenzo De Stefani |
The I/O complexity of Toom-Cook integer multiplication. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Antonios Antoniadis 0001, Krzysztof Fleszar 0001, Ruben Hoeksma, Kevin Schewior |
A PTAS for Euclidean TSP with Hyperplane Neighborhoods. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva |
Iterative Refinement for ℓp-norm Regression. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Adrian Dumitrescu, Ritankar Mandal |
New Lower Bounds for the Number of Pseudoline Arrangements. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Tamal K. Dey |
Computing Height Persistence and Homology Generators in R3 Efficiently. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Mrinal Kumar 0001, Ramprasad Saptharishi, Anamay Tengse |
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Jie Han 0002, Yoshiharu Kohayakawa, Marcelo Tadeu Sales, Henrique Stagni |
Extremal and probabilistic results for order types. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Pavel Veselý 0001, Marek Chrobak, Lukasz Jez, Jirí Sgall |
A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, Elaine Shi |
Foundations of Differentially Oblivious Algorithms. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin |
Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh |
Hierarchical Clustering better than Average-Linkage. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Rico Zenklusen |
A 1.5-Approximation for Path TSP. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Rebecca Hoberg, Thomas Rothvoss |
A Fourier-Analytic Approach for the Discrepancy of Random Set Systems. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta 0001, Yin Tat Lee |
A Nearly-Linear Bound for Chasing Nested Convex Bodies. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Busto, William S. Evans, David G. Kirkpatrick |
Minimizing Interference Potential Among Moving Entities. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Marco Molinaro 0001 |
Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen |
The threshold for SDP-refutation of random regular NAE-3SAT. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Xue Chen 0001 |
Derandomized Balanced Allocation. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Raphaël Clifford, Tomasz Kociumaka, Ely Porat |
The streaming k-mismatch problem. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka |
Exact Distance Oracles for Planar Graphs with Failing Vertices. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Kevin Buchin, Tim Ophelders, Bettina Speckmann |
SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Shunhua Jiang, Kasper Green Larsen |
A Faster External Memory Priority Queue with DecreaseKeys. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Michael Kapralov, Ameya Velingker, Amir Zandieh |
Dimension-independent Sparse Fourier Transform. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Alexander Wei 0001 |
Optimal Las Vegas Approximate Near Neighbors in ℓp. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, Martijn Struijs |
Approximating (k, ℓ)-center clustering for curves. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta |
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Charles Carlson 0002, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan |
Optimal Lower Bounds for Sketching Graph Cuts. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Nathaniel Harms |
Testing Halfspaces over Rotation-Invariant Distributions. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford |
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Ulrich Bauer, Abhishek Rathod |
Hardness of Approximation for Morse Matching. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Vida Dujmovic, Fabrizio Frati, Daniel Gonçalves 0001, Pat Morin, Günter Rote |
Every Collinear Set in a Planar Graph Is Free. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, Xingyu Zhang |
Popular Matchings and Limits to Tractability. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Georgios Amanatidis, Pieter Kleer |
Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Ilias Diakonikolas, Weihao Kong, Alistair Stewart |
Efficient Algorithms and Lower Bounds for Robust Linear Regression. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | MohammadHossein Bateni, Alireza Farhadi 0001, MohammadTaghi Hajiaghayi |
Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | David G. Harris 0001 |
Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Ruosong Wang, David P. Woodruff |
Tight Bounds for ℓp Oblivious Subspace Embeddings. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Yuan Deng, Debmalya Panigrahi |
Multi-unit Supply-monotone Auctions with Bayesian Valuations. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Xiaorui Sun |
Approximating LCS in Linear Time: Beating the √n Barrier. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Merav Parter, Eylon Yogev |
Distributed Algorithms Made Secure: A Graph Theoretic Approach. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee |
Metrical task systems on trees via mirror descent and unfair gluing. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Shuchi Chawla 0001, J. Benjamin Miller, Yifeng Teng |
Pricing for Online Resource Allocation: Intervals and Paths. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen |
Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sepehr Assadi, Yu Chen 0039, Sanjeev Khanna |
Sublinear Algorithms for (Δ + 1) Vertex Coloring. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Alina Ene, Huy L. Nguyen |
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Zhiyi Huang 0002, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu 0001, Yuhao Zhang 0001 |
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Rebecca Reiffenhäuser |
An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein 0001 |
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Anna Großwendt, Heiko Röglin, Melanie Schmidt 0001 |
Analysis of Ward's Method. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Karl Bringmann, Marvin Künnemann, André Nusser |
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Nairen Cao, Jeremy T. Fineman, Katina Russell, Eugene Yang |
I/O-Efficient Algorithms for Topological Sort and Related Problems. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Chandra Chekuri, Kent Quanrud |
Submodular Function Maximization in Parallel via the Multilinear Relaxation. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Jelani Nelson, Huacheng Yu |
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Shi Li 0001 |
On Facility Location with General Lower Bounds. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Akshay Kamath, Eric Price 0001 |
Adaptive Sparse Recovery with Limited Adaptivity. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sam Buss, Alexander Knop |
Strategies for Stable Merge Sorting. |
SODA |
2019 |
DBLP DOI BibTeX RDF |
|