Back to search

Georgia Institute of Technology

Random subsequences problems : asymptotics, variance, and quantum statistics.

Abstract

dc:description.abstract

This work considers some random words combinatorial problems and their applications. The starting point of this endeavor is the following question: given two random words, "how much do they have in common"? Even if this question has emerged independently in various fields, including computer science, biology, linguistics, it remains mostly unsolved. Firstly, we study the asymptotic distribution of the length of the longest common and increasing subsequences. There we consider a totally ordered alphabet with an order, say 1,...,m, and the subsequences are simply made of a block of 1's, followed by a block of 2's, ... and so on (such a subsequence is increasing, but not strictly). Secondly, we deal with the problem of the variance of the LCS. By introducing a general framework going beyond this problem, partial results in this direction are presented, and various upper and lower variance bounds are revisited in diverse settings. Lastly, we consider the Longest Increasing Subsequences (LIS) of one random word, and the surprising connection with quantum statistics.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Deslandes, Clement
Advisors dc:contributor.advisor
  • Houdré, Christian
  • Lounici, Karim
Committee members dc:contributor.committeemember
  • Butucea, Cristina
  • Bordenave, Charles
  • Breton, Jean-Christophe
  • Damron, Michael
  • Méliot, Pierre-Loïc

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75205

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Deslandes, Clement. Random subsequences problems : asymptotics, variance, and quantum statistics.. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75205