Colloquium Details
New York Area Theory Day
Speaker: IBM/NYU/Columbia
Location: Schapiro (CEPSR) Building, Columbia University Davis Auditorium (Room 412)
Date: April 15, 2016, 9:30 a.m.
Host: Columbia University, New York
Synopsis:
The New York Area Theory Day is a semi-annual conference, aimed to bring together people in the New York metropolitan area for one day of interaction and discussion. The meeting is free and open to everyone; in particular, students are encouraged to attend.
For directions, please see here.
To subscribe to our mailing list, follow the instructions here.
Organizers:
Program
| 9:30 - 10:00 | Coffee and bagels |
| 10:00 - 10:15 | Professor Cliff Stein and Professor Mihalis Yanakakis Remembering David S. Johnson (1945-2016) |
| 10:20 - 11:15 | Prof. Mariana Raykova Succinct Adaptive Garbled RAM |
| 11:15 - 11:25 | Short break |
| 11:25 - 12:20 | Professor Mark Braverman Constant-Rate Coding for Multiparty Interactive Communication is Impossible |
| 12:20 - 2:20 | Lunch break |
| 2:20 - 3:15 | Professor Ran Raz Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning |
| 3:15 - 3:35 | Coffee break |
| 3:35 - 4:30 | Dr. Cynthia Phillips Cooperative Computing for Autonomous Data Centers |
| 4:30 | Follow-up social (location TBA) |
Speakers
Professor Mariana Raykova (Yale)
Succinct Adaptive Garbled RAM
We show how to garble a large persistent database and then garble, one by one, a sequence of adaptively and adversarially chosen RAM programs that query and modify the database in arbitrary ways. Still, it is guaranteed that the garbled database and programs reveal only the outputs of the programs when run in sequence on the database. The runtime, space requirements and description size of the garbled programs are proportional only to those of the plaintext programs and the security parameter. We assume indistinguishability obfuscation for circuits and poly-to-one collision-resistant hash functions. The latter can be constructed based on standard algebraic assumptions such as the hardness of discrete log, or factoring, or finding shortest independent vectors of lattices. In contrast, all previous garbling schemes with persistent data were shown secure only in the static setting where all the programs are known in advance.
As an immediate application, our scheme is the first to provide a way to outsource large databases to untrusted servers, and later query and update the database over time in a private and verifiable way, with complexity and description size proportional to those of the unprotected queries.
Our scheme extends the non-adaptive RAM garbling scheme of Canetti and Holmgren [ITCS 2016]. We also define and use a new primitive, called adaptive accumulators, which is an adaptive alternative to the positional accumulators of Koppula et al [STOC 2015] and somewhere statistical binding hashing of Hubacek and Wichs [ITCS 2015]. This primitive might well be useful elsewhere.
Joint work with Ran Canetti, Yilei Chen, and Justin Holmgren.
Professor Mark Braverman (Princeton)
Constant-Rate Coding for Multiparty Interactive Communication is Impossible
We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.
Our main result is a lower bound on the communication of any noise-resilient protocol over a star network with $n$-parties. Specifically, we show a task that can be solved by communicating $T$ bits over the noise-free network, but for which any protocol with success probability of $1-o(1)$ must communicate at least $\Omega(T \log n / \log \log n)$ bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a $\log \log n$ factor. We show that our bound is tight for the star network by giving a matching coding scheme.
Joint work with Klim Efremenko, Ran Gelles, and Bernhard Haeupler.
Professor Ran Raz (Weizmann)
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.
More formally, in the problem of parity learning, an unknown string $x \in \{0,1\}^n$ was chosen uniformly at random. A learner tries to learn $x$ from a stream of samples $(a_1, b_1), (a_2, b_2)... $, where each $a_t$ is uniformly distributed over $\{0,1\}^n$ and $b_t$ is the inner product of $a_t$ and $x$, modulo 2. We show that any algorithm for parity learning, that uses less than $n^2/25$ bits of memory, requires an exponential number of samples.
Previously, there was no non-trivial lower bound on the number of samples needed, for any learning problem, even if the allowed memory size is $O(n)$ (where $n$ is the space needed to store one sample).
We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length $n$, as well as time complexity of $n$ per encryption/decryption of each bit, and is provenly and unconditionally secure as long as the attacker uses less than $n^2/25$ memory bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decryption.
Dr. Cynthia Phillips (Sandia National Laboratories)
Cooperative Computing for Autonomous Data Centers
We present a new distributed model for graph computations motivated by limited information sharing. Two autonomous entities have collected large social graphs. They wish to compute the result of running graph algorithms on the entire set of relationships. Because the information is sensitive or economically valuable, they do not wish to simply combine the information in a single location and then run standard serial or parallel graph algorithms. We consider two models for computing the solution to graph algorithms in this setting: 1) limited-sharing: the two entities can share only a polylogarithmic size subgraph; 2) low-trust: the two entities must not reveal any information beyond the query answer, assuming they are both honest but curious. We believe this model captures realistic constraints on cooperating autonomous data centers.