default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID27th SODA 2016: Arlington, VA, USA
- Robert Krauthgamer:
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. SIAM 2016, ISBN 978-1-61197-433-1 - Front Matter.
- Rasmus Pagh
:
Locality-sensitive Hashing without False Negatives. 1-9 - Anja Becker, Léo Ducas, Nicolas Gama, Thijs Laarhoven:
New directions in nearest neighbor searching with applications to lattice sieving. 10-24 - Yann Disser, Jan Hackfeld, Max Klimm:
Undirected Graph Exploration with ⊝(log log n) Pebbles. 25-39 - Jonathan Scarlett, Volkan Cevher:
Phase Transitions in Group Testing. 40-53 - Xi Chen, Jinyu Xie:
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. 54-71 - George Christodoulou, Alkmini Sgouritsa:
Designing Networks with Good Equilibria under Uncertainty. 72-89 - Ran Duan, Jugal Garg, Kurt Mehlhorn:
An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. 90-106 - Adam Kunysz, Katarzyna E. Paluch, Pratik Ghosal:
Characterisation of Strongly Stable Matchings. 107-119 - Thodoris Lykouris, Vasilis Syrgkanis, Éva Tardos:
Learning and Efficiency in Games with Dynamic Population. 120-129 - John Fearnley, Rahul Savani:
The Complexity of All-switches Strategy Improvement. 130-139 - Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi:
Make-to-Order Integrated Scheduling and Distribution. 140-154 - Lin Chen, Nicole Megow, Kevin Schewior:
An O(log m)-Competitive Algorithm for Online Machine Minimization. 155-163 - Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat:
Online Degree-Bounded Steiner Network Design. 164-175 - Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley:
Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time. 176-189 - Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang:
Online Pricing with Impatient Bidders. 190-201 - Mohsen Ghaffari, Bernhard Haeupler:
Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. 202-219 - Merav Parter, David Peleg, Shay Solomon:
Local-on-Average Distributed Tasks. 220-239 - William M. Hoza, Leonard J. Schulman:
The Adversarial Noise Threshold for Distributed Protocols. 240-258 - Zeyuan Allen Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab S. Mirrokni, Lorenzo Orecchia:
Expanders via Local Edge Flips. 259-269 - Mohsen Ghaffari:
An Improved Distributed Algorithm for Maximal Independent Set. 270-277 - Michael B. Cohen:
Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities. 278-287 - Ishay Haviv, Oded Regev:
The Restricted Isometry Property of Subsampled Fourier Matrices. 288-297 - Mahdi Cheraghchi, Piotr Indyk:
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform. 298-317 - Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff:
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching. 318-337 - Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, Holger Petersen:
Simpler, faster and shorter labels for distances in graphs. 338-350 - Christian Wulff-Nilsen:
Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff. 351-362 - Massimo Cairo, Roberto Grossi, Romeo Rizzi:
New Bounds for Approximating Extremal Distances in Undirected Graphs. 363-376 - Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang:
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. 377-391 - Niv Buchbinder, Moran Feldman:
Deterministic Algorithms for Submodular Maximization Problems. 392-403 - Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida:
Improved Approximation Algorithms for k-Submodular Function Maximization. 404-413 - Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer:
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. 414-429 - Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama:
Exact and Approximation Algorithms for Weighted Matroid Intersection. 430-444 - Chandra Chekuri, Kent Quanrud:
A Fast Approximation for Maximum Weight Matroid Intersection. 445-457 - Andreas Galanis, Leslie Ann Goldberg:
The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs. 458-468 - Dimitris Achlioptas, Seyed Hamed Hassani, Nicolas Macris, Rüdiger L. Urbanke:
Bounds for Random Constraint Satisfaction Problems via Spatial Coupling. 469-479 - Ioannis Panageas, Piyush Srivastava, Nisheeth K. Vishnoi:
Evolutionary Dynamics in Finite Populations Mix Rapidly. 480-497 - Antonio Blanca, Alistair Sinclair:
Random-Cluster Dynamics in ℤ2. 498-513 - Lingxiao Huang, Pinyan Lu, Chihao Zhang:
Canonical Paths for MCMC: from Art to Science. 514-527 - Nick Gravin, Yuval Peres, Balasubramanian Sivan:
Towards Optimal Algorithms for Prediction with Expert Advice. 528-547 - Avrim Blum, Sariel Har-Peled, Benjamin Raichel:
Sparse Approximation via Generating Point Sets. 548-557 - Jiyan Yang, Yinlam Chow, Christopher Ré, Michael W. Mahoney:
Weighted SGD for ℓp Regression with Randomized Preconditioning. 558-569 - Tasuku Soma, Yuichi Yoshida:
Non-convex Compressed Sensing with the Sum-of-Squares Method. 570-579 - Justin Hsu, Zhiyi Huang, Aaron Roth, Zhiwei Steven Wu:
Jointly Private Convex Programming. 580-599 - Christian Glacet, Avery Miller, Andrzej Pelc:
Time vs. Information Tradeoffs for Leader Election in Anonymous Trees. 600-609 - Sixia Chen, Matthew Dippel, Alexander Russell, Abhishek Samanta, Ravi Sundaram:
Markovian Hitters and the Complexity of Blind Rendezvous. 610-619 - Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Stabilizing Consensus with Many Opinions. 620-635 - Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Maxwell Young:
How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. 636-654 - John Augustine, William K. Moses Jr., Amanda Redlich, Eli Upfal:
Balanced Allocation: Patience is not a Virtue. 655-671 - John Iacono, Stefan Langerman:
Weighted dynamic finger in binary search trees. 672-691 - Aaron Bernstein, Cliff Stein:
Faster Fully Dynamic Matchings with Small Approximation Ratios. 692-711 - David Peleg, Shay Solomon:
Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach. 712-729 - Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan:
Dynamic DFS in Undirected Graphs: breaking the O(m) barrier. 730-739 - Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck:
On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs. 740-753 - T.-H. Hubert Chan, Shaofeng H.-C. Jiang:
Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics. 754-765 - Anne Driemel, Amer Krivosija, Christian Sohler:
Clustering time series under the Fréchet distance. 766-785 - Shi Li:
Approximating capacitated k-median with (1 + ∊)k open facilities. 786-796 - Chandra Chekuri, Vivek Madan:
Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut. 797-807 - Chandra Chekuri, Vivek Madan:
Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation. 808-820 - Michael Dinitz, Zeyu Zhang:
Approximating Low-Stretch Spanners. 821-840 - Amir Abboud, Greg Bodwin:
Error Amplification for Pairwise Spanner Lower Bounds. 841-854 - Greg Bodwin, Virginia Vassilevska Williams:
Better Distance Preservers and Additive Spanners. 855-872 - Yair Bartal, Arnold Filtser, Ofer Neiman:
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion. 873-882 - Shiri Chechik, Christian Wulff-Nilsen:
Near-Optimal Light Spanners. 883-892 - Jean-François Biasse, Fang Song:
Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. 893-902 - Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf:
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. 903-922 - Scott Garrabrant, Igor Pak:
Permutation patterns are hard to count. 923-936 - Oscar Gilbert, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers:
Computing in continuous space with self-assembling polygonal tiles (extended abstract). 937-956 - János Pach, Natan Rubin, Gábor Tardos:
Beyond the Richter-Thomassen Conjecture. 957-968 - David Eppstein:
Treetopes and their Graphs. 969-984 - Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, Ignaz Rutter:
Windrose Planarity: Embedding Graphs with Direction-Constrained Edges. 985-996 - Tamal K. Dey, Facundo Mémoli, Yusu Wang:
Multiscale Mapper: Topological Summarization via Codomain Covers. 997-1013 - Moran Feldman, Ola Svensson, Rico Zenklusen:
Online Contention Resolution Schemes. 1014-1033 - Satoru Iwata, Yu Yokoi:
Finding a Stable Allocation in Polymatroid Intersection. 1034-1047 - Christos Kalaitzis:
An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem. 1048-1066 - Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink:
The matching problem has no small symmetric SDP. 1067-1078 - Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm:
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. 1079-1095 - Yixin Cao:
Linear Recognition of Almost Interval Graphs. 1096-1115 - Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk:
Subexponential parameterized algorithm for Interval Completion. 1116-1131 - Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk:
Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems. 1132-1151 - Shivam Garg, Geevarghese Philip:
Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee. 1152-1166 - Marcin Pilipczuk, Magnus Wahlström:
Directed multicut is W[1]-hard, even for four terminal pairs. 1167-1178 - Pankaj K. Agarwal, Kyle Fox, Oren Salzman:
An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles. 1179-1192 - Sariel Har-Peled, Haim Kaplan, Micha Sharir:
Approximating the k-Level in Three-Dimensional Plane Arrangements. 1193-1212 - Timothy M. Chan:
Improved Deterministic Algorithms for Linear Programming in Low Dimensions. 1213-1219 - Sunil Arya, David M. Mount:
A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees. 1220-1233 - Michael Kerber, Donald R. Sheehy, Primoz Skraba:
Persistent Homology and Nested Dissection. 1234-1245 - Timothy M. Chan, Ryan Williams:
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. 1246-1255 - Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir:
Subtree Isomorphism Revisited. 1256-1271 - Tsvi Kopelowitz, Seth Pettie, Ely Porat:
Higher Lower Bounds from the 3SUM Conjecture. 1272-1287 - Matti Karppa, Petteri Kaski, Jukka Kohonen:
A Faster Subquadratic Algorithm for Finding Outlier Correlations. 1288-1305 - Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski:
Algorithmic Complexity of Power Law Networks. 1306-1325 - Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova:
Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. 1326-1344 - Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev:
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. 1345-1364 - Amit Chakrabarti, Anthony Wirth:
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. 1365-1373 - Vladimir Braverman, Harry Lang, Keith D. Levin, Morteza Monemizadeh:
Clustering Problems on Sliding Windows. 1374-1390 - Yuichi Yoshida:
Gowers Norm, Function Limits, and Parameter Estimation. 1391-1406 - Nicolas Bousquet, Yang Cai, Christoph Hunkenschröder, Adrian Vetta:
On the Economic Efficiency of the Combinatorial Clock Auction. 1407-1423 - Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta:
Approximately Efficient Double Auctions with Strong Budget Balance. 1424-1443 - Mark Braverman, Jieming Mao, S. Matthew Weinberg:
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. 1444-1457 - Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein:
On the Complexity of Dynamic Mechanism Design. 1458-1475 - Shuchi Chawla, Nikhil R. Devanur, Anna R. Karlin, Balasubramanian Sivan:
Simple Pricing Schemes For Consumers With Evolving Values. 1476-1490 - Giorgi Nadiradze, Andreas Wiese:
On approximating strip packing with a better ratio than 3/2. 1491-1510 - Yossi Azar, Ilan Reuven Cohen, Amos Fiat, Alan Roytman:
Packing Small Vectors. 1511-1525 - Klaus Jansen, Marten Maack, Malin Rau:
Approximation schemes for machine scheduling with resource (in-)dependent processing times. 1526-1542 - Xue Chen:
Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders. 1543-1560 - Nikhil Bansal, Marek Eliás, Arindam Khan:
Improved Approximation for Vector Bin Packing. 1561-1579 - Guillaume Chapuy, Guillem Perarnau:
Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture. 1580-1588 - Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoffman, Linh V. Tran:
Recovery and Rigidity in a Regular Stochastic Block Model. 1589-1601 - Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu:
Distance in the Forest Fire Model How far are you from Eve? 1602-1620 - Constantinos Daskalakis, Sebastien Roch:
Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound (Extended Abstract). 1621-1630 - Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup:
The Power of Two Choices with Simple Tabulation. 1631-1642 - Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala:
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. 1643-1649 - Radu Curticapean, Dániel Marx:
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. 1650-1669 - Robert Ganian, M. S. Ramanujan, Stefan Szeider:
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting. 1670-1681 - Attila Bernáth, Tamás Király:
Blocking Optimal k-Arborescences. 1682-1694 - Jisu Jeong, Eun Jung Kim, Sang-il Oum:
Constructive algorithm for path-width of matroids. 1695-1704 - Guy Kindler, Alexandra Kolla, Luca Trevisan:
Approximation of non-boolean 2CSP. 1705-1714 - Robert Hildebrand, Robert Weismantel, Kevin Zemmer:
An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra. 1715-1723 - Venkatesan Guruswami, Euiwoong Lee:
Nearly Optimal NP-Hardness of Unique Coverage. 1724-1730 - Anupam Gupta, Viswanath Nagarajan, Sahil Singla:
Algorithms and Adaptivity Gaps for Stochastic Probing. 1731-1747 - Noah Stephens-Davidowitz:
Discrete Gaussian Sampling Reduces to CVP and SVP. 1748-1764 - Brendan Nagle, Vojtech Rödl, Mathias Schacht:
An Algorithmic Hypergraph Regularity Lemma. 1765-1773 - Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong:
Obstructions for three-coloring graphs with one forbidden induced subgraph. 1774-1783 - Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen:
Independence and Efficient Domination on P6-free Graphs. 1784-1803 - Gwenaël Joret, Piotr Micek, Veit Wiechert:
Sparsity and dimension. 1804-1813 - Chidambaram Annamalai:
Finding Perfect Matchings in Bipartite Hypergraphs. 1814-1823 - Zeyuan Allen Zhu, Yin Tat Lee, Lorenzo Orecchia:
Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver. 1824-1831 - Ali Kemal Sinop:
How to Round Subspaces: A New Spectral Clustering Algorithm. 1832-1847 - Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee:
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile. 1848-1861 - Richard Peng:
Approximate Undirected Maximum Flows in O(mpolylog(n)) Time. 1862-1867 - Damian Straszak, Nisheeth K. Vishnoi:
Natural Algorithms for Flow Problems. 1868-1883 - Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. 1884-1892 - Boris Bukh, Venkatesan Guruswami:
An improved bound on the fraction of correctable deletions. 1893-1901 - Badih Ghazi, Pritish Kamath, Madhu Sudan:
Communication Complexity of Permutation-Invariant Functions. 1902-1921 - Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson:
Towards Optimal Deterministic Coding for Interactive Communication. 1922-1936 - Ross Berkowitz, Swastik Kopparty:
Robust positioning patterns. 1937-1951 - Sarah Cannon, Dana Randall:
Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions. 1952-1971 - Martin E. Dyer, Mark Jerrum, Haiko Müller:
On the switch Markov chain for perfect matchings. 1972-1983 - Antares Chen, David G. Harris, Aravind Srinivasan:
Partial Resampling to Approximate Covering Integer Programs. 1984-2003 - David G. Harris, Aravind Srinivasan:
Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution. 2004-2023 - Dimitris Achlioptas, Fotis Iliopoulos:
Focused Stochastic Local Search and the Lovász Local Lemma. 2024-2038 - Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya:
The k-mismatch problem revisited. 2039-2052 - Djamal Belazzougui, Simon J. Puglisi:
Range Predecessor and Lempel-Ziv Parsing. 2053-2071 - Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. 2072-2085 - Ross Churchley, Bojan Mohar, Hehui Wu:
Weak duality for packing edge-disjoint odd (u, v)-trails. 2086-2094 - Noga Alon, Humberto Naves, Benny Sudakov:
On the maximum quartet distance between phylogenetic trees. 2095-2106
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 2026-07-14 00:29 CEST 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, funded, and maintained by:
Schloss Dagstuhl - Leibniz Center for Informatics is a member of the Leibniz Association and is funded by the federal government of Germany and the states of Germany, especially Saarland and Rhineland‑Palatinate.
