János Pach, Ph.D.Professor , Alfréd Rényi Institute of Mathematics
Moscow Institute of Physics and Technology
Institute of Science and Technology Austria
Simons Foundation Lectures are free public colloquia related to basic science and mathematics. These high-level talks are intended for professors, students, postdocs and business professionals, but interested people from the metropolitan area are welcome as well.
We regret to tell you that János Pach’s lecture, Escaping the Curse of Dimensionality, scheduled for Wednesday, April 1st, has been cancelled.
From now through April 15, 2020 Simons Foundation Lectures will be live-streamed only (there will be no auditorium gathering), or, if that is not possible, cancelled entirely. It is very likely that our speakers and topics will change as well; we will contact you with updates as soon as they are available.
You can see updates about our other scheduled lectures here.
Please visit our lecture archive or our Simons Foundation Lectures YouTube playlist to rewatch or catch up on prior talks of interest.
We hope to see you online!
Simons Foundation Lectures
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.