Philippe Moser - Publications

Conference Papers

• Elvira Mayordomo and Philippe Moser,
  Polylog space compression is incomparable with Lempel-Ziv and pushdown compression.
  In Current Trends in Theory and Practice of Computer Science SOFSEM 2009
  Pdf.

• Philippe Moser,
  A General Notion of Useful Information.
  International Workshop on The Complexity of Simple Programs, University College Cork, Ireland, December 6th and 7th, p 215-224, 2008.
  Pdf.

• Pilar Albert, Elvira Mayordomo, Philippe Moser, and Sylvain Perifel
  Pushdown Compression.
  In STACS 2008, p 39-48.
  Pdf.
  Older version: Bounded pushdown dimension vs Lempel Ziv information density.

• Philippe Moser,
  On the Convergence of Fourier Series of Computable Lebesgue Integrable Functions.
  In 4th Conference on Computability and Complexity in Analysis (CCA 2007), Siena, Italy, 2007.
  Pdf.

• David Doty and Philippe Moser,
  Feasible depth.
  In Third Conference on Computability in Europe, CiE 2007, 228-237, 2007.
  Pdf.

• Philippe Moser,
  Martingale Families and Dimension in P.
  In Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK , Springer-Verlag, p 388-397, 2006.
  Pdf.

• Xiaoyang Gu, Jack H. Lutz, and Philippe Moser,
  Dimensions of Copeland-Erdoes Sequences.
  In Proceedings of the Twenty-Fifth Conference on Foundations of Software Technology and Theoretical Computer Science, Springer-Verlag, p. 250-260, 2005.
  Pdf.

• David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser,
  Zeta-dimension.
  In Proceedings of the Thirtieth International Symposium on Mathematical Foundations of Computer Science, Springer-Verlag, p. 283-294, 2005.
  Pdf.

• Philippe Moser,
  Generic Density and Small Span Theorem.
  In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory, Springer-Verlag, p. 92-102, 2005.
  Pdf.

• Philippe Moser,
  Baire's Categories on Small Complexity Classes.
  In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory FCT, p. 333-342, 2003.
  Pdf.

• Russell Impagliazzo and Philippe Moser,
  A Zero-One Law for RP.
  In Proceedings of the 18th Conference on Computational Complexity, p. 48-52, 2003.
  Pdf.

Journal Papers

• Russell Impagliazzo and Philippe Moser,
  A zero-one law for RP and derandomization of AM if NP is not small..
  In Inf. Comput., 207(7): 787-792 (2009).

• Philippe Moser,
  Martingale Families and Dimension in P.
  In Theoretical Computer Science, 400/1-3, pp 46-61, 2008.
  Pdf.

• Philippe Moser,
  Baire categories on small complexity classes and meager-comeager laws.
  In Information and Computation, 206(1): 15-33, 2008.
  Pdf.

• Philippe Moser,
  Generic Density and Small Span Theorem..
  In Information and Computation, 206(1): 1-14, 2008.
  Pdf.

• Philippe Moser,
  Resource-bounded Measure on Probabilistic Classes.
  In Information Processing Letters, Vol 106/6, pp 241-245, 2008.
  Pdf.

• Xiaoyang Gu, Jack H. Lutz, and Philippe Moser,
  Dimensions of Copeland-Erdoes Sequences.
  In Information and Computation, 205(9): 1317-1333, 2007.

Technical Reports

• David Doty and Philippe Moser,
  Finite-state dimension and lossy decompressors.
  2006.
  Pdf.

• Philippe Moser,
  BPP Has Effective Dimension at Most 1/2 Unless BPP=EXP.
  In Electronic Colloquium on Computational Complexity, 2003.
  Pdf.

• Philippe Moser,
  RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP.
  In Electronic Colloquium on Computational Complexity, 2003.

• Philippe Moser,
  ZPP is Hard Unless RP is Small.
  In Electronic Colloquium on Computational Complexity, 2002.

• Philippe Moser,
  Random Nondeterministic Functions and Arthur Merlin Games.
  In Electronic Colloquium on Computational Complexity, 2002.
  Pdf.

• Philippe Moser,
  P(prBPP) = P(APP).
  In Electronic Colloquium on Computational Complexity, 2001.
  Pdf.

Thesis