arXiv research

Each free homotopy class of directed closed curves on a surface with boundary can be described by a cyclic reduced word in the generators of the fundamental group and their inverses. The word length is the number of letters of the cyclic word. If the surface has a hyperbolic metric with geodesic boundary, the geometric…

A simple text model shows word lengths follow Zipf's law.

Let $Σ$ be a surface of negative Euler characteristic and $S$ a generating set for $π_1(Σ,p)$ consisting of simple loops that are pairwise disjoint (except at $p$). We show that the word length with respect to $S$ of an element of $π_1(Σ,p)$ is given by its intersection number with a well-chosen collection of curves an…

The study counts curves on a once-punctured torus with self-intersections.

Study shows shorter words for group elements in surface groups and RAAGs.

For word-equations in groups, we find a logarithmic bound on non-solutions.

The study examines conjugation curvature in a specific group, finding elements with various curvatures.

We combine concepts from random matrix theory and free probability together with ideas from the theory of commutator length in groups and maps from surfaces, and establish new connections between the two. More particularly, we study measures induced by free words on the unitary groups $U(n)$. Every word $w$ in the free…

RNA structures show that a significant portion of bases do not form hydrogen bonds.

We discuss a topological approach to words introduced by the author. Words on an arbitrary alphabet are approximated by Gauss words and then studied up to natural modifications inspired by the Reidemeister moves on knot diagrams. This leads us to a notion of homotopy for words. We introduce several homotopy invariants …

Time Series Motif Discovery (TSMD) is defined as searching for patterns that are previously unknown and appear with a given frequency in time series. Another problem strongly related with TSMD is Word Segmentation. This problem has received much attention from the community that studies early language acquisition in ba…

The paper finds formulas for word lengths and conjugacy classes in surface groups.

Study explains Zipf's law using geometric mechanisms from a finite alphabet.

Given any generating set of any pseudo-Anosov-containing subgroup of the mapping class group of a surface, we construct a pseudo-Anosov with word length bounded by a constant depending only on the surface. More generally, in any subgroup G we find an element f with the property that the minimal subsurface supporting a …

A subset of a group is characteristic if it is invariant under every automorphism of the group. We study word length in fundamental groups of closed hyperbolic surfaces with respect to characteristic generating sets consisting of a finite union of orbits of the automorphism group, and show that the translation length o…

Estimates growth of reciprocal classes in Hecke groups.

This work lists and describes the main recent strategies for building fixed-length, dense and distributed representations for words, based on the distributional hypothesis. These representations are now commonly called word embeddings and, in addition to encoding surprisingly good syntactic and semantic information, ha…

We show that an Anosov map has a geodesic axis on the curve graph of a torus. The direct corollary of our result is the stable translation length of an Anosov map on the curve graph is always a positive integer. As the proof is constructive, we also provide an algorithm to calculate the exact translation length for any…

We give a solution to the word problem for the singular braid monoid SB_n. The complexity of the algorithm is quadratic in the product of the word length and the number of the singular generators in the word. Furthermore we algebraically reprove a result of Fenn, Keyman and Rourke that the monoid embeds into a group an…

We show that, for any (symmetric) finite generating set of the Torelli group of a closed surface, the probability that a random word is not pseudo-Anosov decays exponentially in terms of the length of the word.

In an orientable surface with boundary, free homotopy classes of curves on surfaces are in one to one correspondence with cyclic reduced words in a set of standard generators of the fundamental group. The combinatorial length of a class is the number of letters of the corresponding word. The self-intersection of a free…

In this article, we propose two algorithms for determining the Nielsen-Thurston classification of a mapping class $ψ$ on a surface $S$. We start with a finite generating set $X$ for the mapping class group and a word $ψ$ in $\langle X \rangle$. We show that if $ψ$ represents a reducible mapping class in $\Mod(S)$ then …

Let $Σ$ be a compact, orientable surface of negative Euler characteristic, and let $h$ be a complete hyperbolic metric on $Σ$. A geodesic curve $γ$ in $Σ$ is filling, if it cuts the surface into topological disks and annuli. We propose an efficient algorithm for deciding whether a geodesic curve, represented as a word …

Clarifies metric properties on group power sets.

New algorithm verifies Anosov condition for surface groups efficiently.

The study examines translation lengths of pseudo-Anosov maps on curve graphs.

The depth of a link measures the minimum height of a resolving tree for the link whose leaves are all unlinks. We show that the depth of the closure of a strictly positive braid word is the length of the word minus the number of distinct letters.

