ATProto Browser

Record data

{
  "uri": "at://did:plc:fwa55bujvdrwlwlwgqmmxmuf/app.bsky.feed.post/3loc5s3o6uc2d",
  "cid": "bafyreigiervsp73asbvm7imrgnt73oxs5cppmyqxzopqmkkkxmfzegsvda",
  "value": {
    "text": "The Planted Orthogonal Vectors Problem (David Kühnemann, Adam Polak, Alon Rosen) ia.cr/2025/780",
    "$type": "app.bsky.feed.post",
    "embed": {
      "$type": "app.bsky.embed.images",
      "images": [
        {
          "alt": "Abstract. In the k-Orthogonal Vectors (k-OV) problem we are given k sets, each containing n binary vectors of dimension d = n^(o(1)), and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a central problem in fine-grained complexity, conjectured to require n^(k − o(1)) time in the worst case.\n\nWe propose a way to plant a solution among vectors with i.i.d. p-biased entries, for appropriately chosen p, so that the planted solution is the unique one. Our conjecture is that the resulting k-OV instances still require time n^(k − o(1)) to solve, on average.\n\nOur planted distribution has the property that any subset of strictly less than k vectors has the same marginal distribution as in the model distribution, consisting of i.i.d. p-biased random vectors. We use this property to give average-case search-to-decision reductions for k-OV.\n",
          "image": {
            "$type": "blob",
            "ref": {
              "$link": "bafkreidriusqe2neumpyullkkku6nkqlormevfrrizebkg2mytpb5rdwtq"
            },
            "mimeType": "image/png",
            "size": 82225
          },
          "aspectRatio": {
            "width": 1200,
            "height": 800
          }
        }
      ]
    },
    "facets": [
      {
        "index": {
          "byteEnd": 96,
          "byteStart": 82
        },
        "features": [
          {
            "uri": "https://ia.cr/2025/780",
            "$type": "app.bsky.richtext.facet#link"
          }
        ]
      }
    ],
    "createdAt": "2025-05-03T20:16:05.777316Z"
  }
}