Chapter 25: Open Problems and Connections

Learning Objectives

• Articulate the difference between statistical limits (information-theoretic) and computational limits (polynomial-time), using sparse PCA, planted clique, and community detection as canonical examples
• Derive the multiplicative weights update (MWU) regret bound $R_T \leq \sqrt{2 T \ln N}$ and recognize it as online convex optimization
• Apply consensus and gossip algorithms to distributed parameter estimation on graphs, and quantify convergence rate via the second-largest eigenvalue of a doubly stochastic matrix
• Formulate distributed Kalman filtering and understand when cell-free massive MIMO reduces to a distributed estimation problem
• Read an estimation theory paper critically: identify the signal model, criterion, benchmark, and the common pitfalls (CRB vs MSE, threshold effect, unfair comparisons)
• Design fair simulation comparisons — equalized SNR definitions, aligned computational budgets, statistically meaningful confidence intervals