Fetching the paper…
Reading the bibliography…
For an undirected/directed hypergraph $G=(V,E)$, its Laplacian $L_G\colon\mathbb{R}^V\to \mathbb{R}^V$ is defined such that its ``quadratic form'' $\boldsymbol{x}^\top L_G(\boldsymbol{x})$ captures the cut information of $G$.
Non-Uniform Random Variate Generation
L. Devroye · 1986
Earlier work this paper cites.
Directed hypergraphs and applications
G. Gallo, G. Longo, S. Pallottino, and S. Nguyen · 1993
Earlier work this paper cites.
An O ( n log log n ) O(n^{\log\log n}) learning algorithm for DNF under the uniform distribution
Y. Mansour · 1995
Earlier work this paper cites.
Approximating s s - t t minimum cuts in O ~ ( n 2 ) \tilde{O}(n^{2}) time
A. A. Benczúr and D. R. Karger · 1996
Earlier work this paper cites.
Realization of set functions as cut functions of graphs and hypergraphs
S. Fujishige and S. B. Patkar · 2001
Earlier work this paper cites.
Random sampling in residual graphs
D. R. Karger and M. S. Levine · 2002
Earlier work this paper cites.
On the Laplacian eigenvalues and metric parameters of hypergraphs
J. Rodríguez · 2002
Earlier work this paper cites.
Convex optimization
S. Boyd and L. Vandenberghe · 2004
Earlier work this paper cites.
Fast approximation algorithms for cut-based problems in undirected graphs
A. Madry · 2010
Earlier work this paper cites.
A general framework for graph sparsification
W. S. Fung, R. Hariharan, N. J. A. Harvey, and D. Panigrahi · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
D. A. Spielman and N. Srivastava · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
D. A. Spielman and S.-H. Teng · 2011
Cited alongside, same era.
Submodular functions are noise stable
M. Cheraghchi, A. Klivans, P. Kothari, and H. K. Lee · 2012
Cited alongside, same era.
Representation, approximation and learning of submodular functions using low-rank decision trees
V. Feldman, P. Kothari, and J. Vondrák · 2013
Cited alongside, same era.
Privately releasing conjunctions and the statistical query barrier
A. Gupta, M. Hardt, A. Roth, and J. Ullman · 2013
Cited alongside, same era.
On multiplicative λ \lambda -approximations and some geometric applications
I. Newman and Y. Rabinovich · 2013
Cited alongside, same era.
Learning pseudo-Boolean k k -DNF and submodular functions
S. Raskhodnikova and G. Yaroslavtsev · 2013
Cited alongside, same era.
Sparse sums of positive semidefinite matrices
M. K. de Carli Silva, N. J. A. Harvey, and C. M. Sato · 2015
Later among the works it cites.
Sketching cuts in graphs and hypergraphs
D. Kogan and R. Krauthgamer · 2015
Later among the works it cites.
Constructing linear-sized spectral sparsification in almost-linear time
Y. T. Lee and H. Sun · 2015
Later among the works it cites.
Hypergraph Markov operators, eigenvalues and approximation algorithms
A. Louis · 2015
Later among the works it cites.
A note on approximate strengths of edges in a hypergraph
C. Chekuri and C. Xu · 2017
Later among the works it cites.
Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs
M. B. Cohen, J. Kelner, J. Peebles, R. Peng, A. B. Rao, A. Sidford, and A. Vladu · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Twice-Ramanujan sparsifiers
J. Batson, D. A. Spielman, and N. Srivastava · 2014
Cited alongside, same era.
Approaching optimality for solving SDD linear systems
I. Koutis, G. L. Miller, and R. Peng · 2014
Cited alongside, same era.
Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
D. A. Spielman and S.-H. Teng · 2014
Cited alongside, same era.
Spectral sparsification and regret minimization beyond matrix multiplicative updates
Z. Allen-Zhu, Z. Liao, and L. Orecchia · 2015
Cited alongside, same era.
Randomized approximation schemes for cuts and flows in capacitated graphs
A. A. Benczúr and D. R. Karger · 2015
Cited alongside, same era.
An SDP-based algorithm for linear-sized spectral sparsification
Y. T. Lee and H. Sun · 2017
Later among the works it cites.
Cheeger inequalities for submodular transformations
Y. Yoshida · 2017
Later among the works it cites.
Re-revisiting learning on hypergraphs: Confidence interval and subgradient method
C. Zhang, S. Hu, Z. G. Tang, and T.-H. H. Chan · 2017
Later among the works it cites.
Polynomial-time algorithms for submodular Laplacian systems
K. Fujii, T. Soma, and Y. Yoshida · 2018
Closest in time.
Efficient O ~ ( n / ϵ ) \tilde{O}(n/\epsilon) spectral sketches for the Laplacian and its pseudoinverse
A. Jambulapati and A. Sidford · 2018
Closest in time.