The Six Degrees of VDW
Computational Complexity 2018-08-02
A long long time ago a HS student, Justin Kruskal (Clyde's son) was working with me on upper bounds on some Poly VDW numbers (see here for a statement of PVDW). His school required that he have an application. Here is what he ended up doing: rather than argue that PVDW had an application he argued that Ramsey Theory itself had applications, and since this was part of Ramsey Theory it had an application.
How many degrees of separation were there from his work and the so called application.
- The best (at the time) Matrix Multiplication algorithm used 3-free sets.
- 3-free sets are used to get lower bounds on VDW numbers.
- Lower bounds on VDW numbers are related to upper bounds on VDW numbers
- Upper bounds on VDW are related to upper bounds on PVDW numbers.