In this paper we prove that the space of flat metrics (nonpositively curved Euclidean cone metrics) on a closed, oriented surface is marked length spectrally rigid. In other words, two flat metrics assigning the same lengths to all closed curves differ by an isometry isotopic to the identity. The novel proof suggests a…

We prove a rigidity theorem for the geometry of the unit ball in random subspaces of the scl norm in B_1^H of a free group. In a free group F of rank k, a random word w of length n (conditioned to lie in [F,F]) has scl(w)=log(2k-1)n/6log(n) + o(n/log(n)) with high probability, and the unit ball in a subspace spanned by…

Word2vec (Mikolov et al., 2013) has proven to be successful in natural language processing by capturing the semantic relationships between different words. Built on top of single-word embeddings, paragraph vectors (Le and Mikolov, 2014) find fixed-length representations for pieces of text with arbitrary lengths, such a…

Most speech recognition tasks pertain to mapping words across two modalities: acoustic and orthographic. In this work, we suggest learning encoders that map variable-length, acoustic or phonetic, sequences that represent words into fixed-dimensional vectors in a shared latent space; such that the distance between two w…

Neural machine translation is a relatively new approach to statistical machine translation based purely on neural networks. The neural machine translation models often consist of an encoder and a decoder. The encoder extracts a fixed-length representation from a variable-length input sentence, and the decoder generates…

We investigate the average-case complexity of decision problems for finitely generated groups, in particular the word and membership problems. Using our recent results on ``generic-case complexity'' we show that if a finitely generated group $G$ has the word problem solvable in subexponential time and has a subgroup of…

Study inert and ambiguous classes in modular group using combinatorial methods.

The reflection length of an element of a Coxeter group is the minimal number of conjugates of the standard generators whose product is equal to that element. In this paper we prove the conjecture of McCammond and Petersen that reflection length is unbounded in any non-affine Coxeter group. Among the tools used, the con…

Study on stable torsion length in groups, showing it vanishes in crystallographic groups and providing algorithms for computation.

New spectral Dehn function characterizes word-hyperbolic groups.

While the celebrated Word2Vec technique yields semantically rich representations for individual words, there has been relatively less success in extending to generate unsupervised sentences or documents embeddings. Recent work has demonstrated that a distance measure between documents called \emph{Word Mover's Distance…

New invariants derived from random matrices for words in free groups.

For the free group $F_r$ on $r>1$ generators (respectively, the free product $G_1 * G_2$ of two nontrivial finite groups $G_1$ and $G_2$), we obtain the asymptotic for the number of conjugacy classes of commutators in $F_r$ (respectively, $G_1 * G_2$) with a given word length in a fixed set of free generators (respecti…

A method for authorship attribution based on function word adjacency networks (WANs) is introduced. Function words are parts of speech that express grammatical relationships between other words but do not carry lexical meaning on their own. In the WANs in this paper, nodes are function words and directed edges stand in…

Acoustic word embeddings --- fixed-dimensional vector representations of arbitrary-length words --- have attracted increasing interest in query-by-example spoken term detection. Recently, on the fact that the orthography of text labels partly reflects the phonetic similarity between the words' pronunciation, a multi-vi…

Study on quantitative aspects of trace polynomials in free groups.

We prove that the word problem in the mapping class group of the once-punctured surface of genus g has complexity O(|w|^2 g for |w| > log(g) where |w| is the length of the word in a (standard) set of generators. The corresponding bound in the case of the closed surface is O(|w|^2 g^2). We also carry out the same method…

We describe a polynomial-time algorithm to compute a (tight) geodesic between two curves in the curve graph. As well as enabling us to compute the distance between a pair of curves, this has several applications to mapping classes. For example, we can use these geodesics to compute the asymptotic translation length, Ni…

For $n \geq 2$ we describe an $O(l^3n)$-time algorithm that determines if a length $l$ virtual braid word in the standard presentation of the virtual braid group ${\mathcal VB}_n$ represents the trivial virtual braid.

We show that for any given n, there exists a sequence of words a_k in the generators sigma_1, ... sigma_{n-1} of the braid group B_n, representing the identity element of B_n, such that the number of braid relations of the form sigma_i sigma_{i+1} sigma_i = sigma_{i+1} sigma_i sigma_{i+1} needed to pass from a_k to the…

We give a complete classification of complex hyperbolic $(n_1, n_2, n_3)$-triangle groups by types defined according to the ellipticity of two particular words of short length. This improves the Schwartz conjecture proved by Grossi.