NewDevelopments of Discrete-System Algorithmics Based on Complexes

点击翻译按钮获取中文摘要

Simplicial complexes arise in various discrete systems, such as graphs, networks, matroids, convex polytopes, triangulations, etc. There have been known discrete invariant polynomials featuring a given simplicial complex, such as network reliability, chromatic polynomial, invariants of statistical physics and knots/links. We have developed efficient algorithms to compute these invariant polynomials based on the Binary Decision Diagram (BDD), and have shown that moderate-size problems can be solved in practice. Since most of these computation problems are known to be #P-hard, this is a quite remarkable result. We have also presented algebraic approaches to these problems, based on the Groebner bases in computational algebra and also triangulations in computational geometry. This unified approach was analyzed from the viewpoint of combinatorial complexity. We have further investigated new search methods for combinatorial search, geometric and probabilistic proximity structures, full text database search algorithms, etc. Finally, quantum computing and quantum information theory are treated as a natural extension of probabilistic computation and classical information theory, and their discrete structures have been revealed. In so doing, quantum computation simulators have been implemented and used. Some submodularity property of the quantum entropy is also shown.