A 17/8 approximation algorithm for rectangle tiling
Katarzyna Paluch
|
A 2O(n1-1/d) time algorithm for d-dimensional protein folding in the HP-model
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 Comparison-Driven 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 Multi-Product Pricing
Gagan Aggarwal and Tomas Feder and Rajeev Motwani and An Zhu
|
Almost optimal decentralized routing in long-range 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 fixed-parameter tractability and log2 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 Coja-Oghlan
|
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 trade-off curves
Sergei Vassilvitskii, Mihalis Yannakakis
|
|
Coordination mechanisms
George Christodoulou, Elias Koutsoupias, Akash Nanavati
|
Definitions and Bounds for Self-healing 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 fill-in
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 all-pair shortest-paths 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
|
Hard-core 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 error-free 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 Semi-Streaming Model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang
|
On the power of Ambainis`s lower bounds
Shengyu Zhang
|
Online Scheduling of Equal-Length 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 quasi-orders
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 Two-Variable Word Equations
Robert Dabrowski, Wojciech Plandowski
|
Some results on effective randomness
Wolfgang Merkle, Nenad Mihailovic, and Theodore A. Slaman
|
Sublinear-Time 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 black-box complexity of nearest-neighbor 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 Minimum-Entropy Set Cover Problem
Eran Halperin and Richard M. Karp
|
The Power of Verification for One-Parameter Agents
V. Auletta and R. De Prisco and P. Penna and P. Persiano
|
Transparent long proofs: A first PCP theorem for NPR
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
|
