Quanquan Liu: On Bioelectric Algorithms: A Novel Application of Theoretical Computer Science to Core Problems in Developmental Biology. Authors: Seth Gilbert, James Maguire, Calvin Newport
Friday, December 14, 2018 - 1:00pm to 2:30pm
Location:
32-G631
Speaker:
Quanquan Liu
Biography:
MIT
Seminar group:
Previous experimental studies have suggested that cellular bioelectricity plays a key role in organism developmental processes such as tissue regeneration, tumor suppression, and embryogenesis. Cells in living tissue of organisms often generate and maintain voltage gradient patterns caused by different concentrations of charged ions: a phenomenon known as cellular bioelectricity. While attempts in modeling cellular bioelectricity have centered around modeling a given bioelectric network using differential equations and using simulation techniques to test the model, Gilbert, Maguire, and Newport take a computational approach to study this problem. Specifically, I will present their novel model as well as the following key results:
1) They formulate the cellular bioelectric model (CBM) is a new computational model for modeling the constraints of bioelectrical interactions between cells and their environment.
2) They show that a simple procedure, KnockBack, elects a leader in O(log n) rounds with probability greater than 1-1/n in the CBM, matching the \Omega(log n) lower bound on leader election in unrestricted state machines under shared communication channels and collision detection.
3) They show that KnockBack can be used to find a valid MIS in the CBM using O(polylog(\Delta)log n) rounds. They further show that this strategy is self-stabilizing.
4) They provide solutions for threshold detection and majority selection in the CBM.
5) Finally, they show that the CBM is Turing complete, leading to the conjecture that bioelectric cells are themselves Turing complete.
Authors: Seth Gilbert, James Maguire, Calvin Newport