5 papers
Near-linear Size Hypergraph Cut Sparsifiers
Yu Chen, Sanjeev Khanna, Ansh Nagda
Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cu…
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
Yu Chen, Sampath Kannan, Sanjeev Khanna
We consider the problem of designing sublinear time algorithms for estimating the cost of a minimum metric traveling salesman (TSP) tour. Specifically, given access to a $n \times…
Near-Perfect Recovery in the One-Dimensional Latent Space Model
Yu Chen, Sampath Kannan, Sanjeev Khanna
Suppose a graph is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing…
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…
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…