A 17/8 approximation algorithm for rectangle tiling
Katarzyna Paluch

A 2^{O(n11/d)} time algorithm for ddimensional protein folding in the HPmodel
Bin Fu and Wei Wang

A faster algorithm for Minimum Cycle Basis of graphs
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch

A General Technique for Managing Strings in ComparisonDriven Data Structures
Gianni Franceschini, Roberto Grossi

A new algorithm for optimal constraint satisfaction and its implications
Ryan Williams

A polynomial quantum query lower bound for the set equality problem
Gatis Midrijanis

A PTAS for Embedding Hypergraph in a Cycle
Xiaotie Deng, Guojun Li

A Time Lower Bound for Satisfiability
Dieter van Melkebeek and Ran Raz

Algorithms for MultiProduct Pricing
Gagan Aggarwal and Tomas Feder and Rajeev Motwani and An Zhu

Almost optimal decentralized routing in longrange contact networks
Emmanuelle Lebhar and Nicolas Schabanel

An Analog Characterization of Computable Functions Over the Real Numbers
O. Bournez and E. Hainry

Approximating Longest Directed Paths and Cycles
Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and its Variants in Network Design
Raja Jothi, Balaji Raghavachari

Bounded fixedparameter tractability and log^{2} n nondeterministic bits
Joerg Flum, Martin Grohe, and Mark Weyer

Closest Pair Problems in Very High Dimensions
Piotr Indyk, Moshe Lewenstein, Ohad Lipsky and Ely Porat

Coloring semirandom graphs optimally
Amin CojaOghlan

Communication vs. Computation
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim and S Venkatesh

Competition Induced Preferential Attachment
Noam Berger, Christian Borgs, Jennifer Chayes, Raissa D`Souza, Robert Kleinberg

Complexity of Pseudoknot Prediction in Simple Models
Rune Bang Lyngsø

Computing quickly succinct tradeoff curves
Sergei Vassilvitskii, Mihalis Yannakakis

Coordination mechanisms
George Christodoulou, Elias Koutsoupias, Akash Nanavati

Definitions and Bounds for Selfhealing Key Distribution Schemes
Carlo Blundo, Paolo D`Arco, and Alfredo De Santis

Deterministic M2M Multicast in Radio Networks
Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin

Dynamic Price Sequence and Incentive Compatibility
Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew C Yao

Easily refutable subformulas of large random 3CNF formulas
Uriel Feige and Eran Ofek

Ecological Turing machines
Durand, Muchnik, Ushakov and Vereshchagin

Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities
Bruno Codenotti and Kasturi Varadarajan

Efficient Consistency Proofs on a Committed Database
Charles Rackoff, Rafail Ostrovsky, Adam Smith

Exact (exponential) algorithms for treewidth and minimum fillin
Fedor Fomin, Dieter Kratsch, Ioan Todinca

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Michael Alekhnovich, Edward A. Hirsch. Dmitry Itsykson

External memory algorithms for diameter and allpair shortestpaths on sparse graphs
Lars Arge, Ulrich Meyer, Laura Toma

Fairness to All While Downsizing
Bala Kalyanasundaram & Mahendran Velauthapillai

Fast parameterized algorithms for graphs on surfaces
Fedor Fomin, Dimitrios Thilikos

Further Improvements in Competitive Guarantees for QoS Buffering
M. Mahdian, N. Bansal, L. Fleischer, T. Kimbrel, B. Schieber, M. Sviridenko

Group Spreading: A Protocol for Provably Secure Distributed Name Service
Baruch Awerbuch and Christian Scheideler

Hardcore Measures for Uniform Mildly Hard Problems
Thomas Holenstein

Hardness of string similarity search and other indexing problems
S. Cenk Sahinalp, Andrey Utis

Improved Results for Data Migration and Open Shop Scheduling
Rajiv Gandhi and Magnus M. Halldorsson and Guy Kortsarz and Hadas Shachnai

LA and the Hajos Calculus
Michael Soltys

Learning a Hidden Subgraph
Noga Alon and Vera Asodi

Linear Taxes Suffice
Lisa Fleischer

Linear time list decoding in errorfree settings
Venkatesan Guruswami and Piotr Indyk

Locally consistent constraint satisfaction problems
Zdenek Dvorak, Daniel Kral, Ondrej Pangrac

Monotonicity Testing over Graph Products
Shirley Halevy and Eyal Kushilevitz

Nash Equilibria in Discrete Routing Games with Convex Latency Functions
Martin Gairing, Thomas Luecking, Marios Mavronicolas, Burkhard Monien, Manuel Rode

On Graph Problems in a SemiStreaming Model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang

On the power of Ambainis`s lower bounds
Shengyu Zhang

Online Scheduling of EqualLength Jobs: Randomization and Restarts Help
Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomas Tichy

Online Scheduling with Bounded Migration
Peter Sanders, Naveen Sivadasan, Martin Skutella

Optimal Website Design with the Constrained Subtree Selection Problem
Brent Heeringa and Micah Adler

Property testing of regular tree languages
Frederic Magniez and Michel de Rougemont

Propositional PSPACE Reasoning with Boolean Programs vs. Quantified Boolean Formulas
Alan Skelley

Quantum query complexity of some graph problems
Christoph Dürr, Mark Heiligman, Peter Høyer, Mehdi Mhalla

Regular solutions of language inequalities and well quasiorders
Michal Kunc

Selfish Unsplittable Flows
Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis

Simple Permutations Mix Well
Shlomo Hoory, Avner Magen, Steve Myers and Charles Rackoff

Solving TwoVariable Word Equations
Robert Dabrowski, Wojciech Plandowski

Some results on effective randomness
Wolfgang Merkle, Nenad Mihailovic, and Theodore A. Slaman

SublinearTime Approximation for Clustering via Random Sampling
Artur Czumaj and Christian Sohler

Succinct representation of Functions
J. Ian Munro and S. Srinivasa Rao

The complexity of partition functions
Andrei Bulatov and Martin Grohe

The blackbox complexity of nearestneighbor search
Robert Krauthgamer and James R. Lee

The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs
S. Nikoletseas, C. Raptopoulos and P. Spirakis

The MinimumEntropy Set Cover Problem
Eran Halperin and Richard M. Karp

The Power of Verification for OneParameter Agents
V. Auletta and R. De Prisco and P. Penna and P. Persiano

Transparent long proofs: A first PCP theorem for NP_{R}
Klaus Meer

Universality in Quantum Computation
Emmanuel Jeandel

Wavelength Assignment in Optical Networks with Fixed Fiber Capacity
Matthew Andrews and Lisa Zhang

Word problems on compressed words
Markus Lohrey
