CANCELED: Escaping the Curse of Dimensionality

When working on problems in dynamic programming, Richard Bellman coined the expression ‘the curse of dimensionality.’ The curse arises when the dimension of space increases. This leads to an exponential increase of volume, which in turn causes data to become spread out and sparse. Combinatorists call this phenomenon the ‘combinatorial explosion.’

In this lecture, János Pach will discuss some notoriously hard combinatorial problems for large classes of graphs and hypergraphs arising in geometric and practical applications. These structures escape the ‘curse of dimensionality’: They can be embedded in a bounded-dimensional space, or they have small Vapnik–Chervonenkis dimension, or they have a short algebraic description. Pach will go on to discuss the various advantages of low dimensionality.