@incollection{Shokrollahi/00,
AUTHOR = {Shokrollahi, M. Amin},
TITLE = {Codes and graphs},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {1-12},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Henzinger-Majumdar/00,
AUTHOR = {Henzinger, Thomas A. and Majumdar, Rupak},
TITLE = {A classification of symbolic transition systems},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {13-34},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Koiran/00a,
AUTHOR = {Koiran, Pascal},
TITLE = {Circuits versus trees in algebraic complexity},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {35-52},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Deshmukh-Shankar-Dasgupta-Rajan/00,
AUTHOR = {Deshmukh, Kaustubh and Shankar, Priti and Dasgupta, Amitava and Rajan, B. Sundar},
TITLE = {On the many faces of block codes},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {53-64},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Hirsch/00a,
AUTHOR = {Hirsch, Edward A.},
TITLE = {A new algorithm for MAX-2-SAT},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {65-73},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Lutz-Strauss/00,
AUTHOR = {Lutz, Jack H. and Strauss, Martin J.},
TITLE = {Bias invariance of small upper spans},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {74-86},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Allender-Mahajan/00,
AUTHOR = {Allender, Eric and Mahajan, Meena},
TITLE = {The complexity of planarity testing},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {87-98},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Richomme-Wlazinski/00,
AUTHOR = {Richomme, Gw{\'{e}}na{\"e}l and Wlazinski, Francis},
TITLE = {About cube-free morphisms},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {99-109},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Kari/00,
AUTHOR = {Kari, Jarkko},
TITLE = {Linear cellular automata with multiple state variables},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {110-121},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Ilie-Plandowski/00,
AUTHOR = {Ilie, Lucian and Plandowski, Wojciech},
TITLE = {Two-variable word equations},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {122-132},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Ambainis-Wolf/00,
AUTHOR = {Ambainis, Andris and Wolf, Ronald de},
TITLE = {Average-case quantum query complexity},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {133-144},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Hromkovic-Sauerhoff/00,
AUTHOR = {Hromkovi{\v{c}}, Juraj and Sauerhoff, Martin},
TITLE = {Tradeoffs between nondeterminism and complexity for communication protocols and branching programs},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {145-156},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Kosub-Wagner/00,
AUTHOR = {Kosub, Sven and Wagner, Klaus W.},
TITLE = {The Boolean hierarchy of $NP$-partitions},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {157-168},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Al-Ammal-Goldberg-Mackenzie/00,
AUTHOR = {Al-Ammal, Hesham and Goldberg, Leslie Ann and Mackenzie, Phil},
TITLE = {Binary exponential backoff is stable for high arrival rates},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {169-180},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=1770&spage=169},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Schabanel/00,
AUTHOR = {Schabanel, Nicolas},
TITLE = {The data broadcast problem with preemption},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {181-192},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Fong-Strauss/00,
AUTHOR = {Fong, Jessica H. and Strauss, Martin J.},
TITLE = {An approximate $\L^p$-difference algorithm for massive data streams},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {193-204},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Penna/00,
AUTHOR = {Penna, Paolo},
TITLE = {Succinct representations of model based belief revision},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {205-216},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Libkin/00,
AUTHOR = {Libkin, Leonid},
TITLE = {Logics capturing local properties},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {217-229},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Hemaspaandra/00,
AUTHOR = {Hemaspaandra, Edith},
TITLE = {The complexity of poor man's logic},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {230-241},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Han/00,
AUTHOR = {Han, Yijie},
TITLE = {Fast integer sorting in linear space},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {242-253},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Edelkamp-Wegener/00,
AUTHOR = {Edelkamp, Stefan and Wegener, Ingo},
TITLE = {On the performance of WEAK-HEAPSORT},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {254-266},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Aceto-Esik-Ingolfsdottir/00,
AUTHOR = {Aceto, Luca and {\'{E}}sik, Zolt{\'{a}}n and Ing{\'{o}}lfsd{\'{o}}ttir, Anna},
TITLE = {On the two-variable fragment of the equational theory of the Max-Sum algebra of the natural numbers},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {267-278},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Dima/00,
AUTHOR = {Dima, C{\u{a}}talin},
TITLE = {Real-time automata and the Kleene algebra of sets of real numbers},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {279-289},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Jurdzinski/00,
AUTHOR = {Jurdzi{\'n}ski, Marcin},
TITLE = {Small progress measures for solving parity games},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {290-301},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Magniez/00,
AUTHOR = {Magniez, Fr{\'{e}}d{\'{e}}ric},
TITLE = {Multi-linearity self-testing with relative error},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {302-313},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Arvind-Kobler-Mundhenk-Toran/00,
AUTHOR = {Arvind, Vikraman and K{\"o}bler, Johannes and Mundhenk, Martin and Tor{\'{a}}n, Jacobo},
TITLE = {Nondeterministic instance complexity and hard-to-prove tautologies},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {314-323},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Lutz-Mhetre-Srinivasan/00,
AUTHOR = {Lutz, Jack H. and Mhetre, Vikram and Srinivasan, Sridhar},
TITLE = {Hard instances of hard problems},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {324-333},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Jancar-Kucera-Moller/00,
AUTHOR = {Jan{\v{c}}ar, Petr and Ku{\v{c}}era, Anton{\'{i}}n and Moller, Faron},
TITLE = {Simulation and bisimulation over one-counter processes},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {334-345},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Finkel-Sutre/00,
AUTHOR = {Finkel, Alain and Sutre, Gr{\'{e}}goire},
TITLE = {Decidability of reachability problems for classes of two counters automata},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {346-357},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Jurdzinski-Nielsen/00,
AUTHOR = {Jurdzi{\'n}ski, Marcin and Nielsen, Mogens},
TITLE = {Hereditary history preserving bisimilarity is undecidable},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {358-369},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Elkin-Peleg/00,
AUTHOR = {Elkin, Michael and Peleg, David},
TITLE = {The hardness of approximating spanner problems},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {370-381},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Bockenhauer-Hromkovic-Klasing-Seibert-Unger/00b,
AUTHOR = {B{\"o}ckenhauer, Hans-Joachim and Hromkovi{\v{c}}, Juraj and Klasing, Ralf and Seibert, Sebastian and Unger, Walter},
TITLE = {An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {382-394},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Bodlaender-Kloks-Tan-Leeuwen/00,
AUTHOR = {Bodlaender, Hans L. and Kloks, Ton and Tan, Richard B. and Leeuwen, Jan van},
TITLE = {$\lambda$-coloring of graphs},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {395-406},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Buhrman-Fenner-Fortnow-Melkebeek/00,
AUTHOR = {Buhrman, Harry and Fenner, Steve and Fortnow, Lance and Melkebeek, Dieter van},
TITLE = {Optimal proof systems and sparse sets},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {407-418},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Ambos-Spies-Merkle-Reimann-Terwijn/00,
AUTHOR = {Ambos-Spies, Klaus and Merkle, Wolfgang and Reimann, Jan and Terwijn, Sebastiaan A.},
TITLE = {Almost complete sets},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {419-430},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Arvind-Kobler/00,
AUTHOR = {Arvind, Vikraman and K{\"o}bler, Johannes},
TITLE = {Graph isomorphism is low for $ZPP(NP)$ and other lowness results},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {431-442},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Bampis-Giroudeau-Konig/00,
AUTHOR = {Bampis, Evripidis and Giroudeau, Rodolphe and K{\"o}nig, Jean-Claude},
TITLE = {An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {443-454},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Jansen-Sviridenko/00,
AUTHOR = {Jansen, Klaus and Sviridenko, Maxim I.},
TITLE = {Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {455-465},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Lorenz/00,
AUTHOR = {Lorenz, Ulf},
TITLE = {Controlled conspiracy-2 search},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {466-478},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Blondel-Bournez-Koiran-Tsitsiklis/00,
AUTHOR = {Blondel, Vincent D. and Bournez, Olivier and Koiran, Pascal and Tsitsiklis, John N.},
TITLE = {The stability of saturated linear dynamical systems is undecidable},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {479-490},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Cervelle-Durand/00,
AUTHOR = {Cervelle, Julien and Durand, Bruno},
TITLE = {Tilings: Recursivity and regularity},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {491-502},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Bouchitte-Todinca/00,
AUTHOR = {Bouchitt{\'{e}}, Vincent and Todinca, Ioan},
TITLE = {Listing all potential maximal cliques of a graph},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {503-515},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Katz-Katz-Peleg/00,
AUTHOR = {Katz, Michal and Katz, Nir A. and Peleg, David},
TITLE = {Distance labeling schemes for well-separated graph classes},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {516-528},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Lanlignel-Raynaud-Thierry/00,
AUTHOR = {Lanlignel, Jean-Marc and Raynaud, Olivier and Thierry, Eric},
TITLE = {Pruning graphs with digital search trees --- Application to distance hereditary graphs},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {529-541},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Engelfriet-Maneth/00,
AUTHOR = {Engelfriet, Joost and Maneth, Sebastian},
TITLE = {Characterizing and deciding MSO-definability of macro tree transductions},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {542-554},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Glasser-Schmitz/00,
AUTHOR = {Gla{\"ss}er, Christian and Schmitz, Heinz},
TITLE = {Languages of dot-depth 3/2},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {555-566},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Bertoni-Goldwurm-Santini/00,
AUTHOR = {Bertoni, Alberto and Goldwurm, Massimiliano and Santini, Massimo},
TITLE = {Random generation and approximate counting of ambiguously described combinatorial structures},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {567-580},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Koutsoupias-Taylor/00,
AUTHOR = {Koutsoupias, Elias and Taylor, David Scot},
TITLE = {The CNN problem and other $k$-server variants},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {581-592},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Chrobak-Sgall/00a,
AUTHOR = {Chrobak, Marek and Sgall, Ji{\v{r}}{\'{i}}},
TITLE = {The weighted 2-server problem},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {593-604},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Bartal-Koutsoupias/00,
AUTHOR = {Bartal, Yair and Koutsoupias, Elias},
TITLE = {On the competitive ratio of the work function algorithm for the $k$-server problem},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {605-613},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Goldmann-Russell/00,
AUTHOR = {Goldmann, Mikael and Russell, Alexander},
TITLE = {Spectral bounds on general hard core predicates},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {614-625},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{de_Bonis-Santis/00,
AUTHOR = {de Bonis, Annalisa and Santis, Alfredo de},
TITLE = {Randomness in visual cryptography},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {626-638},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Ascheuer-Krumke-Rambau/00,
AUTHOR = {Ascheuer, Norbert and Krumke, Sven O. and Rambau, J{\"o}rg},
TITLE = {Online dial-a-ride problems: Minimizing the completion time},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {639-650},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}
@incollection{Clementi-Penna-Silvestri/00,
AUTHOR = {Clementi, Andrea E.F. and Penna, Paolo and Silvestri, Riccardo},
TITLE = {The power range assignment problem in radio networks on the plane},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS'2000 (Lille, France, February 17-19, 2000)},
SERIES = {LNCS},
VOLUME = {1770},
PAGES = {651-660},
YEAR = {2000},
EDITOR = {Reichel, Horst and Tison, Sophie},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapore-Tokyo},
}