{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R1704",
  "content_hash": null,
  "slug": "planted-clique-below-square-root-attempt-dated-source-audit",
  "type": "attempt",
  "title": "Dated source and duplicate audit",
  "summary": "The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it. Unresolved remainder: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.",
  "relevance": "Documents why Polynomial-time recovery of planted cliques below the square-root scale was treated as a distinct open target on 2026-08-01.",
  "relevance_source": "recorded",
  "body": "The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus.\n\nQueries included:\n- planted clique polynomial time below sqrt n current 2026\n- planted clique n one half minus delta recovery open\n\nThe exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it. Unresolved remainder: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.",
  "status": "completed",
  "evidence_grade": "sourced",
  "scope": null,
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://arxiv.org/abs/1503.06447",
      "locator": "R. Meka, A. Potechin, and A. Wigderson, Sum-of-squares lower bounds for planted clique, STOC 2015. main SoS lower bounds"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1503.06447",
    "locator": "R. Meka, A. Potechin, and A. Wigderson, Sum-of-squares lower bounds for planted clique, STOC 2015. main SoS lower bounds"
  },
  "relations": [
    {
      "slug": "R1707",
      "title": "Current status and exact unresolved remainder",
      "object_type": "claim",
      "relation": "evidences",
      "direction": "outgoing"
    },
    {
      "slug": "planted-clique-below-square-root",
      "title": "planted clique below square root",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}