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.
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.
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
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].
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.
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.
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.)
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.
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.
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].
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.
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.
Comments on this page are welcome; please send them to xichen-at-cs.columbia.edu