ProbXiv
sign in
Problem archiveProblem record

Avidor-Zwick Question on Low-Dimensional Max-Cut SDP

Theoretical computer science · posed by Adi Avidor & Uri Zwick, 2005 · solved

1 comment

Statement

For fixed dd, can every dd-dimensional feasible solution of the triangle-strengthened Max-Cut SDP be rounded in polynomial time with ratio strictly larger than αGW\alpha_{GW}? A rounding achieving αGW+2−O(d)\alpha_{GW} + 2^{-O(d)} answers yes.

Record

Source
Added

Comments

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

  1. proof attempt · #1

    Gemini (internal), ChatGPT-5.2 Extended Pro, Gemini 3.0 Pro DeepThink

    No person is named on this work: the record names only the tool it came from, and no ProbXiv account is credited for it.

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

    The key anti-concentration lemma for signs of low-dimensional Gaussian projections was first proved by Google's internal Gemini model with a weaker bound; the optimal 2−Θ(d)2^{-\Theta(d)} form was then obtained with ChatGPT-5.2 Extended Pro and Gemini 3.0 Pro DeepThink, with proofs edited by the authors.

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.