For Fall 2013, the usual time for the meetings will be Friday at 11:30 - 13:00 in the CS conference room, CSB 453. Abstracts for talks are given below the talk schedule.

Seny Kamara

Microsoft Research

**Abstract:**
The problem of searching over encrypted data arises often and, most
notably, in the design of secure database systems, file systems, cloud
storage systems and in the design of cryptographic protocols. Many
solutions to this problem have been proposed in the past, including
searchable encryption, deterministic encryption, order preserving
encryption, functional encryption, oblivious RAMs, secure two-party
computation and fully-homomorphic encryption.

In this talk, I will survey the different solutions to the encrypted search problem and discuss their various strengths and limitations, paying particularly close attention to the tradeoffs made between security, efficiency and functionality. I will then present recent advances in the area of searchable encryption and give an overview of the state-of-the art constructions and implementations.

Ben lee Volk

Technion

**Abstract:**
In this talk we show several results regarding Boolean
functions with small spectral norm (the spectral norm of f is
[;\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|;]). Specifically, we
prove the following results for functions [;f:\{0,1\}^n \to \{0,1\};]
with [;\|\hat{f}\|_1=A;].

1. There is a subspace V of co-dimension at most [;A^2;] such that [;f|_V;] is constant.

2. f can be computed by a parity decision tree of size [;2^{A^2}n^{2A};]. (a parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.)

3. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth [;A^2 \log s;].

4. For every [;0<\epsilon;] there is a parity decision tree of depth [;O(A^2 + \log(1/\epsilon));] and size [;2^{O(A^2)} \cdot \min\{1/\epsilon^2,O(\log(1/\epsilon))^{2A}\};] that [;\epsilon;]-approximates f. Furthermore, this tree can be learned, with probability [;1-\delta;], using [;\poly(n,\exp(A^2),1/\epsilon,\log(1/\delta));] membership queries.

All the results above also hold (with a slight change in parameters) to functions [;f:Z_p^n\to \{0,1\};].

Joint work with Amir Shpilka and Avishay Tal

Andrew Drucker

IAS

**Abstract:**
In this talk I will describe nondeterministic reductions which yield
new direct product theorems (DPTs) for Boolean circuits. In our
theorems one assumes that a function F is "mildly hard" against
**nondeterministic** circuits of some size s(n), and concludes that the
t-fold direct product F^t is "extremely hard" against probabilistic
circuits of only polynomially smaller size s'(n). The main advantage
of these results compared with previous DPTs is the greatly improved
size bound in our conclusion.

As an application, we show that if NP is not in coNP/poly then, for every PPT algorithm attempting to produce satisfying assignments to Boolean formulas, there are infinitely many satisfiable instances on which the algorithm's success probability is nearly-exponentially small. This furthers a project of Paturi and Pudlak [STOC'10].

Jonathan Ullman

Harvard University

