Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

Portland State University

2011

Computational complexity

Articles 1 - 2 of 2

Full-Text Articles in Physical Sciences and Mathematics

Integer Optimization And Computational Algebraic Topology, Bala Krishnamoorthy Apr 2011

Integer Optimization And Computational Algebraic Topology, Bala Krishnamoorthy

Systems Science Friday Noon Seminar Series

We present recently discovered connections between integer optimization, or integer programming (IP), and homology. Under reasonable assumptions, these results lead to efficient solutions of several otherwise hard-to-solve problems from computational topology and geometric analysis. The main result equates the total unimodularity of the boundary matrix of a simplicial complex to an algebraic topological condition on the complex (absence of relative torsion), which is often satisfied in real-life applications . When the boundary matrix is totally unimodular, the problem of finding the shortest chain homologous under Z (ring of integers) to a given chain, which is inherently an integer program, can …


On The Effect Of Criticality And Topology On Learning In Random Boolean Networks, Alireza Goudarzi Jan 2011

On The Effect Of Criticality And Topology On Learning In Random Boolean Networks, Alireza Goudarzi

Systems Science Friday Noon Seminar Series

Random Boolean networks (RBN) are discrete dynamical systems composed of N automata with a binary state, each of which interacts with other automata in the network. RBNs were originally introduced as simplified models of gene regulation. In this presentation, I will present recent work done conjointly with Natali Gulbahce (UCSF), Thimo Rohlf (MPI, CNRS), and Christof Teuscher (PSU). We extend the study of learning in feedforward Boolean networks to random Boolean networks (RBNs) and systematically explore the relationship between the learning capability, the network topology, the system size N, the training sample T, and the complexity of the computational task. …