arXiv research

Algorithm decides if odd-dimensional maps can be immersed.

Algorithm decides if pseudo-Anosov flows have perfect fits.

No algorithm exists to decide 4-manifold homeomorphism.

Algorithm decides homeomorphism of 4-manifolds.

We demonstrate that the question whether or not a given postcritically finite topological ramified covering map of the 2-sphere is Thurston equivalent to a rational map is algorithmically decidable.

Paper tackles decidability of subgroup discreteness problem.

Algorithm decides if genus-two surfaces in 3-sphere are isotopic.

Complexes' contractibility depends on the Collatz conjecture.

Efficient algorithms decide algebraic constraints of causal graphs.

We address the question of whether the property of being virtually special (in the sense of Haglund and Wise) is algorithmically decidable for finite, non-positively curved cube complexes. Our main theorem shows that it cannot be decided locally, i.e. by examining one hyperplane at a time. Specifically, we prove that t…

We present an algorithm which given a presentation of a group $G$ without 2-torsion, a solution to the word problem with respect to this presentation, and an acylindricity constant $κ$, outputs a collection of tracks in an appropriate presentation complex. We give two applications: the first is an algorithm which decid…

We find a constructive bound for the word length of a generating set for the centralizer of an element of the Mapping Class Group. As a consequence, we show that it is algorithmically decidable whether two postcritically finite branched coverings of the sphere are Thurston equivalent.

We prove that there is an algorithm to decide whehter two virtual links are equivalent or not

Algorithm decides if two hyperbolic 3-manifolds are homeomorphic.

