[CS] [masters-presentation] Stern/MS Presentation/Nov 16, 2020

[Tricia Baclawski]

This is an announcement of Jesse Stern's MS Presentation.


https://uchicago.zoom.us/j/91540184597?pwd=TE9BOHd5QzBCcmlpMFFYUFgxS1Vvdz09
Password: 098533

------------------------------------------------------------------------------
Date:  Monday, November 16, 2020

Time:  3:00 PM

Place:  via zoom

M.S. Candidate:  Jesse Stern

M.S. Paper Title: Database Reconstruction and The Turnpike Problem

Abstract:
We identify a new connection between the cryptographic problem of
reconstructing databases from volume leakage and the turnpike problem.
The database reconstruction problem is, given some leaked information
about queries made to the range database, to output a database
consistent with the leakage. For volume leakage, this means deducing
the number of volumes associated with each range query. As past
literature has already established the equivalence of the turnpike
problem to other problems, such as the partial digest problem and
X-ray crystallography, this also connects the newer database problem
to a wealth of other prior work. Given this, we examine a number of
properties of the database reconstruction problem implied by the
turnpike connection and discuss their practical implications. In
addition, we define a new problem of n-dimensional database
reconstruction from volume leakage for any n. As the problem is no
longer equivalent to the n-dimensional turnpike problem in dimensions
higher than one, we give a novel algorithm for this problem and prove
its correctness. We also initiate several new lines of research with
respect to the turnpike problem such as giving a quantum algorithm for
the problem and studying the the relationship between homometric sets
and the classical backtracking algorithm for the problem.

Jesse's advisor is Prof. Laszlo Babai

Login to the Computer Science Department website for details:
 https://newtraell.cs.uchicago.edu/phd/ms_announcements#jesseastern

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Tricia Baclawski
Student Affairs Administrator
Computer Science Department
5730 S. Ellis - Room 350
Chicago, IL 60637
pbaclawski at uchicago.edu
(773) 702-6854
/pronouns: she, her, hers/
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=