38. ICALP 2011: Zurich, Switzerland - Part I

Network Design Problems

• Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev:
  Improved Approximation for the Directed Spanner Problem. 1-12
  
• Bundit Laekhanukit:
  An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity - (Extended Abstract). 13-24
  
• Anna Adamaszek, Artur Czumaj, Andrzej Lingas, Jakub Onufry Wojtaszczyk:
  Approximation Schemes for Capacitated Geometric Network Design. 25-36
  
• Jiawei Qian, David P. Williamson:
  An O(logn)-Competitive Algorithm for Online Constrained Forest Problems. 37-48
  

Quantum Computing

• Shengyu Zhang:
  On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity. 49-60
  
• Scott Aaronson, Andrew Drucker:
  Advice Coins for Classical and Quantum Computation. 61-72
  
• André Chailloux, Iordanis Kerenidis, Bill Rosgen:
  Quantum Commitments from Complexity Assumptions. 73-85
  
• Aram Wettroth Harrow, Ashley Montanaro, Anthony J. Short:
  Limitations on Quantum Dimensionality Reduction. 86-97
  

Graph Algorithms

• Stefan Canzar, Khaled M. Elbassioni, Gunnar W. Klau, Julián Mestre:
  On Tree-Constrained Matchings and Generalizations. 98-109
  
• Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos:
  Tight Bounds for Linkages in Planar Graphs. 110-121
  
• Markus Chimani, Petr Hlinený:
  A Tighter Insertion-Based Approximation of the Crossing Number. 122-134
  
• Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer:
  Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. 135-146
  

Games, Approximation Schemes, Smoothed Analysis

• Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey:
  Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. 147-158
  
• Martin E. Dyer, Velumailum Mohanaraj:
  Pairwise-Interaction Games. 159-170
  
• Robert Elsässer, Tobias Tscheuschner:
  Settling the Complexity of Local Max-Cut (Almost) Completely. 171-182
  
• Tim Nonner:
  Clique Clustering Yields a PTAS for max-Coloring Interval Graphs. 183-194
  

Online Algorithms

• Leah Epstein, Csanád Imreh, Asaf Levin, Judit Nagy-György:
  On Variants of File Caching. 195-206
  
• Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic:
  On the Advice Complexity of the k-Server Problem. 207-218
  
• Sze-Hang Chan, Tak Wah Lam, Lap-Kei Lee, Chi-Man Liu, Hing-Fung Ting:
  Sleep Management on Multiple Machines for Energy and Flow Time. 219-231
  
• S. Anand, Naveen Garg, Nicole Megow:
  Meeting Deadlines: How Much Speed Suffices? 232-243
  

Data Structures, Distributed Computing

• Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson, Matthew Skala:
  Range Majority in Constant Time and Linear Space. 244-255
  
• Gerth Stølting Brodal, Konstantinos Tsakalidis:
  Dynamic Planar Range Maxima Queries. 256-267
  
• Arash Farzan, Shahin Kamali:
  Compact Navigation and Distance Oracles for Graphs with Small Treewidth. 268-280
  
• Martin Hirt, Vassilis Zikas:
  Player-Centric Byzantine Agreement. 281-292
  

Complexity, Randomness

• Eric Allender, Luke Friedman, William I. Gasarch:
  Limits on the Computational Power of Random Strings. 293-304
  
• Amin Coja-Oghlan, Angelica Y. Pachon-Pinzon:
  The Decimation Process in Random k-SAT. 305-316
  
• Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao:
  Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. 317-329
  
• Ryan O'Donnell, John Wright, Yuan Zhou:
  The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions. 330-341
  

Submodular Optimization, Matroids

• Moran Feldman, Joseph Naor, Roy Schwartz:
  Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract). 342-353
  
• Chandra Chekuri, Alina Ene:
  Submodular Cost Allocation Problem and Applications. 354-366
  
• Naonori Kakimura, Kazuhisa Makino:
  Robust Independence Systems. 367-378
  
