Author name cluster

Philippe Moser

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

TCS Journal 2024 Journal Article

Pebble-depth

Liam Jordon
Phil Maguire
Philippe Moser

In this paper we introduce a new feasible notion of Bennett's logical depth based on pebble transducers. This notion is defined based on the difference between the minimal length descriptional complexity of prefixes of infinite sequences from the perspective of finite-state transducers and pebble transducers. Our notion of pebble-depth satisfies the four fundamental properties of depth: i. e. deep sequences exist, trivial sequences are not deep, random sequences are not deep, and the existence of a slow growth law type result. We also compare pebble-depth to other depth notions based on finite-state transducers, pushdown compressors, and the Lempel-Ziv 78 compression algorithm. We first demonstrate how there exists a normal pebble-deep sequence even though there is no normal finite-state-deep sequence. We next build a sequence that has a pebble-depth level of roughly 1, a pushdown-depth level of roughly 1/2 and a finite-state-depth level of roughly 0. We then build a sequence that has a pebble-depth level of roughly 1/2 and a Lempel-Ziv-depth level of roughly 0.

Details DOI

I&C Journal 2023 Journal Article

Pushdown and Lempel-Ziv depth

Liam Jordon
Philippe Moser

In previously published work (Jordon and Moser, 2020), notions of finite-state-depth and pushdown-depth were presented. These were based on finite-state transducers and information lossless pushdown compressors. Unfortunately, a complete separation between the two notions was not established. This paper introduces a new formulation of pushdown-depth based on restricting how fast a pushdown compressor's stack can grow. This allows us to do a full comparison by demonstrating the existence of sequences with high finite-state-depth and low pushdown-depth, and vice-versa. A new notion based on the Lempel-Ziv 78 algorithm is also presented. Its difference from finite-state-depth is shown by a Lempel-Ziv deep sequence that is not finite-state deep, and vice versa. Lempel-Ziv-depth's difference from pushdown-depth is shown by building sequences that have a pushdown-depth of roughly 1/2 but low Lempel-Ziv depth, and by a sequence with high Lempel-Ziv depth but low pushdown-depth. Properties of all three notions are also studied.

Details DOI

I&C Journal 2020 Journal Article

Polylog depth, highness and lowness for E

Philippe Moser

We study the relations between the notions of highness, lowness and logical depth in the setting of complexity theory. We introduce a new notion of polylog depth based on time bounded Kolmogorov complexity. We show polylog depth satisfies all basic logical depth properties, namely sets in P are not polylog deep, sets with (time bounded)-Kolmogorov complexity greater than polylog are not polylog deep, and only polylog deep sets can polynomially Turing compute a polylog deep set. We prove that if NP does not have p-measure zero, then NP contains polylog deep sets. We show that every high set for E contains a polylog deep set in its polynomial Turing degree, and that there exist Low ( E, EXP ) polylog deep sets. Keywords: algorithmic information theory; Kolmogorov complexity; Bennett logical depth.

Details DOI

TCS Journal 2013 Journal Article

On the polynomial depth of various sets of random strings

Philippe Moser

We introduce a general framework for defining the depth of an infinite binary sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in computability/complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions. We use our framework to define new notions of polynomial depth (called monotone poly depth), based on a polynomial version of monotone Kolmogorov complexity. We show that monotone poly depth satisfies all desirable properties of depth notions. We give two natural examples of deep sets, by showing that both the set of Levin random strings and the set of Kolmogorov random strings are monotone poly deep.

Details DOI

I&C Journal 2009 Journal Article

A zero-one law for RP and derandomization of AM if NP is not small

Russell Impagliazzo
Philippe Moser

We show that if RP does not have p-measure zero then ZPP = EXP. As corollaries we obtain a zero-one law for RP in EXP, and that both probabilistic classes ZPP and RP have the same measure in EXP. We also prove that if NP does not have p-measure zero then NP = AM.

Details DOI

I&C Journal 2008 Journal Article

Baire categories on small complexity classes and meager–comeager laws

Philippe Moser

We introduce two resource-bounded Baire category notions on small complexity classes such as P, QUASIPOLY, SUBEXP and PSPACE and on probabilistic classes such as BPP, which differ on how the corresponding finite extension strategies are computed. We give an alternative characterization of small sets via resource-bounded Banach-Mazur games. As an application of the first notion, we show that for almost every language A (i. e. all except a meager class) computable in subexponential time, P A =BPP A. We also show that almost all languages in PSPACE do not have small nonuniform complexity. We then switch to the second Baire category notion (called locally-computable), and show that the class SPARSE is meager in P. We show that in contrast to the resource-bounded measure case, meager–comeager laws can be obtained for many standard complexity classes, relative to locally-computable Baire category on BPP and PSPACE. Another topic where locally-computable Baire categories differ from resource-bounded measure is regarding weak-completeness: we show that there is no weak-completeness notion in P based on locally-computable Baire categories, i. e. every P-weakly-complete set is complete for P. We also prove that the class of complete sets for P under Turing-logspace reductions is meager in P, if P is not equal to DSPACE (log n), and that the same holds unconditionally for QUASIPOLY. Finally we observe that locally-computable Baire categories are incomparable with all existing resource-bounded measure notions on small complexity classes, which might explain why those two settings seem to differ so fundamentally.

