@incollection{Agrawal-Saxena/05,
AUTHOR = {Agrawal, Manindra and Saxena, Nitin},
TITLE = {Automorphisms of finite rings and applications to complexity of problems},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {1-17},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Bousquet-Melou/05,
AUTHOR = {Bousquet-M{\'e}lou, Mireille},
TITLE = {Algebraic generating functions in enumerative combinatorics and context-free languages},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {18-35},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Schoning/05,
AUTHOR = {Sch{\"o}ning, Uwe},
TITLE = {Algorithmics in exponential time},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {36-43},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Witt/05,
AUTHOR = {Witt, Carsten},
TITLE = {Worst-case and average-case approximations by simple randomized search heuristics},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {44-56},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Drineas-Kannan-Mahoney/05,
AUTHOR = {Drineas, Petros and Kannan, Ravi and Mahoney, Michael W.},
TITLE = {Sampling sub-problems of heterogeneous max-cut problems and approximation algorithms},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {57-68},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Andelman-Azar-Sorani/05,
AUTHOR = {Andelman, Nir and Azar, Yossi and Sorani, Motti},
TITLE = {Truthful approximation mechanisms for scheduling selfish related machines},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {69-82},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=69},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Tendera/05,
AUTHOR = {Tendera, Lidia},
TITLE = {Counting in the two variable guarded logic with transitivity},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {83-96},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {guarded fragment, counting, transitivity, decision problem, computational complexity},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=83},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Berwanger-Lenzi/05,
AUTHOR = {Berwanger, Dietmar and Lenzi, Giacomo},
TITLE = {The variable hierarchy of the $\mu$-calculus is strict},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {97-109},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {$\mu$-calculus, structural complexity.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=97},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Bodirsky/05,
AUTHOR = {Bodirsky, Manuel},
TITLE = {The core of a countably categorical structure},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {110-120},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=110},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Theyssier/05,
AUTHOR = {Theyssier, Guillaume},
TITLE = {How common can be universality for cellular automata?},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {121-132},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {cellular automata, universality, zero-one law},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=121},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Poupet/05,
AUTHOR = {Poupet, Victor},
TITLE = {Cellular automata: Real-time equivalence between one-dimensional neighborhoods},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {133-144},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {cellular automata, neighborhoods, real-time},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=133},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Brazdil-Kucera-Strazovsky/05,
AUTHOR = {Br{\'a}zdil, Tom{\'a}{\v{s}} and Ku{\v{c}}era, Anton{\'{i}}n and Stra{\v{z}}ovsk{\'y}, Old{\v{r}}ich},
TITLE = {On the decidability of temporal properties of probabilistic pushdown automata},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {145-157},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=145},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Kahler-Kusters-Wilke/05,
AUTHOR = {K{\"a}hler, Detlef and K{\"u}sters, Ralf and Wilke, Thomas},
TITLE = {Deciding properties of contract-signing protocols},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {158-169},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=158},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Glasser/05,
AUTHOR = {Gla{\ss}er, Christian},
TITLE = {Polylog-time reductions decrease dot-depth},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {170-181},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=170},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Harary-Slany-Verbitsky/05,
AUTHOR = {Harary, Frank and Slany, Wolfgang and Verbitsky, Oleg},
TITLE = {On the computational complexity of the forcing chromatic number},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {182-193},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=182},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Engebretsen-Holmerin/05,
AUTHOR = {Engebretsen, Lars and Holmerin, Jonas},
TITLE = {More efficient queries in PCPs for $NP$ and improved approximation hardness of maximum CSP},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {194-205},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=194},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Dvorak-Jelinek-Kral-Kyncl-Saks/05,
AUTHOR = {Dvo{\v{r}}{\'a}k, Zdenk and Jel{\'{i}}nek, V{\'{i}}t and Kr{\'a}l', Daniel and Kyn{\v{c}}l, Jan and Saks, Michael},
TITLE = {Three optimal algorithms for balls of three colors},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {206-217},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=206},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Li-Sun-Wang/05,
AUTHOR = {Li, Xiang-Yang and Sun, Zheng and Wang, Weizhao},
TITLE = {Cost sharing and strategyproof mechanisms for set cover games},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {218-230},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=218},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Berenbrink-Friedetzky-Hu-Martin/05,
AUTHOR = {Berenbrink, Petra and Friedetzky, Tom and Hu, Zengjian and Martin, Russell},
TITLE = {On weighted balls-into-bins games},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {231-243},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=231},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Malajovich-Meer/05,
AUTHOR = {Malajovich, Gregorio and Meer, Klaus},
TITLE = {Computing minimal multi-homogeneous B{\'e}zout numbers is hard},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {244-255},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=244},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Weber-Schwentick/05,
AUTHOR = {Weber, Volker and Schwentick, Thomas},
TITLE = {Dynamic complexity theory revisited},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {256-268},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=256},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Chen-Fernau-Kanj-Xia/05,
AUTHOR = {Chen, Jianer and Fernau, Henning and Kanj, Iyad A. and Xia, Ge},
TITLE = {Parametric duality and kernelization: Lower bounds and upper bounds on kernel size},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {269-280},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {kernelization, parameterized complexity},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=269},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Roy-Das-Nandy/05,
AUTHOR = {Roy, Sasanka and Das, Sandip and Nandy, Subhas C.},
TITLE = {Shortest monotone descent path problem in polyhedral terrain},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {281-292},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=281},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Schmidt/05,
AUTHOR = {Schmidt, Markus},
TITLE = {Packet buffering: Randomization beats deterministic algorithms},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {293-304},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=293},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Flaxman-Przydatek/05,
AUTHOR = {Flaxman, Abraham D. and Przydatek, Bartosz},
TITLE = {Solving medium-density subset sum problems in expected polynomial time},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {305-314},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=305},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Chen/05a,
AUTHOR = {Chen, Hubie},
TITLE = {Quantified constraint satisfaction, maximal constraint languages, and symmetric polymorphisms},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {315-326},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=315},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Benedikt-Segoufin/05,
AUTHOR = {Benedikt, Michael and Segoufin, Luc},
TITLE = {Regular tree languages definable in $FO$},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {327-339},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {tree automata, logic},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=327},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Etessami-Yannakakis/05,
AUTHOR = {Etessami, Kousha and Yannakakis, Mihalis},
TITLE = {Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {340-352},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=340},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Diaz-Perez-Serna-Wormald/05,
AUTHOR = {D{\'{i}}az, Josep and P{\'e}rez, Xavier and Serna, Maria J. and Wormald, Nicholas C.},
TITLE = {Connectivity for wireless agents moving on a cycle or grid},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {353-364},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=353},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Bienkowski-Dynia-Korzeniowski/05,
AUTHOR = {Bienkowski, Marcin and Dynia, Miroslaw and Korzeniowski, Miroslaw},
TITLE = {Improved algorithms for dynamic page migration},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {365-376},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=365},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Bose-Kranakis-Morin-Tang/05,
AUTHOR = {Bose, Prosenjit and Kranakis, Evangelos and Morin, Pat and Tang, Yihui},
TITLE = {Approximate range mode and range median queries},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {377-388},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=377},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Jeandel/05,
AUTHOR = {Jeandel, Emmanuel},
TITLE = {Topological automata},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {389-398},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {finite automata, formal languages, probabilistic automata, quantum automata},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=389},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Gramlich-Schnitger/05,
AUTHOR = {Gramlich, Gregor and Schnitger, Georg},
TITLE = {Minimizing NFA's and regular expressions},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {399-411},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {automata and formal languages, computational complexity, approximability},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=399},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Buhrman-Fortnow-Newman-Vereshchagin/05,
AUTHOR = {Buhrman, Harry and Fortnow, Lance and Newman, Ilan and Vereshchagin, Nikolai},
TITLE = {Increasing Kolmogorov complexity},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {412-421},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {kolmogorov complexity, computational complexity},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=412},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Merkle-Miller-Nies-Reimann-Stephan/05,
AUTHOR = {Merkle, Wolfgang and Miller, Joseph and Nies, Andr{\'e} and Reimann, Jan and Stephan, Frank},
TITLE = {Kolmogorov-Loveland randomness and stochasticity},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {422-433},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=422},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Ailon-Chazelle/05a,
AUTHOR = {Ailon, Nir and Chazelle, Bernard},
TITLE = {Information theory in property testing and monotonicity testing in higher dimension},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {434-447},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=434},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Bil-Flammini-Moscardelli/05,
AUTHOR = {Bil, Vittorio and Flammini, Michele and Moscardelli, Luca},
TITLE = {On Nash equilibria in non-cooperative all-optical networks},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {448-459},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=448},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Bansal-Pruhs/05,
AUTHOR = {Bansal, Nikhil and Pruhs, Kirk},
TITLE = {Speed scaling to manage temperature},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {460-471},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=460},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Arvind-Vijayaraghavan/05,
AUTHOR = {Arvind, V. and Vijayaraghavan, T.C.},
TITLE = {The complexity of solving linear equations over a finite ring},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {472-484},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=472},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Kaminski/05,
AUTHOR = {Kaminski, Michael},
TITLE = {A lower bound on the complexity of polynomial multiplication over finite fields},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {485-495},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=485},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Krebs-Lange-Reifferscheid/05,
AUTHOR = {Krebs, Andreas and Lange, Klaus-J{\"o}rn and Reifferscheid, Stephanie},
TITLE = {Characterizing $TC^0$ in terms of infinite groups},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {496-507},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=496},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Gudmundsson-Narasimhan-Smid/05,
AUTHOR = {Gudmundsson, Joachim and Narasimhan, Giri and Smid, Michiel},
TITLE = {Fast pruning of geometric spanners},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {508-520},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=508},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Chang-Kloks-Liu-Peng/05,
AUTHOR = {Chang, Gerard Jennhwa and Kloks, Antonius J.J. and Liu, Jiping and Peng, Sheng-Lung},
TITLE = {The PIGs full monty --- A floor show of minimal separators},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {521-532},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {algorithms and data structures, algorithms for computational biology},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=521},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Brandes-Fleischer/05,
AUTHOR = {Brandes, Ulrik and Fleischer, Daniel},
TITLE = {Centrality measures based on current flow},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {533-544},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=533},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Burderi-Restivo/05,
AUTHOR = {Burderi, Fabio and Restivo, Antonio},
TITLE = {Varieties of codes and Kraft inequality},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {545-556},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=545},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Rom-Ta-Shma/05,
AUTHOR = {Rom, Eran and Ta-Shma, Amnon},
TITLE = {Improving the alphabet-size in high noise, almost optimal rate list decodable codes},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {557-568},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=557},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Kunc/05,
AUTHOR = {Kunc, Michal},
TITLE = {The power of commuting with finite sets of words},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {569-580},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=569},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Tani-Kobayashi-Matsumoto/05,
AUTHOR = {Tani, Seiichiro and Kobayashi, Hirotada and Matsumoto, Keiji},
TITLE = {Exact quantum algorithms for the leader election problem},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {581-592},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=581},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Buhrman-Newman-Rohrig-de_Wolf/05,
AUTHOR = {Buhrman, Harry and Newman, Ilan and R{\"o}hrig, Hein and de Wolf, Ronald},
TITLE = {Robust polynomials and quantum algorithms},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {593-604},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=593},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Gutoski-Watrous/05,
AUTHOR = {Gutoski, Gus and Watrous, John},
TITLE = {Quantum interactive proofs with competing provers},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {605-616},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=605},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Doerr/05,
AUTHOR = {Doerr, Benjamin},
TITLE = {Roundings respecting hard constraints},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {617-628},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=617},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Franceschini/05,
AUTHOR = {Franceschini, Gianni},
TITLE = {Sorting stably, in-place, with $O(n \log n)$ comparisons and $O(n)$ moves},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {629-640},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=629},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Immorlica-Mahdian-Mirrokni/05,
AUTHOR = {Immorlica, Nicole and Mahdian, Mohammad and Mirrokni, Vahab S.},
TITLE = {Cycle cover with short cycles},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {641-653},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=641},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Kavitha-Mehlhorn/05,
AUTHOR = {Kavitha, Telikepalli and Mehlhorn, Kurt},
TITLE = {A polynomial time algorithm for minimum cycle basis in directed graphs},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {654-665},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=654},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Baswana-Goyal-Sen/05,
AUTHOR = {Baswana, Surender and Goyal, Vishrut and Sen, Sandeep},
TITLE = {All-pairs nearly 2-approximate shortest-paths in $O(n^2 polylog n)$ time},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {666-679},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=666},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Goldwurm-Lonati/05,
AUTHOR = {Goldwurm, Massimiliano and Lonati, Violetta},
TITLE = {Pattern occurrences in multicomponent models},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {680-692},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
KEYWORDS = {automata and formal languages, limit distributions, nonnegative matrices, pattern statistics, rational formal series},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=680},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}
@incollection{Oliver-Thomas/05,
AUTHOR = {Oliver, Graham P. and Thomas, Richard M.},
TITLE = {Automatic presentations for finitely generated groups},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2005 (Stuttgart, Germany, February 24-26, 2005)},
SERIES = {LNCS},
VOLUME = {3404},
PAGES = {693-704},
YEAR = {2005},
EDITOR = {Diekert, Volker and Durand, Bruno},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3404&spage=693},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York},
}