We give an algorithm to decide which elements of pi_2(S^2\times S^1#...#S^2\times S^1) can be represented by embedded spheres. Such spheres correspond to splittings of the free group on k generators. Equivalently our algorithm decides whether, for a handlebody N, an element in pi_2(N,\partial N) can be represented by a…

We give a method of constructing maps between tubular groups inductively according to a set of strategies. This map will be a quasi-isometry exactly when the set of strategies is consistent. Conversely, if there exists a quasi-isometry between tubular groups, then there is a consistent set of strategies for them. There…

We produce an algorithm that, given $φ\in Out(F_N)$, where $N\ge 2$, decides wether or not $φ$ is an iwip ("fully irreducible") automorphism.

Authors show that genus defects of Hopf arborescent links are decidable.

An algorithm is proposed that solves two decision problems for pseudo-Anosov elements in the mapping class group of a surface with at least one marked fixed point. The first problem is the root problem: decide if the element is a power and in this case compute the roots. The second problem is the symmetry problem: deci…

Algorithm finds minimal volume hyperbolic links in 3-manifolds.

We show that the following algorithmic problem is decidable: given a $2$-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in $\mathbf{R}^3$? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold $X$ into the 3-sphere $S^3$…

We give an algorithm to find vertical essential tori in small Seifert fiber spaces with infinite fundamental groups. This implies that there are algorithms to decide whether a 3-manifold is a Seifert fiber space.

Agent decides when to measure latent states in RL to improve efficiency.

New bounds for causal effect identification in time series graphs with latent confounders.

Algorithm to determine if two curves are of the same type.

Generalizing empirical findings to new environments, settings, or populations is essential in most scientific explorations. This article treats a particular problem of generalizability, called "transportability", defined as a license to transfer information learned in experimental studies to a different population, on …

This is a report on our long term project to find an algorithm to decide if a finitely presented group has a non-trivial action on a tree.

Efficient algorithm for identifying causal effects in linear models.

Decides if elements in free groups are primitive in polynomial time.

We solve Dehn's isomorphism problem for virtually torsion-free relatively hyperbolic groups with nilpotent parabolic subgroups. We do so by reducing the isomorphism problem to three algorithmic problems in the parabolic subgroups, namely the isomorphism problem, separation of torsion (in their outer automorphism groups…

More and more processes governing our lives use in some part an automatic decision step, where -- based on a feature vector derived from an applicant -- an algorithm has the decision power over the final outcome. Here we present a simple idea which gives some of the power back to the applicant by providing her with alt…

The study examines discrete subgroups of PSL2 over non-archimedean fields.

We give a more geometric approach to an algorithm for deciding whether two hyperbolic 3-manifolds are homeomorphic. We also give a more algebraic approach to the homeomorphism problem for geometric, but non-hyperbolic, 3-manifolds.

For a fixed marked surface $S$, we show that the problem of deciding whether or not a mapping class is reducible lies in $\textbf{NP}$. As usual this immediately gives an exponential time algorithm to decide whether or not a mapping class is reducible. To do this we use an (ideal) triangulation to obtain a coordinate s…

We propose an algorithm for deciding whether a given braid is pseudo-Anosov, reducible, or periodic. The algorithm is based on Garside's weighted decomposition and is polynomial-time in the word-length of an input braid. Moreover, a reduction system of circles can be found completely if the input is a certain type of r…

We prove that the three-sphere recognition problem lies in the complexity class NP. Our work relies on Thompson's original proof that the problem is decidable [Math. Res. Let., 1994], Casson's version of her algorithm, and recent results of Agol, Hass, and Thurston [ArXiv, 2002].

We give a computational algorithm which decides if a braid is quasipositive or not. A braid is quasipositive if it's a product of conjuguates of generators. For this, we use the theory of Garside and the combinatorials properties of the Artin monoid.

A generalized Baumslag-Solitar group (GBS group) is a finitely generated group $G$ which acts on a tree with all edge and vertex stabilizers infinite cyclic. We show that Out(G) either contains non-abelian free groups or is virtually nilpotent of class at most 2. It has torsion only at finitely many primes. One may dec…

Algorithm compares Legendrian knots efficiently in some cases.

Deciding 3-manifolds fibering over the circle is in NP

We analyze an algorithmic question about immersion theory: for which $m$, $n$, and $CAT=\mathbf{Diff}$ or $\mathbf{PL}$ is the question of whether an $m$-dimensional $CAT$-manifold is immersible in $\mathbb{R}^n$ decidable? As a corollary, we show that the smooth embeddability of an $m$-manifold with boundary in $\math…

Decides undecidability of equations and first-order theory for Seifert 3-manifold groups.

In \cite{Ka14} we produced an algorithm for deciding whether or not an element $φ\in Out(F_N)$ is an iwip ("fully irreducible") automorphism. At several points that algorithm was rather inefficient as it involved some general enumeration procedures as well as running several abstract processes in parallel. In this pape…

Although the methods of bagging and random forests are some of the most widely used prediction methods, relatively little is known about their algorithmic convergence. In particular, there are not many theoretical guarantees for deciding when an ensemble is "large enough" --- so that its accuracy is close to that of an…

Whenever a social media user decides to share a story, she is typically pleased to receive likes, comments, shares, or, more generally, feedback from her followers. As a result, she may feel compelled to use the feedback she receives to (re-)estimate her followers' preferences and decides which stories to share next to…

This work facilitates ensuring fairness of machine learning in the real world by decoupling fairness considerations in compound decisions. In particular, this work studies how fairness propagates through a compound decision-making processes, which we call a pipeline. Prior work in algorithmic fairness only focuses on f…

We consider pairs of finitely presented, residually finite groups $u:P\hookrightarrow Γ$. We prove that there is no algorithm that, given an arbitrary such pair, can determine whether or not the associated map of profinite completions $\hat{u}: \widehat{P} \to \widehatΓ$ is an isomorphism. Nor do there exist algorithms…

In this paper, we consider which lens spaces are obtainable by Dehn surgery described by Berge on doubly primitive knots. It is given an algorithm to decide whether a given lens space is obtainable by such surgery. Also included is a complete characterization of such surgery yielding lens spaces with Klein bottles.