33. ICALP 2006: Venice, Italy

Invited Lectures

• Noga Alon, Asaf Shapira, Benny Sudakov:
  Additive Approximation for Edge-Deletion Problems (Abstract). 1-2
  

Graph Theory I

• Martin Grohe, Oleg Verbitsky:
  Testing Graph Isomorphism in Parallel by Playing a Game. 3-14
  
• Amin Coja-Oghlan, André Lanka:
  The Spectral Gap of Random Graphs with Given Expected Degrees. 15-26
  
• Douglas E. Carroll, Ashish Goel, Adam Meyerson:
  Embedding Bounded Bandwidth Graphs into l₁. 27-37
  
• Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
  On Counting Homomorphisms to Directed Acyclic Graphs. 38-49
  

Quantum Computing

• Ben Reichardt:
  Fault-Tolerance Threshold for a Distance-Three Quantum Code. 50-61
  
• Ronald de Wolf:
  Lower Bounds on Matrix Rigidity Via a Quantum Argument. 62-71
  
• Frédéric Magniez, Dominic Mayers, Michele Mosca, Harold Ollivier:
  Self-testing of Quantum Circuits. 72-83
  

Randomness

• Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai:
  Deterministic Extractors for Independent-Symbol Sources. 84-95
  
• Jaikumar Radhakrishnan:
  Gap Amplification in PCPs Using Lazy Random Walks. 96-107
  
• Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
  Stopping Times, Metrics and Approximate Counting. 108-119
  

Formal Languages

• Michal Kunc:
  Algebraic Characterization of the Finite Power Property. 120-131
  
• Turlough Neary, Damien Woods:
  P-completeness of Cellular Automaton Rule 110. 132-143
  
• Christos A. Kapoutsis:
  Small Sweeping 2NFAs Are Not Closed Under Complement. 144-156
  
• Mikolaj Bojanczyk, Mathias Samuelides, Thomas Schwentick, Luc Segoufin:
  Expressive Power of Pebble Automata. 157-168
  

Approximation Algorithms I

• R. Ravi, Mohit Singh:
  Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs. 169-180
  
• Naveen Garg, Amit Kumar:
  Better Algorithms for Minimizing Average Flow-Time on Related Machines. 181-190
  
• Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar:
  A Push-Relabel Algorithm for Approximating Degree Bounded MSTs. 191-201
  
• Satish Rao, Shuheng Zhou:
  Edge Disjoint Paths in Moderately Connected Graphs. 202-213
  

Approximation Algorithms II

• Leah Epstein, Asaf Levin:
  A Robust APTAS for the Classical Bin Packing Problem. 214-225
  
• Subhash Khot, Ashok Kumar Ponnuswami:
  Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. 226-237
  
• Rolf Harren:
  Approximating the Orthogonal Knapsack Problem for Hypercubes. 238-249
  

Graph Algorithms I

• Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn:
  A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs. 250-261
  
• Virginia Vassilevska, Ryan Williams, Raphael Yuster:
  Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems. 262-273
  
• Piotr Sankowski:
  Weighted Bipartite Matching in Matrix Multiplication Time. 274-285
  

Algorithms I

• Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano:
  Optimal Resilient Sorting and Searching in the Presence of Memory Faults. 286-298
  
• Kurt Mehlhorn, Ralf Osbild, Michael Sagraloff:
  Reliable and Efficient Computational Geometry Via Controlled Perturbation. 299-310
  
• Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, Luca Moscardelli:
  Tight Bounds for Selfish and Greedy Load Balancing. 311-322
  

Complexity I

• Arist Kojevnikov, Dmitry Itsykson:
  Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies. 323-334
  
• Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
  Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. 335-345
  
• Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
  The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. 346-357
  

Data Structures and Linear Algebra

• Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein:
  Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. 358-369
  
• Alexander Golynski:
  Optimal Lower Bounds for Rank and Select Indexes. 370-381
  
• Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios K. Tsakalidis, Kostas Tsichlas, Christos D. Zaroliagis:
  Dynamic Interpolation Search Revisited. 382-394
  
• Gudmund Skovbjerg Frandsen, Peter Frands Frandsen:
  Dynamic Matrix Rank. 395-406
  

Graphs

• Xin He, Huaming Zhang:
  Nearly Optimal Visibility Representations of Plane Graphs. 407-418
  
• Hristo Djidjev, Imrich Vrto:
  Planar Crossing Numbers of Genus g Graphs. 419-430
  
• Toshihiro Fujito:
  How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover. 431-442
  
• Guy Kortsarz, Zeev Nutov:
  Tight Approximation Algorithm for Connectivity Augmentation Problems. 443-452
  

Complexity II

• Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf:
  On the Bipartite Unique Perfect Matching Problem. 453-464
  
• John M. Hitchcock, Aduri Pavan:
  Comparing Reductions to NP-Complete Sets. 465-476
  
• Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani:
  Design Is as Easy as Optimization. 477-488
  
• Xi Chen, Xiaotie Deng:
  On the Complexity of 2D Discrete Fixed Point Problem. 489-500
  

Game Theory I

• Martin Gairing, Burkhard Monien, Karsten Tiemann:
  Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions. 501-512
  
• Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou:
  The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. 513-524
  
• Roberto Cominetti, José R. Correa, Nicolás E. Stier Moses:
  Network Games with Atomic Players. 525-536
  

Algorithms II

• David Doty, Jack H. Lutz, Satyadev Nandakumar:
  Finite-State Dimension and Real Arithmetic. 537-547
  
• Andreas Björklund, Thore Husfeldt:
  Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings. 548-559
  
• Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini:
  The Myriad Virtues of Wavelet Trees. 560-571
  

Game Theory II

• Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis:
  Atomic Congestion Games Among Coalitions. 572-583
  
• Bruno Codenotti, Luis Rademacher, Kasturi R. Varadarajan:
  Computing Equilibrium Prices in Exchange Economies with Tax Distortions. 584-595
  
• Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano, Carmine Ventre:
  New Constructions of Mechanisms with Verification. 596-607
  

Networks, Circuits and Regular Expressions

• Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo:
  On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations. 608-618
  
• Amos Korman, David Peleg:
  Dynamic Routing Schemes for General Graphs. 619-630
  
• Kei Uchizawa, Rodney J. Douglas, Wolfgang Maass:
  Energy Complexity and Entropy of Threshold Circuits. 631-642
  
• Philip Bille:
  New Algorithms for Regular Expression Matching. 643-654
  

Fixed Parameter Complexity and Approximation Algorithms

• Dániel Marx:
  A Parameterized View on Matroid Optimization Problems. 655-666
  
• Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, Srinath Sridhar:
  Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction. 667-678
  
• Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Heiko Schilling, Martin Skutella:
  Length-Bounded Cuts and Flows. 679-690
  

Graph Algorithms II

• Amin Coja-Oghlan:
  An Adaptive Spectral Heuristic for Partitioning Random Graphs. 691-702
  
• Jin-yi Cai, Vinay Choudhary:
  Some Results on Matchgates and Holographic Algorithms. 703-714
  
• Julián Mestre:
  Weighted Popular Matchings. 715-726
  

Last update Thu Feb 9 05:00:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page