Testing Dependency of Databases - Lecture

Explore a 45-minute conference talk on detecting dependency between random databases presented by Wasim Huleihel from Tel Aviv University at IPAM's EnCORE Workshop. Dive into the hypothesis testing problem where the null hypothesis assumes independent database generation, while the alternative posits dependency under a latent row permutation. Discover sharp thresholds for optimal testing error probability, examining how they relate to database dimensions and generative distributions. Gain insights into the phase transition from zero to one in error probability. Recorded on February 28, 2024, this presentation is part of the Computational vs Statistical Gaps in Learning and Optimization workshop at the Institute for Pure & Applied Mathematics (IPAM) at UCLA.