{"id":"arxiv/2610.02095","url":"https://arxiv.org/abs/2610.02095","tags":["math.OC","cs.DS"],"score":0,"title":"Randomized Matvec Lower Bounds for Simplex-Based Matrix Games","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Cong Fang"],"reviews":0,"subject":"math.OC","summary":"We prove randomized matrix-vector query lower bounds for two normalized matrix-game geometries: a Euclidean unit ball against a probability simplex, with row norms at most one, and two probability simplices, with entries of absolute value at most one. Each query returns $(Ax,A^\\top y)$ for arbitrary real vectors. The algorithm must return a feasible pair with full saddle-point gap at most $\\varepsilon$, with probability at least $2/3$ on every admissible matrix. For sufficiently small $\\varepsilon$, the worst-case query complexities are…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}