Showing 2021Show all
2 papers · 1 filter
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…