Talk:Small set expansion hypothesis

GA Review

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

This review is transcluded from Talk:Small set expansion hypothesis/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Sohom Datta (talk · contribs) 19:40, 1 January 2024 (UTC)

Taking up this review, this is probably a bit more on the mathematical side of CS than what I tend to look at, and so, I might be unfamiliar with certain aspects of this. Let me know if I mess up anywhere :)

The article looks good, once the last few nits are addressed, we should be good to list :) Sohom (talk) 11:37, 7 January 2024 (UTC)

Lede

• Can we define unique games conjecture as part of the text ?
  • Not in any complete sense (the UGC article definition section goes on for many paragraphs) but I added more of an explanation. —David Eppstein (talk) 21:35, 2 January 2024 (UTC)

Statement

• On a initial read through it's unclear to me what $\varepsilon$ is refering to in this section
  • Ok, added a description of what it's used for before using it. —David Eppstein (talk) 21:44, 2 January 2024 (UTC)
• I think explicitly mentioning that $d$ is the degree of the regular graph before the statement would be a good idea ?
  • Ok, stated in the first paragraph of this section. —David Eppstein (talk) 21:44, 2 January 2024 (UTC)
• Can we mention what a regular graph is as part of the flow of the text (instead of having to click the link) ?
  • Done. —David Eppstein (talk) 21:44, 2 January 2024 (UTC)
• (Optional) I wonder if it would be possible to have most of the text explaining the expansion set metric as a background section and have the statement section be just the statement of the hypothesis ?
  • Ok, done. —David Eppstein (talk) 21:49, 2 January 2024 (UTC)
• (Optional) Any chance you could generate a set of two graphs that might satisfy this hypothesis ? (I think it would aid a lot with visualizing the statement as opposed to understanding it mathematically)
  • Not really. It is about the behavior of algorithms on families of graphs. Any individual graph is trivial from this point of view. I did add an illustration of a graph demonstrating the difference between edge expansion and small set expansion. —David Eppstein (talk) 02:22, 3 January 2024 (UTC)

Consequences

• This section seems fine, I have only one nitpick, I assume there have been no efforts to prove/solve these other problems ? (If so it might be worth mentioning somewhere while we talk about the other problems associated with it)
  • Not successful ones. Researchers don't generally publish reports on their unsuccessful efforts, so there is nothing we can use as a reference for that. In some sense the small set expansion hypothesis helps explain why any such efforts would have been unsuccessful. —David Eppstein (talk) 02:25, 3 January 2024 (UTC)

History and partial results

• Seems fine, small nit, it would be nice to know from a readers POV what was the body of work for which the prize was awarded.

Source spot checks

• Ref 1f says but current knowledge suggests that all three problems are likely to be computationally equivalent., but that's not what's written in the article Boaz Barak has suggested more strongly that these two hypotheses are equivalent.
  • In addressing this comment, it would be helpful if you would explain more clearly why you think this source quote says something different from this article quote. I don't want to resort to just quoting Barak's text directly, because if there is something incompletely understood here then it will remain incompletely understood in a direct quote. Is it that Barak also suggests an equivalence to a third problem, 2LIN, that we happen not to mention in this article? Is it Barak's invocation of "current knowledge"? Is it the word "computationally", used by Barak to point to the computational complexity of the problems (rather than for instance their distinct definitions in terms of their inputs and outputs), but left implicit in our article? Is it that our article says that the hypotheses (that certain problems have a certain computational complexity) are equivalent while Barak says the computational complexity of the problems is equivalent? Which of these do you think needs to be rephrased more closely to what Barak says? —David Eppstein (talk) 07:31, 8 January 2024 (UTC)

  @David Eppstein My major concern is the fact that Boaz Barak mentions the "current knowledge" suggest that the problems are equivalent. I don't have an issue with the omission of the third problem (which is fine if it is not relevant) or the other semantic differences you mentioned :) Sohom (talk) 07:53, 8 January 2024 (UTC)

  Well, either they are equivalent or they aren't; that's not something that will change based on later changes to our state of knowledge. To me the part about "current knowledge" means that he thinks they are equivalent and that he sees current knowledge as the basis for his opinion. What do you think it means that is different from that? —David Eppstein (talk) 08:07, 8 January 2024 (UTC)

  I think I'm fine if that interpretation. My initial personal interpretation was that he meant to say that there was an existing understanding based on current knowledge on the subject (as opposed to it being solely his personal opinion), which is why flagged it. :)

  I think that addresses my concerns, I'll give the article another look over and promote if I don't find anything new. Sohom (talk) 09:08, 8 January 2024 (UTC)

• No issues with other instances of Ref 1
• [nit] Ref 2 should set |s2cid-access=free (I think)
  • My experience is that it is extremely rare for s2cid to be anything but useless noise, but it is pointless to try to remove it because some bot will come along and add it again. When it does have a free copy of a paywalled paper, there is usually a better link elsewhere, and this is no exception. I added a direct |url= parameter pointing to a copy hosted by one of the reference's authors. —David Eppstein (talk) 07:31, 8 January 2024 (UTC)
• Ref 3 verifies

Wrapping up

• Other GACR criteria are met

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.