Publications of the cosec research group (von zur Gathen, Bonn-Aachen International Center for Information Technology)
Subject area: complexity theory (sorted by year)
Last generated: 13 May 2012, 03:35.
There is also a BibTeX file corresponding to this list.
The local PDFs contained in this page are included as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that these works are posted here electronically. It is understood that all persons copying any of these documents will adhere to the terms and constraints invoked by each copyright holder, and in particular use them only for noncommercial purposes. These works may not be posted elsewhere without the explicit written permission of the copyright holder.
2005
Kathrin Tofall (2005). Fourier Analysis for Polynomials over Finite Fields. Diplomarbeit, Universität Paderborn. Local PDF (12.5MB).
2004
Joachim von zur Gathen (2004). Arithmetic Circuits for Discrete Logarithms. In LATIN04, Martin Farach-Colton, editor, number 2976 in Lecture Notes in Computer Science, 557-566. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-540-21258-4. ISSN 0302-9743 (Print) 1611-3349 (Online). Link to electronic version. Local PDF (291KB).
2003
Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks & Igor Shparlinski (2003). Complexity of some arithmetic problems for binary polynomials. computational complexity 12(1/2), 23-47. Link to electronic version. Local PDF (399KB).
2002
Joachim von zur Gathen (2002). Review of: Donald E. Knuth, Selected Papers on Analysis of Algorithms. IEEE Annals of the History of Computing 24(2), 98-99.
Olaf Müller & Michael Nüsken (2002). Never Trust Victor: An Alternative Resettable Zero-Knowledge Proof System. In Progress in Cryptology - INDOCRYPT 2002, Alfred Menezes & Palash Sarkar, editors, number 2551 in Lecture Notes in Computer Science, 79-92. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-00263-4. ISSN 0302-9743. Abstract and electronic version.
2001
Olaf Müller (2001). Resettable Zero-Knowledge. Diplomarbeit, Universität Paderborn. Link to electronic version.
2000
Joachim von zur Gathen (2000). Algebra und Algorithmik. In Lexikon der Mathematik, Guido Walz, editor, 43-47. Spektrum Verlag, Heidelberg. ISBN 3-8274-0303-0. Book online (accessible only from uni-paderborn). Local PDF (188KB).
Joachim von zur Gathen & Igor Shparlinski (2000). The CREW PRAM complexity of modular inversion. SIAM Journal on Computing 29(6), 1839-1857. Link to electronic version. Local PDF (306KB).
1997
Joachim von zur Gathen & James R. Roche (1997). Polynomials with two values. Combinatorica 17(3), 345-362. Link to electronic version.
1995
K. Ma & J. von zur Gathen (1995). The computational complexity of recognizing permutation functions. computational complexity 5(1), 76-97. Link to electronic version.
1991
Joachim von zur Gathen (1991). Maximal Bilinear Complexity and Codes. Linear Algebra and its Applications 144, 49-61. Link to electronic version.
Joachim von zur Gathen & Gadiel Seroussi (1991). Boolean Circuits versus Arithmetic Circuits. Information and Computation 91, 142-154. Link to electronic version.
1988
Joachim von zur Gathen (1988). Algebraic complexity theory. Annual Review of Computer Science 3, 317-347. Link to electronic version.
1987
Joachim von zur Gathen (1987). Computing powers in parallel. SIAM Journal on Computing 16, 930-945. Link to electronic version.
Joachim von zur Gathen (1987). Feasible Arithmetic Computations: Valiant’s Hypothesis. Journal of Symbolic Computation 4, 137-172. Link to electronic version. Local PDF (414KB).
Joachim von zur Gathen (1987). Permanent and determinant. Linear Algebra and its Applications 96, 87-100. Link to electronic version.
1986
Joachim von zur Gathen (1986). Parallel Arithmetic computations: a survey. In Proceedings of the 12th International Symposium Mathematical Foundations of Computer Science 1986, Bratislava, Czechosolvakia, Jozef Gruska, Branislav Rovan & Juraj Wiedermann, editors, volume 233 of Lecture Notes in Computer Science, 93-112. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-16783-8. ISSN 0302-9743. Link to electronic version.
Joachim von zur Gathen (1986). Permanent and determinant. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, Ontario, Canada, 398-401. IEEE Computer Society Press, Washington DC. Final version in Linear Algebra and its Applications.
J. von zur Gathen & G. Seroussi (1986). Boolean Circuits versus Arithmetic Circuits. In Proc. 6th Int. Conf. Computer Science, Santiago, Chile, 171-184. Final version in Information and Computation.
1983
J. von zur Gathen & V. Strassen (1983). Некоторюе многочленю, имеющие бюсокую сложност вючисления Some polynomials that are hard to compute. (Russian). Kiberneticeskij sbornik, Nov. Ser. 20 59-63. Local PDF (2.1MB).
1980
J. von zur Gathen & V. Strassen (1980). Some polynomials that are hard to compute. Theoretical Computer Science 11, 331-335. Link to electronic version. Local PDF (2.0MB).
1978
Joachim von zur Gathen & Malte Sieveking (1978). A bound on solutions of linear integer equalities and inequalities. Proceedings of the American Mathematical Society 72(1), 155-158. Link to electronic version. Local PDF (97KB).
1976
J. von zur Gathen & M. Sieveking (1976). Weitere zum Erfüllungsproblem polynomial äquivalente kombinatorische Aufgaben. In Komplexität von Entscheidungsproblemen, number 43 in Lecture Notes in Computer Science, 49-71. Springer-Verlag. Link to electronic version. Local PDF (527KB).