Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial and computational investigations of Neighbor-Joining bias
239
0
0.0
(
0
)
Added by
Abraham Martin del Campo
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Neighbor-Joining algorithm is a popular distance-based phylogenetic method that computes a tree metric from a dissimilarity map arising from biological data. Realizing dissimilarity maps as points in Euclidean space, the algorithm partitions the input space into polyhedral regions indexed by the combinatorial type of the trees returned. A full combinatorial description of these regions has not been found yet; different sequences of Neighbor-Joining agglomeration events can produce the same combinatorial tree, therefore associating multiple geometric regions to the same algorithmic output. We resolve this confusion by defining agglomeration orders on trees, leading to a bijection between distinct regions of the output space and weighted Motzkin paths. As a result, we give a formula for the number of polyhedral regions depending only on the number of taxa. We conclude with a computational comparison between these polyhedral regions, to unveil biases introduced in any implementation of the algorithm.
rate research
Read More
Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid associated to the Cayley-Menger ideal for $n$ points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from $K_4$ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs.
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-succinct in representation, rich in structures, explosive in complexity, dazzling for visualization, and sophisticated for strategic reasoning-has drawn us to play concrete games full of subtleties and to characterize abstract properties pertinent to complexity consequence. Going beyond individual games, we explore the tractability of quantum combinatorial games as whole, and address fundamental questions including: Quantum Leap in Complexity: Are there polynomial-time solvable games whose quantum extensions are intractable? Quantum Collapses in Complexity: Are there PSPACE-complete games whose quantum extensions fall to the lower levels of the polynomial-time hierarchy? Quantumness Matters: How do outcome classes and strategies change under quantum moves? Under what conditions doesnt quantumness matter? PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into outer polynomial space We show that quantum moves not only enrich the game structure, but also impact their computational complexity. In settling some of these basic questions, we characterize both the powers and limitations of quantum moves as well as the superposition of game configurations that they create. Our constructive proofs-both on the leap of complexity in concrete Quantum Nim and Quantum Undirected Geography and on the continuous collapses, in the quantum setting, of complexity in abstract PSPACE-complete games to each level of the polynomial-time hierarchy-illustrate the striking computational landscape over quantum games and highlight surprising turns with unexpected quantum impact. Our studies also enable us to identify several elegant open questions fundamental to quantum combinatorial game theory (QCGT).
The purpose of this article is to study directed collapsibility of directed Euclidean cubical complexes. One application of this is in the nontrivial task of verifying the execution of concurrent programs. The classical definition of collapsibility involves certain conditions on a pair of cubes of the complex. The direction of the space can be taken into account by requiring that the past links of vertices remain homotopy equivalent after collapsing. We call this type of collapse a link-preserving directed collapse. In this paper, we give combinatorially equivalent conditions for preserving the topology of the links, allowing for the implementation of an algorithm for collapsing a directed Euclidean cubical complex. Furthermore, we give conditions for when link-preserving directed collapses preserve the contractability and connectedness of directed path spaces, as well as examples when link-preserving directed collapses do not preserve the number of connected components of the path space between the minimum and a given vertex.
Covering spaces of graphs have long been useful for studying expanders (as graph lifts) and unique games (as the label-extended graph). In this paper we advocate for the thesis that there is a much deeper relationship between computational topology and the Unique Games Conjecture. Our starting point is Linials 2005 observation that the only known problems whose inapproximability is equivalent to the Unique Games Conjecture - Unique Games and Max-2Lin - are instances of Maximum Section of a Covering Space on graphs. We then observe that the reduction between these two problems (Khot-Kindler-Mossel-ODonnell, FOCS 2004; SICOMP, 2007) gives a well-defined map of covering spaces. We further prove that inapproximability for Maximum Section of a Covering Space on (cell decompositions of) closed 2-manifolds is also equivalent to the Unique Games Conjecture. This gives the first new Unique Games-complete problem in over a decade. Our results partially settle an open question of Chen and Freedman (SODA 2010; Disc. Comput. Geom., 2011) from computational topology, by showing that their question is almost equivalent to the Unique Games Conjecture. (The main difference is that they ask for inapproximability over $mathbb{Z}/2mathbb{Z}$, and we show Unique Games-completeness over $mathbb{Z}/kmathbb{Z}$ for large $k$.) This equivalence comes from the fact that when the structure group $G$ of the covering space is Abelian - or more generally for principal $G$-bundles - Maximum Section of a $G$-Covering Space is the same as the well-studied problem of 1-Homology Localization. Although our most technically demanding result is an application of Unique Games to computational topology, we hope that our observations on the topological nature of the Unique Games Conjecture will lead to applications of algebraic topology to the Unique Games Conjecture in the future.
A combinatorial substitution is a map over tilings which allows to define sets of tilings with a strong hierarchical structure. In this paper, we show that such sets of tilings are sofic, that is, can be enforced by finitely many local constraints. This extends some similar previous results (Mozes90, Goodman-Strauss98) in a much shorter presentation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
