{
  "annotation_id": "1607cc55-f08a-4de7-909a-9b160996173f",
  "date_created": "2026-03-02T18:02:06.287000Z",
  "date_modified": "2026-03-02T18:02:06.287000Z",
  "file_hash": "91f49de7a2ab085263866e4912f17e3ebd7036d12d4b0b24e2d3895c8f8ae871",
  "private": false,
  "record": {
    "abstract": "We prove new lower bounds for locally decodable codes and private information\nretrieval. We show that a 2-query LDC encoding n-bit strings over an l-bit\nalphabet, where the decoder only uses b bits of each queried position of the\ncodeword, needs code length m = exp(Omega(n/(2^b Sum_{i=0}^b {l choose i})))\nSimilarly, a 2-server PIR scheme with an n-bit database and t-bit queries,\nwhere the user only needs b bits from each of the two l-bit answers, unknown to\nthe servers, satisfies t = Omega(n/(2^b Sum_{i=0}^b {l choose i})). This\nimplies that several known PIR schemes are close to optimal. Our results\ngeneralize those of Goldreich et al. who proved roughly the same bounds for\nlinear LDCs and PIRs. Like earlier work by Kerenidis and de Wolf, our classical\nlower bounds are proved using quantum computational techniques. In particular,\nwe give a tight analysis of how well a 2-input function can be computed from a\nquantum superposition of both inputs.",
    "arxiv_id": "quant-ph/0403140",
    "authors": [
      "Stephanie Wehner",
      "Ronald de Wolf"
    ],
    "categories": [
      "quant-ph",
      "cs.CC",
      "cs.CR"
    ],
    "doi": "10.1007/11523468_115",
    "journal_ref": "Proc. of 32nd ICALP, 2005, LNCS 3580, pages 1424-1436.",
    "title": "Improved Lower Bounds for Locally Decodable Codes and Private   Information Retrieval",
    "url": "https://arxiv.org/abs/quant-ph/0403140"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "bbabdb23-7639-4f14-bfdb-851a77d007ab",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}