Showing 2019Show all
2 papers · 1 filter
cs.GT2019
Network Formation under Random Attack and Probabilistic Spread
Yu Chen, Shahin Jabbari, Michael Kearns +2
We study a network formation game where agents receive benefits by forming connections to other agents but also incur both direct and indirect costs from the formed connections. Sp…
cs.DS2019
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Sepehr Assadi, Yu Chen, Sanjeev Khanna
We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instan…