3 ms·
>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
by Vt71fcAqt7 4y ago
>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.
- jmblpati 4y agoI 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/LIPIcs-CCC-2021-2.pdf https://drops.dagstuhl.de/opus/volltexte/2021/14276/pdf/LIPI...