Details DOI

I&C Journal 2008 Journal Article

Generic density and small span theorem

Philippe Moser

We refine the genericity concept of Ambos-Spies, 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], and show a relationship between generic density and Lutz resource bounded dimension. We also introduce strong generic density, and show that it is related to packing dimension. We show that all four notions are different. We show that whereas dimension notions depend on the underlying probability measure, generic density does not, which implies that every dimension result proved by generic density arguments, simultaneously holds under any (biased coin based) probability measure. We prove such a result: we improve the small span theorem of Juedes and Lutz, to the packing dimension setting, for k-bounded-truth-table reductions, under any (biased coin) probability measure.

Details DOI

TCS Journal 2008 Journal Article

Martingale families and dimension in P

Philippe Moser

We introduce a new measure notion on small complexity classes (called F -measure), based on martingale families, that gets rid of some drawbacks of previous measure notions: it can be used to define dimension because martingale families can make money on all strings, and it yields random sequences with an equal frequency of 0 ’s and 1 ’s. On larger complexity classes ( E and above), F -measure is equivalent to Lutz resource-bounded measure. As applications to F -measure, we answer a question raised in [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci. , 1994, pp. 807–818] by improving their result to: for almost every language A decidable in subexponential time, P A = BPP A. We show that almost all languages in PSPACE do not have small non-uniform complexity. We compare F -measure to previous notions and prove that martingale families are strictly stronger than Γ -measure [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci. , 1994, pp. 807–818], we also discuss the limitations of martingale families concerning finite unions. We observe that all classes closed under polynomial many-one reductions have measure zero in EXP iff they have measure zero in SUBEXP. We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension [J. H. Lutz, Dimension in complexity classes, in: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 158–169] on P, which meets the intuition behind Lutz’s notion. We show that P -dimension lies between finite-state dimension and dimension on E. We prove an analogue of a Theorem of Eggleston in P, i. e. the class of languages whose characteristic sequence contains 1 ’s with frequency α, has dimension the Shannon entropy of α in P.

Details DOI

I&C Journal 2007 Journal Article

Dimensions of Copeland–Erdös sequences

Xiaoyang Gu
Jack H. Lutz
Philippe Moser

The base-k Copeland–Erdös sequence given by an infinite set A of positive integers is the infinite sequence CEk(A) formed by concatenating the base-k representations of the elements of A in numerical order. This paper concerns the following four quantities. • The finite-state dimension dim fs (CEk(A)), a finite-state version of classical Hausdorff dimension introduced in 2001. • The finite-state strong dimension Dim fs (CEk(A)), a finite-state version of classical packing dimension introduced in 2004. This is a dual of dim fs (CEk(A)) satisfying Dim fs (CEk(A)))⩾dim fs (CEk(A)). • The zeta-dimension (Dim ζ (A), a kind of discrete fractal dimension discovered many times over the past few decades. • The lower zeta-dimension dim ζ (A), a dual of Dim ζ (A) satisfying dim ζ (A)⩽Dim ζ (A). We prove the following. d im fs (CEk(A))⩾dim ζ (A). This extends the 1946 proof by Copeland and Erdös that the sequence (CEk(PRIMES)) is Borel normal. D im fs (CEk(A))⩾Dim ζ (A). T hese bounds are tight in the strong sense that these four quantities can have (simultaneously) any four values in [0, 1] satisfying the four above-mentioned inequalities.

Details DOI

MFCS Conference 2005 Conference Paper

Zeta-Dimension

David Doty
Xiaoyang Gu
Jack H. Lutz
Elvira Mayordomo
Philippe Moser

Abstract The zeta-dimension of a set A of positive integers is Dim ζ ( A ) = inf { s | ζ A ( s ) < ∞ }, where \(\zeta_A(s)=\sum_{n\in A}n^{-s}. \) Zeta-dimension serves as a fractal dimension on ℤ + that extends naturally and usefully to discrete lattices such as ℤ d, where d is a positive integer. This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include a gale characterization of zeta-dimension and a theorem on the zeta-dimensions of pointwise sums and products of sets of positive integers.

Details