Deconstructing Complexity of Large Topological Models

Overview

This project demonstrated the problem of deconstructing graphical models is polynomial time solvable, with an O(mn^r+3 + nr) algorithm. The execution was split into two parts: one involving the analytical representation of a graph using the Ihara Zeta Function and the other with the topological characteristics of a graph. A graph’s "loop" ensembles were mapped by a ratio of generating functions, which underwent discrete convolution, to a simpler topology. A set-theoretic partition of a graph that gives all the connected subgraph loop ensembles could systematically utilize a process of loop erasure such as one of reducing the generating functions (note that this would also give an equivalence relationship because they are loops) and reduce them to simple connected paths that are subgraphs of the specified graphs. In addition, we show algorithmic vulnerabilities in the predominant use of coding/decoding: Low-Density Parity check. Represented as bipartite graphs, Tanner graphs were analyzed with the Ihara Zeta Function and M-covers to demonstrate decoding in O(mn^6 log n) time, one way through an analysis of a convex form and the other through a functional method. This has applications in current implementations of hash-algorithms (SHA256 for example) which brute-force decodes at O(2^n) (this is what most cryptocurrencies use), decoding LDPC graphs in an interfere-able way, and profound impacts in Complexity Theory and Graph Theory.

Competition history

• ISEF 2018 Mathematics · Entry MATH053

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.