Columbia University Department of Computer Science



New York Area Theory Day - Spring 2016

Friday, April 15, 2016
Organized by: IBM/NYU/Columbia
External Sponsorship by: Google
Davis Auditorium, 412 Schapiro (CEPSR) Building,
Columbia University, New York (Directions)


9:30 - 10:00 Coffee and bagels

10:00 - 10:15 Prof. Cliff Stein and Prof. 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 Prof. Mark Braverman
          Constant-Rate Coding for Multiparty Interactive Communication
          Is Impossible

12:20 - 2:00 Lunch break

2:00 - 2:55 Prof. Ran Raz
          Fast Learning Requires Good Memory: A Time-Space Lower Bound
          for Parity Learning

2:55 - 3:15 Coffee break

3:15 - 4:10 Dr. Cynthia Phillips
              Cooperative Computing for Autonomous Data Centers

4:30 - 5:30 Follow-up social (location TBD)
For directions, please see here.

To subscribe to our mailing list, follow instructions here.


Alex Andoni
Yevgeniy Dodis
Krzysztof Onak



Prof. 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 

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.


Prof. Mark Braverman (Princeton)
Constant-Rate Coding for Multiparty Interactive Communication is 

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.


Prof. Ran Raz (Weizmann)
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity 

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.

We present results for both models for s-t connectivity. In the 
limited-sharing model, our results exploit social network structure to 
exchange O(log^2 n) bits, overcoming polynomial lower bounds for general 
graphs.  In the low-trust model, our algorithm requires no cryptographic 
assumptions for 3 or more centers and does not even reveal node names.  
We then consider low-communication algorithms in this setting for the 
planted clique problem.  We conjectured a sociologically-justified 
structural property of social networks with only human nodes. Given this 
property, we developed an O(log^2 n)-communication algorithm for a 
planted clique with log n randomly-selected nodes and adversarial edge 
distribution for 2 centers.  However, validation experiments on real 
networks failed because these real networks contain many non-human nodes. 
We describe a method for cleaning non-human nodes given only topology 
and some experimental validation for the cleaning. This gives more human 
networks with a new constructive property that may be useful for future 

This is joint work with Jon Berry (Sandia National Laboratories), Michael 
Collins (Christopher Newport University), Aaron Kearns (University of New 
Mexico), Jared Saia (University of New Mexico), and Randy Smith (Sandia 
National Laboratories).


Back to New York Area Theory Day.