Kannan–Tetali–Vempala conjecture (bipartite/binary-matrix case)

The swap chain flips checkerboard 2×2 blocks to sample 0/1 matrices with fixed row and column sums. Kannan, Tetali and Vempala conjectured in 1997 that it mixes in polynomial time for all feasible margins; the lazy chain is shown to have spectral gap at least $\binom{m}{2}^{-1}\binom{n}{2}^{-1}$ on $m \times n$ matrices, which is worst-case tight and settles the bipartite case.

Result

Proved

Status

Resolved

AI contribution

AI-discovered

Method

Argument

Field

Markov chain mixing time

Posed by

Ravindran Kannan, Prasad Tetali, Santosh Vempala

Year posed

1997

Years open

29y

Solved

2026-06-21

Model

ChatGPT 5.5 Pro

Vendor

OpenAI

Collaborators

Weibo Fu (Princeton), Qian Qin (Minnesota), Guanyang Wang (Rutgers)

Verification

Lean-verified

Publication

Preprint

Significance

30 / 100*

Disclosed cost

—

Wikipedia

No dedicated article

Submitted by QuietLemur253 on 01 Aug 2026