6533b831fe1ef96bd12996e3

RESEARCH PRODUCT

Upper bound on the communication complexity of private information retrieval

Andris Ambainis

subject

Scheme (programming language)Information retrievalTheoretical computer scienceComputer scienceBoolean circuitConstruct (python library)Communication complexityUpper and lower boundscomputerPrivate information retrievalcomputer.programming_language

description

We construct a scheme for private information retrieval with k databases and communication complexity O(n 1/(2k−1) ).

https://doi.org/10.1007/3-540-63165-8_196