Open Problems:91 - Revision history

Ccanonne at 04:32, 20 August 2019

2019-08-20T04:32:21Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Cut-Sparsification of Hypergraphs to Open Problems:91 without leaving a redirect

2019-08-20T03:44:01Z

Krzysztof Onak moved page Waiting:Cut-Sparsification of Hypergraphs to Open Problems:91 without leaving a redirect

Krzysztof Onak: Updating the header

2019-08-20T03:43:31Z

Updating the header

176.74.251.242 at 20:06, 24 July 2018

2018-07-24T20:06:59Z

176.74.251.242 at 20:04, 24 July 2018

2018-07-24T20:04:45Z

Krzysztof Onak: small fix

2018-07-24T02:11:55Z

small fix

Krzysztof Onak: Adding another citation

2018-07-24T02:09:42Z

Adding another citation

Krzysztof Onak: Two more citations fixed.

2018-07-24T01:58:56Z

Two more citations fixed.

Krzysztof Onak: adding some references

2018-07-24T01:44:25Z

adding some references

Krzysztof Onak: Adding existing references

2018-07-24T01:18:37Z

Adding existing references

← Older revision		Revision as of 04:32, 20 August 2019
Line 23:		Line 23:
	'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite\|AndoniCKQWZ-16}}. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan {{cite\|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).		'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite\|AndoniCKQWZ-16}}. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan {{cite\|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).

−	'''Remark:''' The above considers the number of hyperedges to be the size measure. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} \|e\|$. The current upper bound on the total size of the ~~sparisifier~~ is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.	+	'''Remark:''' The above considers the number of hyperedges to be the size measure. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} \|e\|$. The current upper bound on the total size of the sparsifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.

@@ Line 1: / Line 1: @@
 {{Header
 |source=warwick18
 |who=Robert Krauthgamer

← Older revision		Revision as of 20:06, 24 July 2018
Line 24:		Line 24:
	'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite\|AndoniCKQWZ-16}}. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan {{cite\|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).		'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite\|AndoniCKQWZ-16}}. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan {{cite\|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).

−	'''Remark:''' The above considers ~~size to be~~ the number of hyperedges. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} \|e\|$. The current upper bound on the total size of the sparisifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.	+	'''Remark:''' The above considers the number of hyperedges to be the size measure. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} \|e\|$. The current upper bound on the total size of the sparisifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.

@@ Line 22: / Line 22: @@
 Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$; see the thesis of Pogrow {{cite|Pogrow-17}}. Note that this family clearly contains all ordinary graphs.
-'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite|AndoniCKQWZ-16}}. For a simpler proof see the note of Carlson, Kolla, Srivastava, and Trevisan {{cite|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).
+'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite|AndoniCKQWZ-16}}. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan {{cite|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).
-'''Remark:''' The above defines size as the number of edges. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} |e|$. The current upper bound on the total size of the sparisifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.
+'''Remark:''' The above considers size to be the number of hyperedges. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} |e|$. The current upper bound on the total size of the sparisifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.

@@ Line 22: / Line 22: @@
 Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$; see the thesis of Pogrow {{cite|Pogrow-17}}. Note that this family clearly contains all ordinary graphs.
-'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite|AndoniCKQWZ-16}}. For a simpler proof see the note of Carlson, Kolla, Srivastava, and Trevisan {{cite|CarlsonKST-17}}.
+'''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite|AndoniCKQWZ-16}}. For a simpler proof see the note of Carlson, Kolla, Srivastava, and Trevisan {{cite|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).
 '''Remark:''' The above defines size as the number of edges. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} |e|$. The current upper bound on the total size of the sparisifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.

← Older revision	Revision as of 03:44, 20 August 2019
(No difference)

@@ Line 18: / Line 18: @@
 '''Upper bound:''' The known bound is $O(n^2/\epsilon^2)$ due to Kogan and Krauthgamer {{cite|KoganK-15}}. It is based on the sparsification method of Benczur and Karger {{cite|BenczurK-96}}. Another proof can be derived from a paper of Newman and Rabinovich {{cite|NewmanR-13}}.
-'''Special cases:''' The current upper bound $O(n^2/\epsilon^2)$ can be refined in terms of $\rank(H) := \max_{e\in E} |e| \leq n$. When $\rank(H)=2$ (i.e., ordinary graphs where all edges have cardinality 2), there always exists a sparsifier $H'$ of size $O(n/\epsilon^2)$ [J. D. Batson, D. A. Spielman, and N. Srivastava. Twice-ramanujan sparsifiers. SIAM Review, 56(2):315334, 2014].
+'''Special cases:''' The current upper bound $O(n^2/\epsilon^2)$ can be refined in terms of $\rank(H) := \max_{e\in E} |e| \leq n$. When $\rank(H)=2$ (i.e., ordinary graphs where all edges have cardinality 2), there always exists a sparsifier $H'$ of size $O(n/\epsilon^2)$ {{cite|BatsonSS-14}}.
 This bound easily extends to $\rank(H)=3$, because every hyperedge in $H$ can be replaced by a triangle (3 edges of cardinality 2) with edge weights $1/2$. For intermediate values of $\rank(H)$, the known upper bound is $O((\rank(H)+\log n) n/\epsilon^2)$ {{cite|KoganK-15}}.
-Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$ (this family clearly contains all ordinary graphs), see [Yosef Pogrow. Solving Symmetric Diagonally Dominant Linear Systems in Sublinear Time and Some Observations on Graph Sparsification. Weizmann MSc Thesis, 2017].
+Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$; see the thesis of Pogrow {{cite|Pogrow-17}}. Note that this family clearly contains all ordinary graphs.
 '''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite|AndoniCKQWZ-16}}. For a simpler proof see [Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan: Optimal Lower Bounds for Sketching Graph Cuts. CoRR abs/1712.10261 (2017)]. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).
 '''Remark:''' The above defines size as the number of edges. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} |e|$. The current upper bound on the total size of the sparisifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.

@@ Line 16: / Line 16: @@
 '''Question:''' Is it true that for every $n$-vertex hypergraph $H$ and every $\epsilon\in (0,1/2)$, there is a $(1+\epsilon)$-cut-sparsifier $H'$ with at most $O(n/\epsilon^2)$ edges?
-'''Upper bound:''' The known bound is $O(n^2/\epsilon^2)$ due to Kogan and Krauthgamer {{cite|KoganK-15}}. It is based on the sparsification method of Benczur and Karger [A. A. Bencz ur and D. R. Karger. Approximating s-t minimum cuts in   $O(n^2)$ time. STOC ’96]. Another proof can be derived from a paper of Newman and Rabinovich [I. Newman and Y. Rabinovich. On multiplicative λ-approximations and some geometric applications. SIAM Journal on Computing, 42(3):855883, 2013].
+'''Upper bound:''' The known bound is $O(n^2/\epsilon^2)$ due to Kogan and Krauthgamer {{cite|KoganK-15}}. It is based on the sparsification method of Benczur and Karger {{cite|BenczurK-96}}. Another proof can be derived from a paper of Newman and Rabinovich {{cite|NewmanR-13}}.
 '''Special cases:''' The current upper bound $O(n^2/\epsilon^2)$ can be refined in terms of $\rank(H) := \max_{e\in E} |e| \leq n$. When $\rank(H)=2$ (i.e., ordinary graphs where all edges have cardinality 2), there always exists a sparsifier $H'$ of size $O(n/\epsilon^2)$ [J. D. Batson, D. A. Spielman, and N. Srivastava. Twice-ramanujan sparsifiers. SIAM Review, 56(2):315334, 2014].