default search action
24th SODA 2013: New Orleans, Louisiana, USA
- Sanjeev Khanna:
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013. SIAM 2013, ISBN 978-1-61197-251-1
Session 1A
- Prateek Bhakta, Sarah Miracle, Dana Randall, Amanda Pascoe Streib:
Mixing Times of Markov Chains for Self-Organizing Lists and Biased Permutations. 1-15 - Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, He Sun:
Balls into Bins via Local Search. 16-34 - Mathieu Leconte, Marc Lelarge, Laurent Massoulié:
Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing. 35-46 - Yitong Yin, Chihao Zhang:
Approximate Counting via Correlation Decay on Planar Graphs. 47-66 - Liang Li, Pinyan Lu
, Yitong Yin:
Correlation Decay up to Uniqueness in Spin Systems. 67-84
Session 1B
- Yossi Azar, Umang Bhaskar, Lisa Fleischer, Debmalya Panigrahi:
Online Mixed Packing and Covering. 85-100 - Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg:
Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching. 101-107 - Michael Dinitz
Matroid Secretary for Regular and Decomposable Matroids. 108-117 - Elisabeth Günther, Olaf Maurer, Nicole Megow, Andreas Wiese:
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio. 118-128 - Kyle Fox, Madhukar Korupolu:
Weighted Flowtime on Capacitated Machines. 129-143
Session 1C
- Siu-Wing Cheng, Jiongxin Jin:
Approximate Shortest Descending Paths. 144-155 - Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, Micha Sharir:
Computing the Discrete Fréchet Distance in Subquadratic Time. 156-167 - Benjamin A. Burton, Jonathan Spreer
The complexity of detecting taut angle structures on triangulations. 168-183 - Matthew Bauer, Mirela Damian:
An Infinite Class of Sparse-Yao Spanners. 184-196 - Tamal K. Dey, Pawas Ranjan, Yusu Wang:
Weighted Graph Laplace Operator under Topological Noise. 197-208
Session 2A
- Mihai Patrascu, Mikkel Thorup
Twisted Tabulation Hashing. 209-228 - Djamal Belazzougui, Rossano Venturini:
Compressed static functions with applications. 229-240 - Timothy M. Chan, Bryan T. Wilkinson:
Adaptive and Approximate Orthogonal Range Counting. 241-251 - Zhewei Wei, Ke Yi:
The Space Complexity of 2-Dimensional Approximate Range Counting. 252-264 - Kasper Green Larsen, Freek van Walderveen:
Near-Optimal Range Reporting Structures for Categorical Data. 265-276
Session 2B
- Per Austrin, Siavosh Benabbas, Konstantinos Georgiou:
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection. 277-294 - Venkatesan Guruswami, Ali Kemal Sinop:
Approximating Non-Uniform Sparsest Cut Via Generalized Spectra. 295-305 - Alina Ene, Jan Vondrák, Yi Wu:
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. 306-325 - Chandra Chekuri, Alina Ene:
Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion. 326-341 - Marek Cygan, Fabrizio Grandoni
How to Sell Hyperedges: The Hypermatching Assignment Problem. 342-351
Session 2C
- Kyle Fox:
Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs. 352-364 - Ken-ichi Kawarabayashi, Daniel Král', Marek Krcál, Stephan Kreutzer:
Packing directed cycles through a specified vertex set. 365-377 - Ken-ichi Kawarabayashi, Kenta Ozeki:
4-connected projective-planar graphs are hamiltonian-connected. 378-395 - Fedor V. Fomin, Michal Pilipczuk:
Jungles, bundles, and fixed parameter tractability. 396-413 - Martin Grohe, Ken-ichi Kawarabayashi, Bruce A. Reed:
A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory. 414-431
Session 3A
- Mahdi Cheraghchi
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. 432-442 - Zvika Brakerski, Moni Naor:
Fast Algorithms for Interactive Coding. 443-456 - Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh
Shift Finding in Sub-Linear Time. 457-465 - Kenneth L. Clarkson, Petros Drineas
The Fast Cauchy Transform and Faster Robust Linear Regression. 466-477 - Chen Avin, Michael Borokhovich, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter, David Peleg:
Generalized Perron-Frobenius Theorem for Multiple Choice Matrices, and Applications. 478-497
Session 3B
- Shiri Chechik:
New Additive Spanners. 498-512 - Michael Elkin, Shay Solomon:
Fast Constructions of Light-Weight Spanners for General Graphs. 513-525 - Rachit Agarwal, Philip Brighten Godfrey:
Distance Oracles for Stretch Less Than 2. 526-538 - Christian Wulff-Nilsen:
Approximate Distance Oracles with Improved Query Time. 539-549 - Ken-ichi Kawarabayashi, Christian Sommer, Mikkel Thorup
More Compact Oracles for Approximate Distances in Undirected Planar Graphs. 550-563
Session 3C
- Yang Cai
Simple and Nearly Optimal Multi-Item Auctions. 564-577 - Yang Cai
Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations. 578-595 - Pablo Daniel Azar, Constantinos Daskalakis, Silvio Micali, S. Matthew Weinberg
Optimal and Efficient Parametric Auctions. 596-604 - Gagan Goel, Vahab S. Mirrokni, Renato Paes Leme:
Clinching Auction with Online Supply. 605-619 - Rahul Deb, Mallesh M. Pai:
Ironing in Dynamic Revenue Management: Posted Prices & Biased Auctions. 620-631
Session 4A
- Emanuele Viola:
The communication complexity of addition. 632-651 - Eric Price, David P. Woodruff:
Lower Bounds for Adaptive Sparse Recovery. 652-663 - Raphaël Clifford, Markus Jalsenius, Benjamin Sach:
Tight Cell-Probe Bounds for Online Hamming Distance Computation. 664-674 - Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol:
On the number of matroids. 675-694 - Benjamin Doerr, Reto Spöhel, Henning Thomas, Carola Winzen
Playing Mastermind with Many Colors. 695-704
Session 4B
- Bernhard Haeupler
Simple, Fast and Deterministic Gossip and Rumor Spreading. 705-716 - Chinmoy Dutta, Gopal Pandurangan
On the Complexity of Information Spreading in Dynamic Networks. 717-736 - Yoann Dieudonné, Andrzej Pelc:
Anonymous Meeting in Networks. 737-747 - Mohsen Ghaffari, Bernhard Haeupler
Near Optimal Leader Election in Multi-Hop Radio Networks. 748-766 - Maria-Florina Balcan, Christian Borgs
Finding Endogenously Formed Communities. 767-783
Session 4C
- Dror Aiger, Haim Kaplan, Micha Sharir:
Reporting neighbors in high-dimensional Euclidean spaces. 784-803 - Sariel Har-Peled
Euclidean spanners in high dimensions. 804-809 - Euiwoong Lee
Clustering Affine Subspaces: Hardness and Algorithms. 810-827 - Adrian Dumitrescu, Csaba D. Tóth:
The traveling salesman problem for lines, balls and planes. 828-843 - Joseph S. B. Mitchell:
Approximating Watchman Routes. 844-855
Session 5A
- Michael J. Bannister, Christopher DuBois, David Eppstein, Padhraic Smyth
Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges. 856-864 - Gonzalo Navarro, Yakov Nekrich
Optimal Dynamic Sequence Representations. 865-876 - Ralph Neininger, Kevin Leckey, Wojciech Szpankowski:
Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model. 877-886 - Xiaocheng Hu, Cheng Sheng, Yufei Tao
Output-sensitive Skyline Algorithms in External Memory. 887-900 - Freek van Walderveen, Norbert Zeh, Lars Arge:
Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs. 901-918
Session 5B
- Klaus Jansen, Lars Prädel:
New Approximability Results for Two-Dimensional Bin Packing. 919-936 - Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, Udi Wieder:
Minimum Makespan Scheduling with Low Rank Processing Times. 937-947 - Kyle Fox, Sungjin Im, Benjamin Moseley:
Energy Efficient Scheduling of Parallelizable Jobs. 948-957 - Marcin Mucha:
Lyndon Words and Short Superstrings. 958-972 - Noa Avigdor-Elgrabli, Yuval Rabani
A Constant Factor Approximation Algorithm for Reordering Buffer Management. 973-984
Session 5C
- Ken-ichi Kawarabayashi:
5-coloring K3, k-minor-free graphs: Beyond Thomassen. 985-1003 - Zdenek Dvorák
List-coloring embedded graphs. 1004-1012 - Ken-ichi Kawarabayashi:
Totally odd subdivisions and parity subdivisions: Structures and Coloring. 1013-1029 - Thomas Bläsius, Ignaz Rutter:
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems. 1030-1043 - Marek Cygan, Marcin Pilipczuk
Known algorithms for EDGE CLIQUE COVER are probably optimal. 1044-1053
Session 6A
- David J. Rosenbaum:
Breaking the nlog n Barrier for Solvable-Group Isomorphism. 1054-1073 - Henry Cohn, Christopher Umans:
Fast matrix multiplication using coherent configurations. 1074-1087 - Daniel Dadush
Lattice Sparsification and the Approximate Closest Vector Problem. 1088-1102 - Daniel Dadush
Algorithms for the Densest Sub-Lattice Problem. 1103-1122 - Friedrich Eisenbrand, Nicolai Hähnle:
Minimizing the number of lattice points in a translated polygon. 1123-1130
Session 6B
- Bruce M. Kapron
Dynamic graph connectivity in polylogarithmic worst case time. 1131-1142 - Liam Roditty:
Decremental maintenance of strongly connected components. 1143-1150 - Gary L. Miller, Richard Peng:
Approximate Maximum Flow on Separable Undirected Graphs. 1151-1170 - Ran Duan:
Breaking the O(n2.5) Time Barrier for Undirected Unit-Capacity Maximum Flow. 1171-1179 - Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin
Smoothed Analysis of the Successive Shortest Path Algorithm. 1180-1189
Session 6C
- Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour:
Regret Minimization for Reserve Prices in Second-Price Auctions. 1190-1204 - Shahar Dobzinski, Jan Vondrák:
Communication Complexity of Combinatorial Auctions with Submodular Valuations. 1205-1215 - Michael Kapralov
Online Submodular Welfare Maximization: Greedy is Optimal. 1216-1225 - Jugal Garg, Ruta Mehta, Milind A. Sohoni, Nisheeth K. Vishnoi:
Towards Polynomial Simplex-Like Algorithms for Market Equlibria. 1226-1242 - Leah Epstein, Asaf Levin
A unified approach to truthful scheduling on related machines. 1243-1252
Session 7A
- Dominik Scheder
Exponential Lower Bounds for the PPSZ k-SAT Algorithm. 1253-1263 - Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini:
Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis. 1264-1277 - Jin-Yi Cai, Pinyan Lu
Dichotomy for Holant* Problems with Domain Size 3. 1278-1295 - Anna Huber, Andrei A. Krokhin, Robert Powell:
Skew Bisubmodularity and Valued CSPs. 1296-1305 - Michael Molloy, Ricardo Restrepo:
Frozen variables in random boolean constraint satisfaction problems. 1306-1318
Session 7B
- Dana Ron, Rocco A. Servedio
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. 1319-1336 - Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. 1337-1355 - Sofya Raskhodnikova, Grigory Yaroslavtsev:
Learning pseudo-Boolean k-DNF and submodular functions. 1356-1368 - Erik D. Demaine, Morteza Zadimoghaddam:
Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's". 1369-1379 - Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio
Learning mixtures of structured distributions over discrete domains. 1380-1394
Session 7C
- Michael Kapralov
On differentially private low rank approximation. 1395-1414 - Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith:
The Power of Linear Reconstruction Attacks. 1415-1433 - Dan Feldman, Melanie Schmidt
Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. 1434-1453 - Ankur Moitra:
An Almost Optimal Algorithm for Computing Nonnegative Rank. 1454-1464 - Ian Post, Yinyu Ye:
The simplex method is strongly polynomial for deterministic Markov decision processes. 1465-1473
Session 8A
- Stacey Jeffery, Robin Kothari, Frédéric Magniez:
Nested Quantum Walks with Quantum Data Structures. 1474-1485 - Troy Lee, Frédéric Magniez, Miklos Santha:
Improved quantum query algorithms for triangle finding and associativity testing. 1486-1502 - Rahul Jain, Yaoyun Shi, Zhaohui Wei, Shengyu Zhang:
Efficient protocols of generating bipartite classical distributions and quantum states. 1503-1512 - Robert T. Schweller, Michael Sherman:
Fuel Efficient Computation in Passive Self-Assembly. 1513-1525 - Nadine Dabby, Ho-Lin Chen:
Active Self-Assembly of Simple Units Using an Insertion Primitive. 1526-1536
Session 8B
- Ryan O'Donnell, Yuan Zhou
Approximability and proof complexity. 1537-1556 - Parinya Chalermsook, Bundit Laekhanukit
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More. 1557-1576 - Sharon Goldberg, Zhenming Liu:
The Diffusion of Networking Technologies. 1577-1594 - Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra, Roger Wattenhofer:
The Power of Non-Uniform Wireless Power. 1595-1606 - Sara Ahmadian, Zachary Friggstad, Chaitanya Swamy:
Local-Search based Approximation Algorithms for Mobile Facility Location Problems. 1607-1621
Session 8C
- Jeff M. Phillips:
Є-Samples for Kernels. 1622-1632 - Chih-Hung Liu, D. T. Lee:
Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes. 1633-1645 - Jeff Erickson, Kim Whittlesey:
Transforming Curves on Surfaces Redux. 1646-1655 - Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati
Morphing Planar Graph Drawings with a Polynomial Number of Steps. 1656-1667 - Stephen G. Kobourov
Combinatorial and Geometric Properties of Planar Laman Graphs. 1668-1678
Session 9A
- Michael Kapralov
Better bounds for matchings in the streaming model. 1679-1697 - Michael E. Saks, C. Seshadhri:
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. 1698-1709 - Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, Christian Sohler
(1+ Є)-approximation for facility location in data streams. 1710-1728 - Alexandr Andoni, Huy L. Nguyen:
Eigenvalues of a matrix in the streaming model. 1729-1737 - Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. 1738-1756
Session 9B
- Christian Wulff-Nilsen:
Faster Deterministic Fully-Dynamic Graph Connectivity. 1757-1769 - Hiroshi Hirai:
Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems. 1770-1788 - Robert Krauthgamer, Inbal Rika
Mimicking Networks and Succinct Representations of Terminal Cuts. 1789-1799 - Jesper Jansson, Chuanqi Shen, Wing-Kin Sung:
Improved Algorithms for Constructing Consensus Trees. 1800-1813 - Gerth Stølting Brodal, Rolf Fagerberg, Thomas Mailund, Christian N. S. Pedersen, Andreas Sand:
Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree. 1814-1832
Session 9C
- Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
Testing k-Modal Distributions: Optimal Algorithms via Reductions. 1833-1852 - Ittai Abraham, Shiri Chechik, David Kempe, Aleksandrs Slivkins:
Low-distortion Inference of Latent Similarities from a Multiplex Social Network. 1853-1872 - Adrian Kosowski:
A Õ (n2) Time-Space Trade-off for Undirected s-t Connectivity. 1873-1883 - Etienne Birmelé, Rui A. Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, Gustavo Sacomoto:
Optimal Listing of Cycles and st-Paths in Undirected Graphs. 1884-1896 - Boris Aronov, Anne Driemel
Segmentation of Trajectories for Non-Monotone Criteria. 1897-1911
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-27 20:31 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: