22. SODA 2011: San Francisco, California, USA

Session 1A

• T. S. Jayram, David P. Woodruff:
  Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. 1-10
  
• Elad Verbin, Wei Yu:
  The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems. 11-25
  
• Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku:
  Streaming k-means on Well-Clusterable Data. 26-40
  
• Eric Price:
  Efficient Sketches for the Set Query Problem. 41-56
  
• Guy Feigenblat, Ely Porat, Ariel Shiftan:
  Exponential Time Improvement for min-wise Based Algorithms. 57-66
  

Session 1B

• Gautier Stauffer, Guillaume Massonet, Christophe Rapine, Jean-Philippe Gayon:
  A simple and fast 2-approximation algorithms for the one-warehouse multi-retailers problem. 67-79
  
• Jian Li, Samir Khuller:
  Generalized Machine Activation Problems. 80-94
  
• Sungjin Im, Benjamin Moseley:
  Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time On Unrelated Machines. 95-108
  
• Jeff Edmonds, Sungjin Im, Benjamin Moseley:
  Online Scalable Scheduling for the ℓk-norms of Flow Time Without Conservation of Work. 109-119
  
• Kyle Fox, Benjamin Moseley:
  Online Scheduling on Identical Machines using SRPT. 120-128
  

Session 1C

• Jennifer Debroni, John D. Eblen, Michael A. Langston, Wendy Myrvold, Peter W. Shor, Dinesh Weerapurage:
  A complete resolution of the Keller maximum clique problem. 129-135
  
• Amin Coja-Oghlan, Charilaos Efthymiou:
  On independent sets in random graphs. 136-144
  
• Torsten Mütze, Thomas Rast, Reto Spöhel:
  Coloring random graphs online without creating monochromatic subgraphs. 145-158
  
• Yoshiharu Kohayakawa, Sangjune Lee, Vojtech Rödl:
  The maximum size of a Sidon set contained in a sparse random set of integers. 159-171
  
• Philippe Flajolet, Maryse Pelletier, Michèle Soria:
  On Buffon Machines and Numbers. 172-183
  

Session 2

• Bruce Reed:
  Graph Coloring via The Probabilistic Method. 184-184
  

Best Paper Presentation

• Nir Ailon, Edo Liberty:
  An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform. 185-191
  

Session 3A

• Umang Bhaskar, Lisa Fleischer, Elliot Anshelevich:
  A Stackelberg Strategy for Routing Flow over Time. 192-201
  
• Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick:
  A subexponential lower bound for the Random Facet algorithm for Parity Games. 202-216
  
• Yang Cai, Constantinos Daskalakis:
  On Minmax Theorems for Multiplayer Games. 217-234
  
• Constantinos Daskalakis, Alan Deckelbaum, Anthony Kim:
  Near-Optimal No-Regret Algorithms for Zero-Sum Games. 235-254
  
• Tim Roughgarden, Florian Schoppmann:
  Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games. 255-267
  

Session 3B

• Pankaj K. Agarwal, Thomas Mølhave, Bardia Sadri:
  I/O-Efficient Contour Queries on Terrains. 268-284
  
• Mark de Berg, Herman J. Haverkort, Constantinos P. Tsirogiannis:
  Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures. 285-296
  
• Jeff Erickson, Amir Nayyeri:
  Shortest Non-Crossing Walks in the Plane. 297-208
  
• Danny Z. Chen, Haitao Wang:
  Computing Shortest Paths amid Pseudodisks. 309-226
  
• Luca Foschini, John Hershberger, Subhash Suri:
  On the Complexity of Time-Dependent Shortest Paths. 327-341
  

Session 3C

• Michael Drmota, Wojciech Szpankowski:
  A Master Theorem for Discrete Divide and Conquer Recurrences. 342-361
  
• Pawel Gawrychowski:
  Optimal pattern matching in LZW compressed strings. 362-372
  
• Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, Oren Weimann:
  Random Access to grammar-Compressed Strings. 373-389
  
• Peyman Afshani, Gerth Stølting Brodal, Norbert Zeh:
  Ordered and Unordered Top-K Range Reporting in Large Data Sets. 390-400
  
• Marek Karpinski, Yakov Nekrich:
  Top-K Color Queries for Document Retrieval. 401-411
  

Session 4A

• Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer:
  Mobile Geometric Graphs: Detection, Coverage and Percolation. 412-428
  
• Petra Berenbrink, Colin Cooper, Tom Friedetzky, Tobias Friedrich, Thomas Sauerwald:
  Randomized Diffusion for Indivisible Loads. 429-439
  
• Keren Censor-Hillel, Hadas Shachnai:
  Fast Information Spreading in Graphs with Large Weak Conductance. 440-448
  
• George Giakkoupis, Philipp Woelfel:
  On the Randomness Requirements of Rumor Spreading. 449-461
  
• Thomas Sauerwald, Alexandre Stauffer:
  Rumor Spreading and Vertex Expansion on Regular Graphs. 462-475
  

Session 4B

• Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß:
  Bin Packing via Discrepancy of Permutations. 476-481
  
• Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi:
  Algorithms and Hardness for Subspace Approximation. 482-496
  
• Aditya Bhaskara, Aravindan Vijayaraghavan:
  Approximating Matrix p-norms. 497-511
  
• Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer:
  Subsampling Mathematical Relaxations and Average-case Complexity. 512-531
  
• Lorenzo Orecchia, Nisheeth K. Vishnoi:
  Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition. 532-545
  

Session 4C

• Ben Reichardt:
  Faster quantum algorithm for evaluating game trees. 546-559
  
• Ben Reichardt:
  Reflections for quantum query algorithms. 560-569
  
• Matthew Cook, Yunhui Fu, Robert T. Schweller:
  Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D. 570-589
  
• Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki:
  The Power of Nondeterminism in Self-Assembly. 590-602
  
• Günter Rote, Uri Zwick:
  Collapse. 603-613
  

Session 5A

• Karthekeyan Chandrasekaran, Richard Karp, Erick Moreno-Centeno, Santosh Vempala:
  Algorithms for Implicit Hitting Set Problems. 614-629
  
• Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer:
  An algorithmic decomposition of claw-free graphs leading to an O(n³)-algorithm for the weighted stable set problem. 630-646
  
• Kevin P. Costello, Asaf Shapira, Prasad Tetali:
  Randomized greedy: new variants of some classic approximation algorithms. 647-655
  
• Matthias Poloczek, Georg Schnitger:
  Randomized Variants of Johnson’s Algorithm for MAX SAT. 656-663
  
• Heidi Gebauer, Tibor Szabó, Gábor Tardos:
  The Local Lemma is Tight for SAT. 664-674
  

Session 5B

• Fabrizio Grandoni, Thomas Rothvoß:
  Pricing on Paths: A PTAS for the Highway Problem. 675-684
  
• Ning Chen, Nick Gravin, Pinyan Lu:
  On the Approximability of Budget Feasible Mechanisms. 685-699
  
• Kshipra Bhawalkar, Tim Roughgarden:
  Welfare Guarantees for Combinatorial Auctions with Item Bidding. 700-709
  
• Qiqi Yan:
  Mechanism Design via Correlation Gap. 710-719
  
• Xiaohui Bei, Zhiyi Huang:
  Bayesian Incentive Compatibility via Fractional Assignments. 720-733
  
• Jason D. Hartline, Robert Kleinberg, Azarakhsh Malekian:
  Bayesian Incentive Compatibility via Matchings. 734-747
  

Session 5C

• Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh:
  Bidimensionality and EPTAS. 748-759
  
• Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
  Slightly Superexponential Parameterized Problems. 760-776
  
• Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
  Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. 777-789
  
• Constantinos Daskalakis, Christos H. Papadimitriou:
  Continuous Local Search. 790-804
  
• Allan Grønlund Jørgensen, Kasper Green Larsen:
  Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures. 805-813
  

Session 6 - Invited Plenary Session

• William T. Freeman:
  Where computer vision needs help from computer science. 814-819
  

Session 7A

• Shay Solomon:
  An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter. 820-839
  
• Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty:
  Fast, precise and dynamic distance queries. 840-853
  
• Sariel Har-Peled, Nirman Kumar:
  Approximate Nearest Neighbor Search for Low Dimensional Queries. 854-867
  
• Yair Bartal, Ben Recht, Leonard J. Schulman:
  Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound. 868-887
  
• Lee-Ad Gottlieb, Robert Krauthgamer:
  A Nonlinear Approach to Dimension Reduction. 888-899
  

Session 7B

• Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz, Michael Krivelevich:
  Hitting time results for Maker-Breaker games. 900-912
  
• Alan M. Frieze, Michael Krivelevich, Po-Shen Loh:
  Packing tight Hamilton cycles in 3-uniform hypergraphs. 913-932
  
• Colin Cooper, Martin E. Dyer, Andrew J. Handley:
  Networks of random cycles. 933-944
  
• Ricardo Restrepo, Daniel Stefankovic, Juan Carlos Vera, Eric Vigoda, Linji Yang:
  Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees. 945-956
  
• Amin Coja-Oghlan:
  On Belief Propagation Guided Decimation for Random k-SAT. 957-966
  

Session 7C

• Shayan Oveis Gharan, Amin Saberi:
  The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. 967-975
  
• Matthew Andrews, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Ankur Moitra:
  Capacitated Metric Labeling. 976-995
  
• Laura J. Poplawski, Rajmohan Rajaraman:
  Multicommodity Facility Location under Group Steiner Access Cost. 996-1013
  
• Debmalya Panigrahi:
  Survivable Network Design Problems in Wireless Networks. 1014-1027
  
• MohammadHossein Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, Dániel Marx:
  Prize-collecting Steiner Problems on Planar Graphs. 1028-1049
  

Session 8A

• Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos:
  On Graph Crossing Number and Edge Planarization. 1050-1069
  
• Yossi Azar, Iftah Gamzu:
  Ranking with Submodular Valuations. 1070-1079
  
• Chandra Chekuri, Jan Vondrák, Rico Zenklusen:
  Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. 1080-1097
  
• Shayan Oveis Gharan, Jan Vondrák:
  Submodular Maximization by Simulated Annealing. 1098-1116
  
• Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha:
  The Matroid Median Problem. 1117-1130
  

Session 8B

• Timothy M. Chan:
  Persistent Predecessor Search and Orthogonal point Location on the Word RAM. 1131-1145
  
• Ankan Saha, S. V. N. Vishwanathan, Xinhua Zhang:
  New Approximation Algorithms for Minimum Enclosing Convex Shapes. 1146-1160
  
• Jacob Fox, János Pach:
  Computing the Independence Number of Intersection Graphs. 1161-1165
  
• Jeff Erickson, Amir Nayyeri:
  Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers. 1166-1176
  
• Erik D. Demaine, André Schulz:
  Embedding Stacked Polytopes on a Polynomial-Size Grid. 1177-1187
  

Session 8C

• Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach:
  Overlap properties of geometric expanders. 1188-1197
  
• Konstantinos Panagiotou, Angelika Steger:
  On the Degree Distribution of Random Planar Graphs. 1198-1210
  
• Colin Cooper, Alan M. Frieze:
  Component structure of the vacant set induced by a random walk on a random graph. 1211-1221
  
• Nikolaos Fountoulakis, Megha Khosla, Konstantinos Panagiotou:
  The Multiple-Orientability Thresholds for Random Hypergraphs. 1222-1236
  
• Shiva Prasad Kasiviswanathan, Cristopher Moore, Louis Theran:
  The Rigidity Transition in Random Graphs. 1237-1252
  

Session 9A

• Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta:
  Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations. 1253-1264
  
• Sungjin Im, Yajun Wang:
  Secretary Problems: Laminar Matroid and Interval Scheduling. 1265-1274
  
• José A. Soto:
  Matroid Secretary Problem in the Random Assignment Model. 1275-1284
  
• Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi:
  Online Stochastic Matching: Online Actions Based on Offline Statistics. 1285-1294
  
• Marcin Bienkowski:
  An Optimal Lower Bound for Buffer Management in Multi-Queue Switches. 1295-1305
  

Session 9B

• George B. Mertzios:
  An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy. 1306-1317
  
• Krishnendu Chatterjee, Monika Henzinger:
  Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification. 1318-1336
  
• Virginia Vassilevska Williams:
  Faster Replacement Paths. 1337-1346
  
• Jeff Erickson, Amir Nayyeri:
  Computing Replacement Paths in Surface Embedded Graphs. 1347-1354
  
• Aaron Bernstein, Liam Roditty:
  Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions. 1355-1365
  

Session 9C

• Ho Yee Cheung, Lap Chi Lau, Kai Man Leung:
  Algebraic Algorithms for Linear Matroid Parity Problems. 1366-1382
  
• Nader H. Bshouty, Hanna Mazzawi:
  On Parity Check (0, 1)-Matrix over Z^p. 1383-1394
  
• László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao:
  Code Equivalence and Group Isomorphism. 1395-1408
  
• Neeraj Kayal:
  Efficient algorithms for some special cases of the polynomial equivalence problem. 1409-1421
  
• Avner Magen, Anastasios Zouzias:
  Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication. 1422-1436
  

Session 10 - Invited Plenary Session

• Timothy Chan:
  Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems. 1437-1437
  

Session 11A

• Jakub Lacki:
  Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components. 1438-1445
  
• Liam Roditty, Roei Tov:
  Approximating the Girth. 1446-1454
  
• Yuval Emek, Amos Korman, Yuval Shavitt:
  Approximating the Statistics of various Properties in Randomly Weighted Graphs. 1455-1467
  
• Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell:
  Counting and detecting small subgraphs via equations and matrix multiplication. 1468-1476
  
• Xin He, Huaming Zhang:
  On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs. 1477-1486
  

Session 11B

• Petra Berenbrink, Martin Hoefer, Thomas Sauerwald:
  Distributed Selfish Load Balancing on Networks. 1487-1497
  
• Constantinos Daskalakis:
  On the Complexity of Approximating a Nash Equilibrium. 1498-1517
  
• Yashodhan Kanoria, Mohsen Bayati, Christian Borgs, Jennifer T. Chayes, Andrea Montanari:
  Fast Convergence of Natural Bargaining Dynamics in Exchange Networks. 1518-1537
  
• Magnús M. Halldórsson, Pradipta Mitra:
  Wireless Capacity with Oblivious Power in General Metrics. 1538-1548
  
• Thomas Kesselheim:
  A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model. 1549-1559
  

Session 11C

• Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi:
  On LP-Based Approximability for Strict CSPs. 1560-1573
  
• Venkatesan Guruswami, Yuan Zhou:
  Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. 1574-1589
  
• Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu:
  Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. 1590-1606
  
• Moses Charikar, Alantha Newman, Aleksandar Nikolov:
  Tight Hardness Results for Minimizing Discrepancy. 1607-1614
  
• Venkatesan Guruswami, Ali Kemal Sinop:
  The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. 1615-1626
  

Session 12A

• Chaitanya Swamy:
  Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms for Black-Box Distributions. 1627-1646
  
• Anand Bhalgat, Ashish Goel, Sanjeev Khanna:
  Improved Approximation Results for Stochastic Knapsack Problems. 1647-1665
  
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
  The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). 1666-1674
  
• Gary L. Miller, Richard Peng, Russell Schwartz, Charalampos E. Tsourakakis:
  Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition. 1675-1682
  

Session 12B

• Sourav Chakraborty, David García-Soriano, Arie Matsliah:
  Nearly Tight Bounds for Testing Function Isomorphism. 1683-1702
  
• Pavol Hell, Arash Rafiey:
  The Dichotomy of List Homomorphisms for Digraphs. 1703-1713
  
• Jin-yi Cai, Pinyan Lu, Mingji Xia:
  Dichotomy for Holant* Problems of Boolean Domain. 1714-1728
  
• Kazuyuki Amano:
  Bounding the Randomized Decision Tree Complexity of Read-Once Boolean Functions. 1729-1744
  

Session 12C

• Peyman Afshani, Norbert Zeh:
  Improved Space Bounds for Cache-Oblivious Range Reporting. 1745-1758
  
• Maarten Löffler, Wolfgang Mulzer:
  Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent. 1759-1777
  
• Esther Ezra, Boris Aronov, Micha Sharir:
  Improved Bound for the Union of Fat Triangles. 1778-1785
  

Last update Fri May 25 08:40:51 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page