We study two fundamental geometric problems on a dynamic set of n axis-parallel boxes in d-dimensional space. The maximum depth problem asks for the largest number of boxes that contain a common point, whereas Klee’s measure problem asks for the volume of the union of the boxes. We present fully dynamic exact data structures for both problems achieving Õ(n^{(d-1)/2}) amortized update time. This update time is optimal for an exact dynamic algorithm, up to logarithmic factors, assuming the Combinatorial k-Clique Hypothesis. Previously, matching bounds were established only for d = 1 [Imai and Asano, J. Algo.'83], and for d = 2 [Suri, Xue, Yang, and Zhu, SoCG'25]. Our approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell. This argument allows us to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates. We believe this technique may be of independent interest for other dynamic geometric problems.

We study the problem of learning an n-variables k-CNF formula Φ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with k-wise hard constraints. Revisiting Valiant’s algorithm (Commun. ACM’84), we show that it can exactly learn (1) k-CNFs with bounded clause intersection size under Lovász local lemma type conditions, from O(logn) samples; and (2) random k-CNFs near the satisfiability threshold, from O(nexp(−√k)) samples. These results significantly improve the previous O(nk) sample complexity. We further establish new information-theoretic lower bounds on sample complexity for both exact and approximate learning from uniform random solutions.

We study how to establish spectral independence, a key concept in sampling, without relying on total influence bounds, by applying an approximate inverse of the influence matrix. Our method gives constant upper bounds on spectral independence for two well-studied Gibbs distributions known to have unbounded total influences: