@incollection{Courcelle/08,
AUTHOR = {Courcelle, Bruno},
TITLE = {Graph structure and monadic second-order logic: Language theoretical aspects},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {1-13},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Muthukrishnan/08,
AUTHOR = {Muthukrishnan, S.},
TITLE = {Internet ad auctions: Insights and directions},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {14-23},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Buchfuhrer-Umans/08,
AUTHOR = {Buchfuhrer, David and Umans, Christopher},
TITLE = {The complexity of Boolean formula minimization},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {24-35},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dachman-Soled-Lee-Malkin-Servedio-Wan-Wee/08,
AUTHOR = {Dachman-Soled, Dana and Lee, Homin K. and Malkin, Tal and Servedio, Rocco A. and Wan, Andrew and Wee, Hoeteck},
TITLE = {Optimal cryptographic hardness of learning monotone functions},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {36-47},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Boros-Elbassioni-Makino/08,
AUTHOR = {Boros, Endre and Elbassioni, Khaled and Makino, Kazuhisa},
TITLE = {On Berge multiplication for monotone Boolean dualization},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {48-59},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Saxena/08,
AUTHOR = {Saxena, Nitin},
TITLE = {Diagonal circuit identity testing and lower bounds},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {60-71},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Yin/08,
AUTHOR = {Yin, Yitong},
TITLE = {Cell-probe proofs and nondeterministic cell-probe complexity},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {72-83},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ruzic/08,
AUTHOR = {Ru{\v{z}}i{\'c}, Milan},
TITLE = {Constructing efficient dictionaries in close to sorting time},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {84-95},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Albers-Lauer/08,
AUTHOR = {Albers, Susanne and Lauer, Sonja},
TITLE = {On list update with locality of reference},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {96-107},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Blelloch-Vassilevska-Williams/08,
AUTHOR = {Blelloch, Guy E. and Vassilevska, Virginia and Williams, Ryan},
TITLE = {A new combinatorial approach for sparse graph problems},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {108-120},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_10},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Avin-Koucky-Lotker/08,
AUTHOR = {Avin, Chen and Kouck{\'y}, Michal and Lotker, Zvi},
TITLE = {How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {121-132},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_11},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chaintreau-Fraigniaud-Lebhar/08,
AUTHOR = {Chaintreau, Augustin and Fraigniaud, Pierre and Lebhar, Emmanuelle},
TITLE = {Networks become navigable as nodes move and forget},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {133-144},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_12},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Pritchard/08,
AUTHOR = {Pritchard, David},
TITLE = {Fast distributed computation of cuts via random circulations},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {145-160},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_13},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chebolu-Frieze-Melsted/08,
AUTHOR = {Chebolu, Prasad and Frieze, Alan and Melsted, P{\'a}ll},
TITLE = {Finding a maximum matching in a sparse random graph in $O(n)$ expected time},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {161-172},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cicalese-Laber/08,
AUTHOR = {Cicalese, Ferdinando and Laber, Eduardo Sany},
TITLE = {Function evaluation via linear programming in the priced information model},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {173-185},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_15},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Azar-Birnbaum-Karlin-Mathieu-Nguyen/08,
AUTHOR = {Azar, Yossi and Birnbaum, Benjamin and Karlin, Anna R. and Mathieu, Claire and Nguyen, C. Thach},
TITLE = {Improved approximation algorithms for budgeted allocations},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {186-197},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_16},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bjorklund-Husfeldt-Kaski-Koivisto/08,
AUTHOR = {Bj{\"o}rklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
TITLE = {The Travelling Salesman Problem in bounded degree graphs},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {198-209},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fomin-Villanger/08,
AUTHOR = {Fomin, Fedor V. and Villanger, Yngve},
TITLE = {Treewidth computation and extremal combinatorics},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {210-221},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Plaxton/08,
AUTHOR = {Plaxton, C. Greg},
TITLE = {Fast scheduling of weighted unit jobs with release times and deadlines},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {222-233},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_19},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jansen-Thole/08,
AUTHOR = {Jansen, Klaus and Th{\"o}le, Ralf},
TITLE = {Approximation algorithms for scheduling parallel jobs: Breaking the approximation ratio of 2},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {234-245},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_20},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Eisenbrand-Rothvoss/08,
AUTHOR = {Eisenbrand, Friedrich and Rothvo{\ss}, Thomas},
TITLE = {A PTAS for static priority real-time scheduling with resource augmentation},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {246-257},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_21},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alon-Hod/08,
AUTHOR = {Alon, Noga and Hod, Rani},
TITLE = {Optimal monotone encodings},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {258-270},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_22},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Iwama-Nishimura-Paterson-Raymond-Yamashita/08,
AUTHOR = {Iwama, Kazuo and Nishimura, Harumichi and Paterson, Mike and Raymond, Rudy and Yamashita, Shigeru},
TITLE = {Polynomial-time construction of linear network coding},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {271-282},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_23},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cheng-Wan/08,
AUTHOR = {Cheng, Qi and Wan, Daqing},
TITLE = {Complexity of decoding positive-rate Reed-Solomon codes},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {283-293},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_24},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fiala-Golovach-Kratochvil/08,
AUTHOR = {Fiala, Ji{\v{r}}{\'{i}} and Golovach, Petr A. and Kratochv{\'{i}}l, Jan},
TITLE = {Computational complexity of the distance constrained labeling problem for trees},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {294-305},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Pemmaraju-Srinivasan/08,
AUTHOR = {Pemmaraju, Sriram and Srinivasan, Aravind},
TITLE = {The randomized coloring procedure with symmetry-breaking},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {306-319},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chierichetti-Vattani/08,
AUTHOR = {Chierichetti, Flavio and Vattani, Andrea},
TITLE = {The local nature of list colorings for graphs of high girth},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {320-332},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_27},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kawarabayashi/08a,
AUTHOR = {Kawarabayashi, Ken-ichi},
TITLE = {Approximating list-coloring on a fixed surface},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {333-344},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_28},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Blaser-Hardt-Steurer/08,
AUTHOR = {Bl{\"a}ser, Markus and Hardt, Moritz and Steurer, David},
TITLE = {Asymptotically optimal hitting sets against polynomials},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {345-356},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_29},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Andoni-Krauthgamer/08,
AUTHOR = {Andoni, Alexandr and Krauthgamer, Robert},
TITLE = {The smoothed complexity of edit distance},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {357-369},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_30},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kao-Schweller/08,
AUTHOR = {Kao, Ming-Yang and Schweller, Robert},
TITLE = {Randomized self-assembly for approximate shapes},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {370-384},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_31},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dietzfelbinger-Pagh/08,
AUTHOR = {Dietzfelbinger, Martin and Pagh, Rasmus},
TITLE = {Succinct data structures for retrieval and approximate membership},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {385-396},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_32},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dimitrov-Plaxton/08,
AUTHOR = {Dimitrov, Nedialko B. and Plaxton, C. Greg},
TITLE = {Competitive weighted matching in transversal matroids},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {397-408},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_33},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bansal-Chan-Lam-Lee/08,
AUTHOR = {Bansal, Nikhil and Chan, Ho-Leung and Lam, Tak-Wah and Lee, Lap-Kei},
TITLE = {Scheduling for speed bounded processors},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {409-420},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Haeupler-Kavitha-Mathew-Sen-Tarjan/08,
AUTHOR = {Haeupler, Bernhard and Kavitha, Telikepalli and Mathew, Rogers and Sen, Siddhartha and Tarjan, Robert E.},
TITLE = {Faster algorithms for incremental topological ordering},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {421-433},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_35},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Frandsen-Sankowski/08,
AUTHOR = {Frandsen, Gudmund Skovbjerg and Sankowski, Piotr},
TITLE = {Dynamic normal forms and dynamic characteristic polynomial},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {434-446},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Phillips/08,
AUTHOR = {Phillips, Jeff M.},
TITLE = {Algorithms for $\epsilon$-approximations of terrains},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {447-458},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_37},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Laber-Molinaro/08,
AUTHOR = {Laber, Eduardo and Molinaro, Marco},
TITLE = {An approximation algorithm for binary searching in trees},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {459-471},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chekuri-Khanna/08,
AUTHOR = {Chekuri, Chandra and Khanna, Sanjeev},
TITLE = {Algorithms for 2-route cut problems},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {472-484},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_39},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Borradaile-Klein/08,
AUTHOR = {Borradaile, Glencora and Klein, Philip},
TITLE = {The two-edge connectivity survivable network problem in planar graphs},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {485-501},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_40},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Diakonikolas-Lee-Matulef-Servedio-Wan/08,
AUTHOR = {Diakonikolas, Ilias and Lee, Homin K. and Matulef, Kevin and Servedio, Rocco A. and Wan, Andrew},
TITLE = {Efficiently testing sparse $GF(2)$ polynomials},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {502-514},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_41},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Onak/08,
AUTHOR = {Onak, Krzysztof},
TITLE = {Testing properties of sets of points in metric spaces},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {515-526},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_42},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kale-Seshadhri/08,
AUTHOR = {Kale, Satyen and Seshadhri, C.},
TITLE = {An expansion tester for bounded degree graphs},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {527-538},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_43},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Yoshida-Ito/08,
AUTHOR = {Yoshida, Yuichi and Ito, Hiro},
TITLE = {Property testing on $k$-vertex-connectivity of graphs},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {539-550},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Razgon-OSullivan/08,
AUTHOR = {Razgon, Igor and O'Sullivan, Barry},
TITLE = {Almost 2-SAT is fixed-parameter tractable},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {551-562},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_45},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bodlaender-Downey-Fellows-Hermelin/08,
AUTHOR = {Bodlaender, Hans L. and Downey, Rodney G. and Fellows, Michael R. and Hermelin, Danny},
TITLE = {On problems without polynomial kernels},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {563-574},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_46},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Koutis/08,
AUTHOR = {Koutis, Ioannis},
TITLE = {Faster algebraic algorithms for path and packing problems},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {575-586},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_47},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Thurley-Weyer/08,
AUTHOR = {Chen, Yijia and Thurley, Marc and Weyer, Mark},
TITLE = {Understanding the complexity of induced subgraph isomorphisms},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {587-596},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_48},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dragan-Fomin-Golovach/08,
AUTHOR = {Dragan, Feodor F. and Fomin, Fedor V. and Golovach, Petr A.},
TITLE = {Spanners in sparse graphs},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {597-608},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_49},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Baswana-Gaur-Sen-Upadhyay/08,
AUTHOR = {Baswana, Surender and Gaur, Akshay and Sen, Sandeep and Upadhyay, Jayant},
TITLE = {Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {609-621},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Roditty-Shapira/08,
AUTHOR = {Roditty, Liam and Shapira, Asaf},
TITLE = {All-pairs shortest paths with a sublinear additive error},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {622-633},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_51},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Tedder-Corneil-Habib-Paul/08,
AUTHOR = {Tedder, Marc and Corneil, Derek and Habib, Michel and Paul, Christophe},
TITLE = {Simpler linear-time modular decomposition via recursive factorizing permutations},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {634-645},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_52},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bulatov/08,
AUTHOR = {Bulatov, Andrei A.},
TITLE = {The complexity of the counting constraint satisfaction problem},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {646-661},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_53},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Krokhin-Marx/08,
AUTHOR = {Krokhin, Andrei and Marx, D{\'a}niel},
TITLE = {On the hardness of losing weight},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {662-673},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_54},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lee-Mittal/08,
AUTHOR = {Lee, Troy and Mittal, Rajat},
TITLE = {Product theorems via semidefinite programming},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {674-685},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_55},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ben-Sasson-Harsha-Lachish-Matsliah/08,
AUTHOR = {Ben-Sasson, Eli and Harsha, Prahladh and Lachish, Oded and Matsliah, Arie},
TITLE = {Sound 3-query PCPPs are long},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {686-697},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_56},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Esparza-Gawlitza-Kiefer-Seidl/08,
AUTHOR = {Esparza, Javier and Gawlitza, Thomas and Kiefer, Stefan and Seidl, Helmut},
TITLE = {Approximative methods for monotone systems of min-max-polynomial equations},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {698-710},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Etessami-Wojtczak-Yannakakis/08,
AUTHOR = {Etessami, Kousha and Wojtczak, Dominik and Yannakakis, Mihalis},
TITLE = {Recursive stochastic games with positive rewards},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {711-723},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_58},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kahler-Wilke/08,
AUTHOR = {K{\"a}hler, Detlef and Wilke, Thomas},
TITLE = {Complementation, disambiguation, and determinization of B{\"u}chi automata unified},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {724-735},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_59},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Greco-Scarcello/08,
AUTHOR = {Greco, Gianluigi and Scarcello, Francesco},
TITLE = {Tree projections: Hypergraph games and minimality},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {736-747},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_60},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Porat-Rothschild/08,
AUTHOR = {Porat, Ely and Rothschild, Amir},
TITLE = {Explicit non-adaptive combinatorial group testing schemes},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {748-759},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_61},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guha-McGregor/08,
AUTHOR = {Guha, Sudipto and McGregor, Andrew},
TITLE = {Tight lower bounds for multi-pass stream computation via pass elimination},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {760-772},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_62},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Regev-Schiff/08,
AUTHOR = {Regev, Oded and Schiff, Liron},
TITLE = {Impossibility of a quantum speed-up with a faulty oracle},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {773-781},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_63},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hallgren-Harrow/08,
AUTHOR = {Hallgren, Sean and Harrow, Aram W.},
TITLE = {Superpolynomial speedups based on almost any quantum circuit},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {782-795},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_64},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fanelli-Flammini-Moscardelli/08,
AUTHOR = {Fanelli, Angelo and Flammini, Michele and Moscardelli, Luca},
TITLE = {The speed of convergence in congestion games under best-response dynamics},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {796-807},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_65},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Briest/08,
AUTHOR = {Briest, Patrick},
TITLE = {Uniform budgets and the envy-free pricing problem},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {808-819},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_66},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Christodoulou-Kovacs-Schapira/08,
AUTHOR = {Christodoulou, George and Kov{\'a}cs, Annam{\'a}ria and Schapira, Michael},
TITLE = {Bayesian combinatorial auctions},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {820-832},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_67},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Azar-Gamzu/08,
AUTHOR = {Azar, Yossi and Gamzu, Iftah},
TITLE = {Truthful unification framework for packing integer programs with choices},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {833-844},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_68},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kempe-Regev-Unger-de_Wolf/08,
AUTHOR = {Kempe, Julia and Regev, Oded and Unger, Falk and de Wolf, Ronald},
TITLE = {Upper bounds on the noise threshold for fault-tolerant quantum computing},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {845-856},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_69},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mhalla-Perdrix/08,
AUTHOR = {Mhalla, Mehdi and Perdrix, Simon},
TITLE = {Finding optimal flows efficiently},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {857-868},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_70},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Childs-Lee/08,
AUTHOR = {Childs, Andrew M. and Lee, Troy},
TITLE = {Optimal quantum adversary lower bounds for ordered search},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {869-880},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_71},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Eldar-Regev/08,
AUTHOR = {Eldar, Lior and Regev, Oded},
TITLE = {Quantum SAT for a qutrit-cinquit pair is QMA$_1$-complete},
BOOKTITLE = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'2008, Part I (Reykjavik, Iceland, July 7-11, 2008)},
SERIES = {LNCS},
VOLUME = {5125},
PAGES = {881-892},
YEAR = {2008},
EDITOR = {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
URL = {http://dx.doi.org/10.1007/978-3-540-70575-8_72},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}