Accepted Papers

(54 out of 217 submissions, sorted by first author)
  1. Nir Ailon and Bernard Chazelle
    Information Theory in Property Testing and Monotonicity Testing in Higher Dimension
  2. Nir Andelman, Yossi Azar and Motti Sorani
    Truthful Approximation Mechanisms for Scheduling Selfish Related Machines
  3. Vikraman Arvind and Thirumalai Chakravarthi Vijayaraghavan
    The Complexity of solving Linear Equations over a Finite Ring
  4. Nikhil Bansal and Kirk Pruhs
    Speed Scaling to Manage Temperature
  5. Surender Baswana, Vishrut Goyal and Sandeep Sen
    All-pairs nearly 2-approximate shortest-paths in O(n^2 polylog n) time
  6. Michael Benedikt and Luc Segoufin
    Regular tree-languages definable in FO
  7. Petra Berenbrink, Tom Friedetzky, Zengjian Hu and Russ Martin
    On Weighted Balls-into-bins Games
  8. Dietmar Berwanger and Giacomo Lenzi
    The variable hierarchy of the mu-calculus is strict
  9. Marcin Bienkowski, Miroslaw Dynia and Miroslaw Korzeniowski
    Improved Algorithms for Dynamic Page Migration
  10. Vittorio Bilò, Michele Flammini and Luca Moscardelli
    On Nash Equilibria in Non-Cooperative All-Optical Networks
  11. Manuel Bodirsky
    The core of a countably categorical structure
  12. Prosenjit Bose, Evangelos Kranakis, Pat Morin and Yihui Tang
    Approximate range mode and range median queries
  13. Ulrik Brandes and Daniel Fleischer
    Centrality Measures Based on Current Flow
  14. Tomas Brazdil, Antonin Kucera and Oldrich Strazovsky
    On the Decidability of Temporal Properties of Probabilistic Pushdown Automata
  15. Harry Buhrman, Ilan Newman, Hein Roehrig and Ronald de Wolf
    Robust Polynomials and Quantum Algorithms
  16. Harry Buhrman, Ilan Newman, Nikolai Vereshchagin and Lance Fortnow
    Increasing Kolmogorov Complexity
  17. Fabio Burderi and Antonio Restivo
    Varieties of Codes and Kraft Inequality
  18. Hubie Chen
    Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms
  19. Jianer Chen, Henning Fernau, Iyad Kanj and Ge Xia
    Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
  20. Josep Diaz, Xavier Perez, Maria Serna and Nicholas Charles Wormald
    Connectivity for wireless agents moving on a cycle or grid
  21. Benjamin Doerr
    Roundings Respecting Hard Constraints
  22. Petros Drineas, Ravi Kannan and Michael Mahoney
    Sampling Sub-problems of Heterogeneous Max-Cut Problems and Approximation Algorithms
  23. Zdeněk Dvořák, Vít Jelínek, Daniel Král', Jan Kynčl and Michael Saks
    Three Optimal Algorithms for Balls of Three Colors
  24. Lars Engebretsen and Jonas Holmerin
    More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP
  25. Kousha Etessami and Mihalis Yannakakis
    Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Non-linear equations
  26. Abraham D. Flaxman and Bartosz Przydatek
    Solving Medium-Density Subset Sum Problems in Expected Polynomial Time
  27. Gianni Franceschini
    Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves
  28. Christian Glaßer
    Polylog-Time Reductions Decrease Dot-Depth
  29. Gregor Gramlich and Georg Schnitger
    Minimizing NFA's and Regular Expressions
  30. Joachim Gudmundsson, Giri Narasimhan and Michiel Smid
    Fast pruning of geometric spanners
  31. Gus Gutoski and John Watrous
    Quantum Interactive Proofs with Competing Provers
  32. Frank Harary, Wolfgang Slany and Oleg Verbitsky
    On the Computational Complexity of the Forcing Chromatic Number
  33. Nicole Immorlica, Mohammad Mahdian and Vahab Mirrokni
    Cycle Cover with Short Cycles
  34. Emmanuel Jeandel
    Topological Automata
  35. Gerard Jennhwa Chang, Antonius J. J. Kloks, Jiping Liu and Sheng-Lung Peng
    The PIGs Full Monty -- A floor show of minimal separators
  36. Detlef Kähler, Ralf Küsters and Thomas Wilke
    Deciding Properties of Contract-Signing Protocols
  37. Michael Kaminski
    A lower bound on the complexity of polynomial multiplication over finite fields
  38. Telikepalli Kavitha and Kurt Mehlhorn
    A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs
  39. Andreas Krebs, Klaus-Jörn Lange and Stephanie Reifferscheid
    Characterizing TC0 in Terms of Infinite Groups
  40. Michal Kunc
    The power of commuting with finite sets of words
  41. Xiang-Yang Li and Zheng Sun
    Cost Sharing and Strategyproof Mechanisms for Set Cover Games
  42. Violetta Lonati and Massimiliano Goldwurm
    Pattern occurrences in multicomponent models
  43. Gregorio Malajovich and Klaus Meer
    Computing Multi-Homogeneous Bézout Numbers is Hard
  44. Wolfgang Merkle, Joseph Miller, Andre Nies, Jan Reimann and Frank Stephan
    Kolmogorov-Loveland Randomness and Stochasticity
  45. Graham P Oliver and Richard M Thomas
    Automatic presentations for finitely generated groups
  46. Victor Poupet
    Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods
  47. Sasanka Roy, Sandip Das and Subhas C. Nandy
    Shortest Monotone Descent Path Problem in Polyhedral Terrain
  48. Markus Schmidt
    Packet Buffering - Randomization Beats Deterministic Algorithms
  49. Amnon Ta-Shma and Eran Rom
    Improving the alphabet-size in high noise, almost optimal rate list decodable codes.
  50. Seiichiro Tani, Hirotada Kobayashi and Keiji Matsumoto
    Deterministic Leader Election via Distributed Quantum Computing
  51. Lidia Tendera
    Counting in the two variable guarded logic with transitivity
  52. Guillaume Theyssier
    How Common Can Be Universality for Cellular Automata
  53. Volker Weber and Thomas Schwentick
    Dynamic Complexity Theory Revisited
  54. Carsten Witt
    Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics