Columbia Theory Seminar, Fall 2013

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.

  • Friday, September 13, 11:30, CSB 453: Seny Kamara: How to Search over Encrypted Data (Abstract)
  • Tuesday, September 17, 13:30, CSB 453 (note unusual time and date): Ben lee Volk: On the Structure of Boolean Functions With Small Spectral Norm (Abstract)
  • Friday, September 27, 11:30, CSB 453: Andrew Drucker: Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers (Abstract)
  • Tuesday, October 8, 13:30, CSB 453 (note unusual time and date): Jonathan Ullman: Fingerprinting Codes and the Price of Approximate Differential Privacy (Abstract)
  • Friday, October 11, 11:30, CSB 453: David Harris: Improved algorithms for estimating network reliability (Abstract)
  • Wednesday, October 16, 14:30, CSB 453 (note unusual time and date): Tuomas Sandholm: Algorithms for Creating Game-Theoretic Strategies for Large Incomplete-Information Games (Abstract)
  • Friday, October 18, 11:30, CSB 453: Jing Chen: Optimal Provision-After-Wait in Healthcares (Abstract)
  • Friday, October 25, 11:30, CSB 453: Viswanath Nagarajan: Hallucination Helps: Energy Efficient Multicommodity Routing (Abstract)
  • Wednesday, November 13, 14:45, CSB 453 (note unusual time and date): Benjamin Rossman: Formulas vs. Circuits for Small Distance Connectivity (Abstract)
  • Monday, December 2, 15:00, CSB 453 (note unusual time and date): Aravind Srinivasan: Progress on algorithmic versions of the Lovasz Local Lemma (Abstract)
  • Friday, December 6, 11:30, CSB 453: Ravishankar Krishnaswamy: Capacitated Network Design: Algorithms and Hardness (Abstract)

  • Talk Abstracts

    Friday, September 13:
    How to Search over Encrypted Data
    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.

    Tuesday, September 17:
    On the Structure of Boolean Functions With Small Spectral Norm
    Ben lee Volk

    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

    Friday, September 27:
    Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
    Andrew Drucker

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

    Tuesday, October 8:
    Fingerprinting Codes and the Price of Approximate Differential Privacy
    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.

    Firday, October 11:
    Improved algorithms for estimating network reliability
    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.

    Wednesday, October 16:
    Algorithms for Creating Game-Theoretic Strategies for Large Incomplete-Information Games
    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.)

    Friday, October 18:
    Optimal Provision-After-Wait in Healthcare
    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.

    Friday, October 25:
    Hallucination Helps: Energy Efficient Multicommodity Routing
    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.

    Wednesday, November 13:
    Formulas vs. Circuits for Small Distance Connectivity
    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].

    Monday, December 2:
    Progress on algorithmic versions of the Lovasz Local Lemma
    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.

    Friday, December 6:
    Capacitated Network Design: Algorithms and Hardness
    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 xichen-at-cs-dot-columbia-dot-edu if you want to volunteer to give a talk (especially for students!). The talk can be about your or others' work. It can be anything from a polished presentation of a completed result, to an informal black-board presentation of an interesting topic where you are stuck on some open problem. It should be accessible to a general theory audience. I will be happy to help students choose papers to talk about.
    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 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

    Back to Theory of Computation at Columbia main page