2014/04/25 by Chen Avin, Avin, Chen, Michael Borokhovich +5 · 1 citation
Computer Science · #Advanced Graph Neural Networks #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1404.6561
openalex publication_date 2014/04/25 · arxiv created 2015/09/15 · arxiv updated 2015/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Inspired by social networks and complex systems, we propose a core-periphery network architecture that supports fast computation for many distributed algorithms and is robust and efficient in number of links. Rather than providing a concrete network model, we take an axiom-based design approach. We provide three intuitive (and independent) algorithmic axioms and prove that any network that satisfies all axioms enjoys an efficient algorithm for a range of tasks (e.g., MST, sparse matrix multiplication, etc.). We also show the minimality of our axiom set: for networks that satisfy any subset of the axioms, the same efficiency cannot be guaranteed for any deterministic algorithm.