News for hackers. Stuff that matters.
Re:Surprise Computer Science Proof Stuns Mathematicians by Vt71fcAqt7 on Tuesday March 21, 2023 @12:06PM (#35248177)
>In late 2021, Kelley and Meka were analyzing the chances that a team of players in a certain cooperative game would be able to win, a standard type of computer science problem. It occurred to them that techniques from research on the size of progression-free sets might be helpful. But they found it easier to directly study those techniques than to apply them to the cooperative game. “My best idea for how to make progress on this problem [was] to actually improve the tool itself, not to use it in a more clever way,” Kelley said.

I wish they went into more detail about how this problem was relevant to the other problem.

Re:Surprise Computer Science Proof Stuns Mathematicians by jmblpati on Tuesday March 21, 2023 @02:22PM (#35250266)
I don't know what specific problem Kelley and Meka were working on, but the connection between arithmetic progression free sets and computer science (especially communication complexity) is somewhat well established. See for example this paper[1] which gives new constructions of "corner-free sets" (which are closely related to 3 arithmetic progression-free sets) by thinking about a specific communication protocol.

[1] https://drops.dagstuhl.de/opus/volltexte/2021/14276/pdf/LIPI...