On Query-to-Communication Lifting for Adversary Bounds
summary
Shows that Chebyshev polynomials give the optimal low-degree approximations driving several concrete advances: a provable near-linear runtime algorithm for 1D Gibbs-state simulation at physically relevant temperatures; tighter correlation decay from gap to sqrt(gap) in frustration-free systems explaining low-entanglement “scar” eigenstates; and a multivariate-polynomial construction that outperforms Chebyshev under local-gap and frustration-free assumptions, yielding the approximation needed to prove a 2D area law for that class.
AI-written summary · about