Time: Fridays 11am-12:30pm, Spring Semester 2017 (first Meeting 2/17)

Location: Stata Center (Bulding 32), G575

Contact: Hsin-Hao Su (hsinhao at mit dot edu), Merav Parter (parter at mit dot edu)

(please contact to be added to email list)

(please contact to be added to email list)

Distributed computing is everywhere. In a wired or wireless communication network, the computation proceeds in a distributed manner. In fact, nature is distributed by design. We will study how distributed computing is happening in neuron networks, insect colonies, and dynamic graphs.

(2/17) Computing with Spiking Neural Networks, Merav Parter.

- Computing with spiking neurons. Wolfgang Maass.
- Networks of spiking neurons: the third generation of neural network models. Wolfgang Maass.
- See discussion of universal approximation theorem for sigmoid nets here and universal computation by perceptron networks with a single hidden layer in Section 3.3 here.

(2/24) VC Dimension in (Neural) Circuit Complexity, Cameron Musco. See notes here.

- VC dimension in circuit complexity. Pascal Koiran.
- What Size Net Gives Valid Generalization? Eric B. Baum and David Haussler.
- Also see bounds on VC dimension for recurrent networks and for networks with sigmoidal and polynomial gates.

(3/10) Models of Cortical Computation, Quanquan Liu.

- Cortical Learning via Prediction. Christos Papadimitrou, Santosh Vempala. COLT 2015.
- For related recent work see Cortical Computation via Iterative Constructions. Papadimitrou, Petti, Vempala. COLT 2016.

- Neural Dynamics as Sampling: A Model for Stochastic Computation in Recurrent Networks of Spiking Neurons. Lars Buesing, Johannes Bill, Bernhard Nessler, Wolfgang Maass. PLoS Comput Biol. 2011 Nov;7(11).
- Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. Nancy Lynch, Cameron Musco, and Merav Parter. ITCS 2017.
- Bootstrap percolation with inhibition. Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou, Frank Mousset, Angelika Steger. arXiv:1410.3291.

- The ANTS Problem. Feinerman O; Korman A. Distributed Computing, 2016.
- Stone Age distributed computing. Yuval Emek, Roger Wattenhofer. PODC 2013: 137-146.
- Ant-Inspired Density Estimation via Random Walks. Cameron Musco, Hsin-Hao Su, Nancy A. Lynch. PODC 2016: 469-478.
- A locally-blazed ant trail achieves efficient collective navigation despite limited information. E. Fonio, Y. Heyman, L. Boczkowski, A. Gelblum, A. Kosowski, A. Korman, and O. Feinerman. eLife, 2016.
- Find your place: Simple distributed algorithms for community detection. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan. SODA 2017.

- Tight Fault Locality. Shay Kutten, David Peleg. SIAM J. Comput. 30(1): 247-268 (2000).
- Optimal maintenance of a spanning tree. Baruch Awerbuch, Israel Cidon, Shay Kutten. J. ACM 55(4): 18:1-18:45 (2008).
- Local-on-Average Distributed Tasks. Merav Parter, David Peleg, Shay Solomon. SODA 2016: 220-239.
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks. Leonid Barenboim. J. ACM 63(5): 47:1-47:22 (2016).