Private Information Retrieval (PIR) schemes are communication protocols that allow a user to recover a single bit from a large database stored across multiple non-interacting servers, without revealing any information about which bit was queried. PIR schemes have deep connections to algebraic coding theory, and in particular to Locally Decodable Codes (LDCs).

In this talk, new t-server PIR schemes are presented with communication complexity sub-polynomial in the previously best known bounds, for all but finitely many t. The key ingredients are matching vectors and polynomial derivatives, both well-established tools in the PIR and LDC literature. A landmark result of Dvir and Gopi previously combined these two ideas using polynomials and derivatives over exotic algebraic rings, giving the first 2-server PIR with sub-polynomial communication. The new approach achieves improved bounds via a simpler method that works natively over finite fields, using only elementary properties of polynomials. In particular, this yields a 3-server PIR scheme with communication complexity 2^{O~((log n)^{1/3})}, improving upon Efremenko's bound of 2^{O~(sqrt(log n))}.