Larger Corner-free Sets in High Dimensions

on YouTube ↗35m

" summary

Presents a concrete improvement over Rankin’s 1961 construction: for k>2 the new protocol yields strictly larger corner-free subsets of [N]^k by shaving communication in the number-on-forehead ExactlyN reductions. Key tools are a number-on-forehead reduction to a number-in-hand equality-with-AP-promise problem, encoding inputs as base-q vectors, and handling carries by sending only the parity of the carry string instead of full carries. The savings produce a better density bound (explicitly improving the Rankin exponent by a k-dependent constant ck tied to Euler zigzag numbers).

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:52ARITHMETIC PROGRESSIONS (AP)
3. 2:44CORNER (2-DIMENSIONAL)
4. 3:49CORNER-FREE SUBSET
5. 7:16ANOTHER APPROACH
6. 8:54SPECIFIC PROBLEM: ExactlyN
7. 11:15NIH Equality WITH AP PROMISE
8. 14:54k-AP FREE COLORING
9. 15:46BEHREND'S CONSTRUCTION
10. 19:00THE ALGORITHM FOR EXACTLY-N, k = 3
11. 19:37AN EXPLICIT ALGORITHM FOR EXACTLY-N. = 3
12. 22:18RANKIN'S CONSTRUCTION, & 3
13. 23:40EXPLICIT PROTOCOL
14. 25:02AVOID CARRIES
15. 28:02IMPROVED PROTOCOL
16. 31:50OPEN QUESTIONS