Multivariate polynomial interpolation: efficient algorithms and applications

This research project aims at providing efficient methods to solve a mathematical problem which has practical applications in digital communication and online storage. In the domain of communications, these methods perform the decoding stage of some error-correcting codes, which are used to ensure reliable data transmission over an unreliable or noisy communication channel such as in Digital Video Broadcasting (digital television), or when reading Blu-Ray discs or bar codes. Concerning storage, the methods are used in private information retrieval, which refers to techniques that allow the user to retrieve information from an online database without letting the server know the keywords that were used to search for this information; this has applications such as anonymous email, or domain name registration. With the steady growth of the size of the manipulated data, conceiving efficient methods for such practical problems becomes crucial; it requires both a thorough theoretical study, which is already partially done in our case, and a careful implementation relying on state-of-the-art building blocks for its most basic components.

Faculty Supervisor:

Éric Schost

Student:

Vincent Neiger

Partner:

Discipline:

Computer science

Sector:

University:

University of Waterloo

Program:

Globalink Research Award