Booth Id:
MATH053
Category:
Mathematics
Year:
2018
Finalist Names:
Warman, Roshan (School: Academy at the Lakes)
Abstract:
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.