3 papers
cs.DS2021
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
Yu Chen, Sanjeev Khanna, Ansh Nagda
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Bencz…
cs.DS2021
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
We show that the ratio of the number of near perfect matchings to the number of perfect matchings in -regular strong expander (non-bipartite) graphs, with vertices, is a po…
cs.DS2020
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…