Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID30th SODA 2019: San Diego, California, USA
- Timothy M. Chan:
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019. SIAM 2019, ISBN 978-1-61197-548-2 - Front Matter. i-ix
- Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein:
Fine-grained Complexity Meets IP = PSPACE. 1-20 - Lijie Chen, Ryan Williams:
An Equivalence Class for Orthogonal Vectors. 21-40 - Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. 41-57 - Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos
, Hongxun Wu:
Fast Modular Subset Sum using Linear Sketching. 58-69 - Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk:
A Subquadratic Approximation Scheme for Partition. 70-88 - Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee:
Metrical task systems on trees via mirror descent and unfair gluing. 89-97 - Niv Buchbinder, Anupam Gupta, Marco Molinaro, Joseph (Seffi) Naor:
k-Servers with a Smile: Online Algorithms via Projections. 98-116 - C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee:
A Nearly-Linear Bound for Chasing Nested Convex Bodies. 117-122 - Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall:
A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. 123-142 - Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi:
Elastic Caching. 143-156 - Santiago R. Balseiro, Vahab S. Mirrokni, Renato Paes Leme, Song Zuo:
Dynamic Double Auctions: Towards First Best. 157-172 - Yuan Deng, Debmalya Panigrahi:
Multi-unit Supply-monotone Auctions with Bayesian Valuations. 173-192 - Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang:
Correlation-Robust Analysis of Single Item Auction. 193-208 - Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, Tao Xiao:
Tight Revenue Gaps among Simple Mechanisms. 209-228 - Itai Ashlagi, Amin Saberi, Ali Shameli:
Assignment Mechanisms under Distributional Constraints. 229-240 - Niv Buchbinder, Moran Feldman, Mohit Garg:
Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid. 241-254 - Matthew Fahrbach, Vahab S. Mirrokni, Morteza Zadimoghaddam:
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity. 255-273 - Alina Ene, Huy L. Nguyen:
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. 274-282 - Eric Balkanski, Aviad Rubinstein, Yaron Singer:
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. 283-302 - Chandra Chekuri, Kent Quanrud:
Submodular Function Maximization in Parallel via the Multilinear Relaxation. 303-322 - Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna:
Stochastic Submodular Cover with Limited Adaptivity. 323-342 - Marco Molinaro:
Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method. 343-354 - Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances. 355-372 - Jie Xue:
Colored range closest-pair problem under general distance functions. 373-390 - Eunjin Oh:
Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons. 391-409 - Adrian Dumitrescu, Ritankar Mandal:
New Lower Bounds for the Number of Pseudoline Arrangements. 410-425 - Jie Han, Yoshiharu Kohayakawa, Marcelo Tadeu Sales, Henrique Stagni:
Extremal and probabilistic results for order types. 426-435 - Joshua Brakensiek, Venkatesan Guruswami:
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. 436-455 - Monaldo Mastrolilli:
The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain. 456-475 - Jin-Yi Cai, Artem Govorov:
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. 476-495 - Matti Karppa, Petteri Kaski:
Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication. 496-515 - Huy L. Nguyen:
Fast greedy for linear matroids. 516-524 - Robert Krauthgamer, James R. Lee, Havana Rika:
Flow-Cut Gaps and Face Covers in Planar Graphs. 525-534 - Ario Salmasi, Anastasios Sidiropoulos, Vijay Sridhar:
On Constant Multi-Commodity Flow-Cut Gaps for Families of Directed Minor-Free Graphs. 535-553 - Yipu Wang:
Maximum Integer Flows in Directed Planar Graphs with Vertex Capacities and Multiple Sources and Sinks. 554-568 - Nathaniel Lahn, Sharath Raghvendra:
A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs. 569-588 - David Eppstein, Bruce A. Reed:
Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time. 589-605 - Ofer Grossman, Yang P. Liu:
Reproducibility and Pseudo-Determinism in Log-Space. 606-620 - Rocco A. Servedio, Li-Yang Tan:
Pseudorandomness for read-k DNF formulas. 621-638 - Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse:
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. 639-646 - Vishwas Bhargava, Markus Bläser, Gorav Jindal, Anurag Pandey:
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials. 647-661 - Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. 662-678 - Gautam Kamath, Christos Tzamos:
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing. 679-693 - Nathaniel Harms:
Testing Halfspaces over Rotation-Invariant Distributions. 694-713 - Hendrik Fichtenberger, Pan Peng, Christian Sohler:
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty. 714-726 - Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang:
Testing Matrix Rank, Optimally. 727-746 - Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for ℓp-Low Rank Approximation. 747-766 - Sepehr Assadi, Yu Chen, Sanjeev Khanna:
Sublinear Algorithms for (Δ + 1) Vertex Coloring. 767-786 - Shiri Chechik, Doron Mukhtar:
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model. 787-804 - Mohsen Ghaffari:
Distributed Maximal Independent Set using Small Messages. 805-820 - Yi-Jun Chang, Seth Pettie, Hengjie Zhang:
Distributed Triangle Detection via Expander Decomposition. 821-840 - David G. Harris:
Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma. 841-860 - Rohit Gurjar, Nisheeth K. Vishnoi:
On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes). 861-880 - Kyle Fox, Debmalya Panigrahi, Fred Zhang:
Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions. 881-896 - Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran:
Improving the smoothed complexity of FLIP for max cut problems. 897-916 - Max Klimm, Philipp Warode:
Computing all Wardrop Equilibria parametrized by the Flow Demand. 917-934 - Leon Sering, Laura Vargas Koch:
Nash Flows Over Time with Spillback. 935-945 - Colin Cooper, Alan M. Frieze, Wesley Pegden:
On the rank of a random binary matrix. 946-955 - Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald:
On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract. 956-965 - Georgios Amanatidis, Pieter Kleer:
Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices. 966-985 - Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan:
XOR Codes and Sparse Learning Parity with Noise. 986-1004 - Elchanan Mossel, Jiaming Xu:
Seeded Graph Matching via Large Neighborhood Statistics. 1005-1014 - Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen:
Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces. 1015-1034 - Fahad Panolan, Saket Saurabh, Meirav Zehavi:
Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity. 1035-1054 - MohammadHossein Bateni, Alireza Farhadi, MohammadTaghi Hajiaghayi:
Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs. 1055-1068 - Eli Fox-Epstein, Philip N. Klein, Aaron Schild:
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. 1069-1088 - Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, Kevin Schewior:
A PTAS for Euclidean TSP with Hyperplane Neighborhoods. 1089-1105 - Raphaël Clifford, Tomasz Kociumaka, Ely Porat:
The streaming k-mismatch problem. 1106-1125 - Karl Bringmann, Marvin Künnemann, Philip Wellnitz:
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. 1126-1145 - Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya:
Lower bounds for text indexing with mismatches and differences. 1146-1164 - William Kuszmaul:
Efficiently Approximating Edit Distance Between Pseudorandom Strings. 1165-1180 - MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Xiaorui Sun:
Approximating LCS in Linear Time: Beating the √n Barrier. 1181-1200 - Günter Rote:
The Maximum Number of Minimal Dominating Sets in a Tree. 1201-1214 - Zilin Jiang, Nikita Polyanskii:
How to guess an n-digit number. 1215-1220 - Raphael Yuster:
Vector clique decompositions. 1221-1238 - Sophie Spirkl, Maria Chudnovsky, Mingxian Zhong:
Four-coloring P6-free graphs. 1239-1256 - Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs. 1257-1271 - Sam Buss, Alexander Knop:
Strategies for Stable Merge Sorting. 1272-1290 - Haim Kaplan, Or Zamir, Uri Zwick:
A sort of an adversary. 1291-1310 - Caleb C. Levy, Robert E. Tarjan:
A New Path from Splay to Dynamic Optimality. 1311-1330 - Shunhua Jiang, Kasper Green Larsen:
A Faster External Memory Priority Queue with DecreaseKeys. 1331-1343 - Dominik Kempa:
Optimal Construction of Compressed Indexes for Highly Repetitive Texts. 1344-1357 - Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. 1358-1368 - Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat:
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design. 1369-1386 - AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford:
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications. 1387-1404 - Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva:
Iterative Refinement for ℓp-norm Regression. 1405-1424 - András Gilyén, Srinivasan Arunachalam, Nathan Wiebe:
Optimizing quantum optimization algorithms via faster quantum gradient computation. 1425-1444 - Julia Chuzhoy, Zihan Tan:
Towards Tight(er) Bounds for the Excluded Grid Theorem. 1445-1464 - Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer:
Polynomial Planar Directed Grid Theorem. 1465-1484 - Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond:
A tight Erdős-Pósa function for planar minors. 1485-1500 - Michal Pilipczuk, Sebastian Siebertz:
Polynomial bounds for centered colorings on proper minor-closed graph classes. 1501-1520 - Vida Dujmovic, Fabrizio Frati, Daniel Gonçalves, Pat Morin, Günter Rote:
Every Collinear Set in a Planar Graph Is Free. 1521-1538 - Rico Zenklusen:
A 1.5-Approximation for Path TSP. 1539-1549 - Martin Nägele, Rico Zenklusen:
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond. 1550-1569 - Shashwat Garg, Janardhan Kulkarni, Shi Li:
Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time. 1570-1584 - Uriel Feige, Janardhan Kulkarni, Shi Li:
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. 1585-1595 - Chandra Chekuri, Kent Quanrud:
On Approximating (Sparse) Covering Integer Programs. 1596-1615 - Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein:
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. 1616-1635 - Mohsen Ghaffari, Jara Uitto:
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. 1636-1653 - MohammadTaghi Hajiaghayi, Saeed Seddighin, Xiaorui Sun:
Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence. 1654-1672 - Merav Parter, Eylon Yogev:
Low Congestion Cycle Covers and Their Applications. 1673-1692 - Merav Parter, Eylon Yogev:
Distributed Algorithms Made Secure: A Graph Theoretic Approach. 1693-1710 - Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, Meirav Zehavi:
Interval Vertex Deletion Admits a Polynomial Kernel. 1711-1730 - Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk:
Losing Treewidth by Separating Subsets. 1731-1749 - Gregory Z. Gutin, Magnus Wahlström, Meirav Zehavi:
On r-Simple k-Path and Related Problems Parameterized by k/r. 1750-1769 - André Berger, László Kozma, Matthias Mnich, Roland Vincze:
A time- and space-optimal algorithm for the many-visits TSP. 1770-1782 - Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. 1783-1793 - Alexander Wei:
Optimal Las Vegas Approximate Near Neighbors in ℓp. 1794-1813 - Subhash Khot, Assaf Naor:
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. 1814-1824 - Ruosong Wang, David P. Woodruff:
Tight Bounds for ℓp Oblivious Subspace Embeddings. 1825-1843 - Jelani Nelson, Huacheng Yu:
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. 1844-1860 - Madhu Sudan, Badih Ghazi, Noah Golowich, Mitali Bafna:
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. 1861-1871 - Sayan Bhattacharya, Janardhan Kulkarni:
Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time. 1872-1885 - Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, Shay Solomon:
(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time. 1886-1898 - Aaron Bernstein, Sebastian Forster, Monika Henzinger:
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. 1899-1918 - Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon:
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. 1919-1936 - Ran Duan, Haoqing He, Tianyi Zhang:
Dynamic Edge Coloring with Improved Approximation. 1937-1945 - José Correa, Raimundo Saona, Bruno Ziliotto:
Prophet Secretary Through Blind Strategies. 1946-1961 - Shuchi Chawla, J. Benjamin Miller, Yifeng Teng:
Pricing for Online Resource Allocation: Intervals and Paths. 1962-1981 - Rebecca Reiffenhäuser:
An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. 1982-1993 - Eshwar Ram Arunachaleswaran, Siddharth Barman, Nidhi Rathi:
Fully Polynomial-Time Approximation Schemes for Fair Rent Division. 1994-2013 - Benjamin Plaut, Tim Roughgarden:
Communication Complexity of Discrete Fair Division. 2014-2033