**Abstract:**
We show new lower bounds on the sample complexity of (eps,
delta)-differentially private algorithms that accurately answer large
sets of counting queries. A counting query on a database D in
({0,1}^d)^n has the form "What fraction of the individual records in
the database satisfy the property q?" We show that in order to answer
an arbitrary set of >> nd counting queries, Q, on D to within error
± alpha it is necessary that n > Omega~(d^{1/2} log|Q| / alpha^2
eps). This bound is optimal up to poly-logarithmic factors, as
demonstrated by the Private Multiplicative Weights algorithm of Hardt
and Rothblum (FOCS'10). In particular, our lower bound is the first
to show that the sample complexity required for accuracy and (eps,
delta)-differential privacy is asymptotically larger than what is
required merely for accuracy, which is O(log|Q| / alpha^2). In
addition, we show that our lower bound holds for the specific case of
k-way marginals (where |Q|~(2d)^k) when alpha is a constant.

Our results rely on the existence of short fingerprinting codes (Boneh-Shaw, CRYPTO'95), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds.

Joint work with Mark Bun and Salil Vadhan.

David Harris

University of Maryland College Park

**Abstract:**
Karger (SIAM Journal on Computing, 1996) developed the first
fully-polynomial approximation scheme to estimate the probability that
a graph G becomes disconnected, given that its edges are removed
independently with probability p. This algorithm runs in [;n^{5+o(1)}
\epsilon^{-3};] to obtain an estimate within relative error [;\epsilon;].

We improve this runtime by showing better bounds on the number of edge cuts which are likely to fail. Karger's analysis depends on bounds for various graph parameters; we show that these bounds cannot be simultaneously tight. This, along with some algorithmic improvements, allow us to improve the run-time to [;n^{3+o(1)} \epsilon^{-2};]; this is essentially best-possible for the meta-approach proposed by Karger. This result rigorously proves experimental observations of Karger \& Tai (Proc. ACM-SIAM Symposium on Discrete Algorithms, 1997) regarding the performance of their algorithm.

Tuomas Sandholm

Carnegie Mellon University

**Abstract:**
Incomplete-information games - such as most auctions, negotiations,
and future (cyber)security settings - cannot be solved using minimax
search even in principle. Completely different algorithms were needed.
A dramatic scalability leap has occurred in our ability to solve such
games over the last seven years, fueled largely by the Annual Computer
Poker Competition. I will discuss the key domain-independent
techniques that enabled this leap, including automated abstraction
techniques and approaches for mitigating the issues that they raise,
new equilibrium-finding algorithms, safe opponent exploitation
methods, techniques that use qualitative knowledge as an extra input,
and endgame solving techniques. I will finish by benchmarking poker
programs against the best human poker professionals and by discussing
what humans can learn from the programs.

(This talk covers results from papers with Sam Ganzfried, Andrew Gilpin, Noam Brown, Kevin Waugh, Satinder Singh, Javier Peña, Sam Hoda, and Troels Bjerre Sørensen.)

Jing Chen

Stony Brook University

**Abstract:**
In this talk we will discuss computational and mechanism design
aspects of optimal scarce resource allocation, where the primary
rationing mechanism is through waiting times.

Specifically, we consider the problem of allocating medical treatments to a population of patients. Each patient has demand for exactly one unit of treatment, and can choose to be treated in one of k hospitals. Different hospitals have different costs, which are fully paid by a third party --- the "payer" --- and do not accrue to the patients. Access to over-demanded hospitals is rationed through waiting times: each hospital [;H_i;] will have waiting time [;w_i;]. In equilibrium, each patient will choose his most preferred hospital given his intrinsic preferences and the waiting times. Assuming the payer has a fixed budget; it needs to decide how many treatments of each type to procure to optimize the welfare in equilibrium.

We show that the equilibrium waiting times will emerge endogenously. We then show that even if the patients' preferences are known to the payer, the task of optimizing social welfare in equilibrium subject to the budget constraint is NP-hard. We also show that, with constant number of hospitals, if the budget constraint can be relaxed from B to [;(1+\epsilon)B;] for an arbitrarily small constant [;\epsilon;], then the original optimum under budget B can be approximated very efficiently.

Going beyond equilibrium solutions we investigate the optimization problem over a much larger class of mechanisms containing the equilibrium ones as special cases. In the setting with two hospitals, we show that under a natural assumption on the patients' preference profiles, optimal welfare is in fact attained by the randomized assignment mechanism, which allocates patients to hospitals at random subject to the budget constraint, but avoids waiting times.

Finally, we discuss potential policy implications of our results, as well as follow-up directions and open problems.

Viswanath Nagarajan

IBM Research

**Abstract:**
We consider virtual circuit routing protocols with an objective of
minimizing energy. We assume the standard model for component power,
namely that the power is some constant static power sigma plus load^a,
where a is some value typically between 1.1 and 3. We will concentrate
on the case that the power management components are links. We give a
polynomial-time offline algorithm for multicommodity routing, that has
approximation ratio O(log^a k), where k is the number of demand pairs.
The key step in the algorithm is a random sampling technique that we
call hallucination, which is reminiscent of sampling in
cut-sparsification algorithms. The algorithm extends rather naturally
to an online algorithm, which we show has competitive ratio O(log^{3a
+ 1} k). The analysis of the online algorithm introduces a natural
"priority" multicommodity flow problem, which might also be of
independent interest.

Joint work with: A. Antoniadis, S. Im, R. Krishnaswamy, B. Moseley, K. Pruhs, C. Stein.

Benjamin Rossman

Tokyo Institute of Technology

**Abstract:**
We consider the Distance k Connectivity problem: given a graph of size
n with two specified vertices, determine whether or not these vertices
are connected by a path of length <= k. The standard "pointer
doubling" (aka "repeated squaring") algorithm solves this problem on
(unbounded fan-in) boolean CIRCUITS of size poly(n) and depth log(k).
In contrast, we show that solving this problem on boolean FORMULAS of
depth log(n)/polyloglog(n) requires size n^Omega(log(k)) for all k <=
loglog(n). This result gives the first super-polynomial separation in
the power of bounded-depth formulas vs. circuits. It also implies a
tight lower bound of Omega(log(k)) on the depth of poly-size circuits
solving Distance k Connectivity for all k <= loglog(n), improving the
previous Omega(loglog(k)) lower bound of Beame, Impagliazzo and
Pitassi [FOCS 1995].

Aravind Srinivasan

University of Maryland

**Abstract:**
There has been substantial progress on algorithmic versions and
generalizations of the Lovasz Local Lemma recently, with some of
the main ideas getting simplified as well. I will survey some of the
main ideas of Moser & Tardos, Pegden, and David Harris & myself
in this context.

Ravishankar Krishnaswamy

Princeton University

**Abstract:**
In this talk, we will discuss the following network design problem: we
are given a multicommodity demand D (or a collection of source-sink
pairs each with a routing requirement), and a capacitated graph. The
goal is to pick the "smallest subgraph" so that the given demand can
be completely routed. This basic problem is a crucial subroutine for
many algorithmic problems, such as buy-at-bulk, energy-minimizing
routing, etc. Our understanding, however, is limited, even for the
case of one demand pair, which is the classical s-t flow problem. In
this talk, we survey what we know about this problem and present some
recent algorithmic results for special cases and hardness results.

Contact

There is a mailing list for the reading group. General information about the mailing list (including how to subscribe yourself to it) is available here. If you want to unsubscribe or change your options, send email to theoryread-request@lists.cs.columbia.edu with the word `help' in the subject or body (don't include the quotes), and you will get back a message with instructions.

Comments on this page are welcome; please send them to
` xichen-at-cs.columbia.edu
`