All reports by Author Philippe Moser:

__
TR07-051
| 18th April 2007
__

Pilar Albert, Elvira Mayordomo, Philippe Moser#### Bounded Pushdown dimension vs Lempel Ziv information density

__
TR05-089
| 30th July 2005
__

Xiaoyang Gu, Jack H. Lutz, Philippe Moser#### Dimensions of Copeland-Erdos Sequences

__
TR05-060
| 30th May 2005
__

Philippe Moser#### Generic Density and Small Span Theorem

__
TR05-045
| 12th April 2005
__

Philippe Moser#### Martingale Families and Dimension in P

Revisions: 1

__
TR03-046
| 11th June 2003
__

Philippe Moser#### Locally Computed Baire's Categories on Small Complexity Classes

__
TR03-040
| 3rd June 2003
__

Philippe Moser#### RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

__
TR03-029
| 1st April 2003
__

Philippe Moser#### BPP has effective dimension at most 1/2 unless BPP=EXP

__
TR02-058
| 25th September 2002
__

Philippe Moser#### A generalization of Lutz's measure to probabilistic classes

__
TR02-015
| 13th February 2002
__

Philippe Moser#### ZPP is hard unless RP is small

Revisions: 1

__
TR02-006
| 8th November 2001
__

Philippe Moser#### Random nondeterministic real functions and Arthur Merlin games

Revisions: 1

__
TR01-068
| 19th September 2001
__

Philippe Moser#### Relative to P, APP and promise-BPP are the same

Revisions: 1

Pilar Albert, Elvira Mayordomo, Philippe Moser

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol ... more >>>

Xiaoyang Gu, Jack H. Lutz, Philippe Moser

The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite

set $A$ of positive integers is the infinite

sequence $\CE_k(A)$ formed by concatenating the base-$k$

representations of the elements of $A$ in numerical

order. This paper concerns the following four

quantities.

\begin{enumerate}[$\bullet$]

\item

The {\em finite-state dimension} $\dimfs (\CE_k(A))$,

a finite-state ...
more >>>

Philippe Moser

We refine the genericity concept of Ambos-Spies et al, by assigning a real number in $[0,1]$ to every generic set, called its generic density.

We construct sets of generic density any E-computable real in $[0,1]$.

We also introduce strong generic density, and show that it is related to packing ...
more >>>

Philippe Moser

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,

that get rid of some drawbacks of previous measure notions:

martingale families can make money on all strings,

and yield random sequences with an equal frequency of 0's and 1's.

As applications to F-measure,

more >>>

Philippe Moser

We strengthen an earlier notion of

resource-bounded Baire's categories, and define

resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP

and on probabilistic complexity classes such as BPP.

We give an alternative characterization of meager sets via resource-bounded

Banach Mazur games.

We show that the class ...
more >>>

Philippe Moser

We use recent results on the hardness of resource-bounded

Kolmogorov random strings, to prove that RP is small in SUBEXP

else ZPP=PSPACE and NP=EXP.

We also prove that if NP is not small in SUBEXP, then

NP=AM, improving a former result which held for the measure ...
more >>>

Philippe Moser

We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP.

Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP

on infinitely many input lengths.

We also prove that BPP has measure zero in the smaller complexity

class ...
more >>>

Philippe Moser

We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes

C

such as BPP , BPE and BPEXP. Unlike former attempts,

all our measure notions satisfy all three Lutz's measure axioms, that is

every singleton {L} has measure zero ...
more >>>

Philippe Moser

We use Lutz's resource bounded measure theory to prove that either \tbf{RP} is

small or \tbf{ZPP} is hard. More precisely we prove that if \tbf{RP} has not p-measure zero, then \tbf{EXP} is contained

in $\mbf{ZPP}/n$.

We also show that if \tbf{RP} has not p-measure zero,

\tbf{EXP} equals ...
more >>>

Philippe Moser

We construct a nondeterministic analogue to \textbf{APP}, denoted

\textbf{NAPP}; which is the set of all real valued functions

$f: \{ 0,1 \}^{*} \rightarrow [0,1]$, that are approximable within 1/$k$,

by a probabilistic nondeterministic transducer, in time poly($n,1^{k}$).

We show that the subset of all Boolean ...
more >>>

Philippe Moser

We show that for determinictic polynomial time computation, oracle access to

$\mathbf{APP}$, the class of real functions

approximable by probabilistic Turing machines, is the same as having oracle access to

promise-$\mathbf{BPP}$. First

we construct a mapping that maps every function in $\mathbf{APP}$ to a promise problem

more >>>