Jan Arpe - Publications

• Research articles
• Theses
• Miscellaneous

Research articles

[J] - Journal article
[C] - Conference article
[T] - Technical report
[P] - Preprint

Multiple Random Oracles Are Better Than One
Jan Arpe and Elchanan Mossel

[P]	Version from April 23, 2008. arXiv:0804.3817v1.

When Does Greedy Learning of Relevant Features Succeed?
- A Fourier-based Characterization -
Jan Arpe and Rüdiger Reischuk

[C]	In Guohui Lin (ed.): Computing and Combinatroics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings. Volume 4598 of Lecture Notes in Computer Science (LNCS), pp. 296-306. Springer, 2007.
[T]	Electronic Colloquium on Computational Complexity Report ECCC-TR06-065, May 2006.
[P]	Version from May 2006.

Approximability of Minimum AND-Circuits
Jan Arpe and Bodo Manthey

[J]	To appear in Algorithmica. Available online since September 2007.
[C]	In Lars Arge, Rusins Freivalds (eds.): Algorithm Theory -- SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 2006, Proceedings. Volume 4059 of Lecture Notes in Computer Science (LNCS), pp. 292-303. Springer, 2006.
[T]	Electronic Colloquium on Computational Complexity Report ECCC-TR06-045, March 2006.
[P]	Version from March 10, 2006.

Learning Juntas in the Presence of Noise
Jan Arpe and Rüdiger Reischuk

[J]	Theoret. Comput. Sci. 384(1):2-21 (2007). Special issue of TAMC 2006.
[C]	In Jin-Yi Cai, S. Barry Cooper, Angsheng Li (eds.): Theory and Applications of Models of Computation: Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006. Proceedings. Volume 3959 of Lecture Notes in Computer Science (LNCS), pp. 387-398. Springer, 2006.
[T]	Electronic Colloquium on Computational Complexity Report ECCC-TR05-088, August 2005.
[P]	Version from January 2007.

On the Complexity of Grammar-Based Compression
Jan Arpe and Rüdiger Reischuk

[C]	In James A. Storer, Martin Cohn (eds.): Proceedings Data Compression Conference, 28-30 March 2006, Snowbird, Utah, pp. 173-182. IEEE Press, 2006.
[T]	SIIM Technical Report A-04-14 der Schriftenreihe der Institute für Informatik/Mathematik, Serie A, Universität zu Lübeck, 2004-12-15.
[P]	Version from December 15, 2004.

One-Way Communication Complexity of Symmetric Boolean Functions
Jan Arpe, Andreas Jakoby, and Maciej Liśkiewicz

[J]	Theoret. Informatics Appl. 39:687-706 (2005).
[C]	In Andrzej Lingas, Bengt J. Nilsson (eds.): Fundamentals of Computation Theory, 14th International Symposium, FCT 2003, Malmö, Sweden, August 2003, Proceedings. Volume 2751 of Lecture Notes in Computer Science, pp. 158-170. Springer, 2003.
[T]	SIIM Technical Report A-03-04 der Schriftenreihe der Institute für Informatik/Mathematik, Serie A, Universität zu Lübeck, 2003-11-21.
[P]	Version from September 1, 2004.

Robust Inference of Relevant Attributes
Jan Arpe and Rüdiger Reischuk

[C]	In Ricard Gavaldà, Klaus P. Jantke, Eiji Takamoto (eds.): Algorithmic Learning Theory, 14th International Conference, ALT 2003, Sapporo, Japan, October 2003, Proceedings. Volume 2842 of Lecture Notes in Artificial Intelligence, pp. 99-113. Springer, 2003.
[T]	SIIM Technical Report A-03-12 der Schriftenreihe der Institute für Informatik/Mathematik, Serie A, Universität zu Lübeck, 2003-07-03.
[P]	Revised version from September 9, 2005.

Theses

Learning Concepts with Few Unknown Relevant Attributes from Noisy Data
Jan Arpe

Dissertation (PhD thesis) at the Institute for Theoretical Computer Science, University of Lübeck, August 2006. Referees: Prof. Dr. Rüdiger Reischuk (advisor, Univ. of Lübeck, Germany), Prof. Dr. Hans Ulrich Simon (Ruhr-Univ. Bochum, Germany), Prof. Dr. Georg Schnitger (Goethe-Univ. Frankfurt, Germany), Prof. Dr. Thomas Zeugmann (Hokkaido Univ., Sapporo, Japan).

Berechnung sekundärer Koeffizientengruppen des SO(3) × S¹ - äquivarianten Abbildungsgrades
Computation of Secondary Coefficient Groups of the SO(3) × S¹ - Equivariant Mapping Degree
Jan Arpe

Diploma thesis (in German) at the Mathematical Institute of the Ludwig-Maximilians-University Munich, December 2001.

Miscellaneous

52. Workshop über Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen ("Theorietag")
52nd Workshop on Complexity Theory, Data Structures, and Efficient Algorithms ("Theory Day")
Jan Arpe, Bodo Manthey, and Rüdiger Reischuk (eds.)

SIIM Technical Report B-05-04 der Schriftenreihe der Institute für Informatik/Mathematik, Serie B, Universität zu Lübeck, August 16 & 17, 2005. Workshop homepage.

Institut für Theoretische Informatik: Theoretische Informatik und das Problem des Handlungsreisenden
Theoretical Computer Science and the traveling salesman problem
Bodo Manthey, Jan Arpe, Andreas Jakoby, and Rüdiger Reischuk

FOCUS MUL, vol. 21, no. 3/4, pp. 195-198, October 2004.