• Ashwinkumar Badanidiyuru Varadaraja:
  Buyback Problem - Approximate Matroid Intersection with Cancellation Costs. 379-390
  

Cryptography, Learning

• Sebastian Faust, Krzysztof Pietrzak, Daniele Venturi:
  Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience. 391-402
  
• Sanjeev Arora, Rong Ge:
  New Algorithms for Learning in Presence of Errors. 403-415
  
• Ryan C. Harkins, John M. Hitchcock:
  Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. 416-423
  

Fixed Parameter Tractability

• Andrei A. Bulatov, Dániel Marx:
  Constraint Satisfaction Parameterized by Solution Size. 424-436
  
• Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
  Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. 437-448
  
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
  Subset Feedback Vertex Set Is Fixed-Parameter Tractable. 449-461
  
• Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger:
  Domination When the Stars Are Out. 462-473
  

Hardness of Approximation

• Per Austrin, Subhash Khot:
  A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. 474-485
  
• Uriel Feige, Daniel Reichman:
  Recoverable Values for Independent Sets. 486-497
  
• Fabian Kuhn, Monaldo Mastrolilli:
  Vertex Cover in Graphs with Locally Few Colors. 498-509
  
• Konstantin Makarychev, Maxim Sviridenko:
  Maximizing Polynomials Subject to Assignment Constraints. 510-520
  

Counting, Testing

• Leslie Ann Goldberg, Mark Jerrum:
  A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. 521-532
  
• Magnus Bordewich, Ross J. Kang:
  Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. 533-544
  
• Sourav Chakraborty, David García-Soriano, Arie Matsliah:
  Efficient Sample Extractors for Juntas with Applications. 545-556
  
• Hung Q. Ngo, Ely Porat, Atri Rudra:
  Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications - (Extended Abstract). 557-568
  

Complexity

• Lance Fortnow, Rahul Santhanam:
  Robust Simulations and Significant Separations. 569-580
  
• Andrew Drucker:
  A PCP Characterization of AM. 581-592
  
• Raphaël Clifford, Markus Jalsenius:
  Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model. 593-604
  

Proof Complexity

• Lei Huang, Toniann Pitassi:
  Automatizability and Simple Stochastic Games. 605-617
  
• Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
  Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds. 618-629
  
• Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov:
  Parameterized Bounded-Depth Frege Is Not Optimal. 630-641
  
• Jakob Nordström, Alexander A. Razborov:
  On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. 642-653
  

Sorting, Matchings, Paths

• Laurent Bulteau, Guillaume Fertin, Irena Rusu:
  Sorting by Transpositions Is Difficult. 654-665
  
• Chien-Chung Huang, Telikepalli Kavitha:
  Popular Matchings in the Stable Marriage Problem. 666-677
  
• Christine T. Cheng, Eric McDermid, Ichiro Suzuki:
  Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices. 678-689
  
• Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, Renato Fonseca F. Werneck:
  VC-Dimension and Shortest Path Algorithms. 690-699
  

Constraint Satisfaction, Algebraic Complexity

• Stefan Mengel:
  Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems - (Extended Abstract). 700-711
  
• Heng Guo, Pinyan Lu, Leslie G. Valiant:
  The Complexity of Symmetric Boolean Parity Holant Problems - (Extended Abstract). 712-723
  
• Maurice J. Jansen, Rahul Santhanam:
  Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. 724-735
  
• Eric Allender, Fengming Wang:
  On the Power of Algebraic Branching Programs of Width Two. 736-747
  

Steiner Problems, Clustering

• Carsten Moldenhauer:
  Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs. 748-759
  
• Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
  Steiner Transitive-Closure Spanners of Low-Dimensional Posets. 760-772
  
• Hu Ding, Jinhui Xu:
  Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere. 773-784
  
• Daniel Lokshtanov, Dániel Marx:
  Clustering with Local Restrictions. 785-797
  

Last update Wed May 23 00:50:06 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page