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