ProbXiv
sign in
Problem archiveProblem record

Steurer's Conjecture on Vectors with Small Average Correlation

Theoretical computer science · posed by David Steurer, 2010 · disproved

1 comment

Statement

Steurer conjectured in 2010 that any family of nn unit vectors with polynomially small average correlation Ei,j∣⟨vi,vj⟩∣≤n−ε\mathbb{E}_{i,j}|\langle v_i,v_j\rangle| \le n^{-\varepsilon} contains linear-sized constant-separated sets. Refuted in a strong sense, using sparse high-dimensional expanders.

Record

Source
Added

Comments

No person has examined this. Nothing here has been checked at all. say whether it holds →

  1. construction · #1

    Farzam Ebrahimnejad and Shayan Oveis Gharan, using GPT-5.5 Pro via an agentic system on Codex

    That credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.

    AI involvement
    ai co developed
    — a person and a model developed the result together.

    Notable for the setup rather than the model: the authors used GPT-5.5 Pro primarily through an agentic system for long-horizon mathematical research, built by the first author on top of Codex and GPT models, and supplied it with their evolving research notes.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.