Sampling algorithms and information theory

Results in Sampling algorithms and information theory

• Critical hard-core influence bounds via nonbacktracking collisions

  Partially resolvedSpectral independence of the hard-core model at the uniqueness threshold λ_c(Δ)

  Theoretical computer science · Sampling algorithms and spectral independence · standalone Lean package

  For every Δ ≥ 3, every n-vertex graph of maximum degree at most Δ, every activity 0 < λ ≤ λ_c(Δ) and every feasible pinning, each absolute row sum of the hard-core influence matrix is O_Δ(√n log n), with an explicit constant.

  Manuscript: Critical hard-core influence bounds via nonbacktracking collisions · Lean proof: Critical hard-core influence bounds via nonbacktracking collisions · Verification: Critical hard-core influence bounds via nonbacktracking collisions

• Counterexamples to a best-of-n win-rate bound at every budget

  DisprovedBeirami et al.'s best-of-n win-rate versus KL divergence conjecture (Conjecture 7.2)

  Theoretical computer science · Sampling algorithms and information theory · shared Lean library

  For every budget n ≥ 2 and cap δ > 0, a finite reference law with all probabilities ≤ δ has a best-of-n policy with D < ℓ(W), violating W ≤ ℓ⁻¹(D); for n = 2, p = (2/5,1/5,1/5,1/5) gives W = 163/250.

  Manuscript: Counterexamples to a best-of-n win-rate bound at every budget · Lean proof: Counterexamples to a best-of-n win-rate bound at every budget · Verification: Counterexamples to a best-of-n win-rate bound at every budget