Cryptography today is in the midst of a tremendous revolution. For example, recently discovered tools like "fully homomorphic" encryption and "functional" encryption allow arbitrary computations on encrypted data. To date, all these cryptosystems are based on computational problems related to (point) lattices, and their most efficient versions operate in certain polynomial rings. In this talk I will survey one of the main cryptographic problems used in ring-based cryptography (called "learning with errors over rings"), explain the theoretical evidence for its hardness and connection to algebraic "ideal lattices," and outline some of the versatile and powerful encryption schemes that can be based upon it. The talk will be self-contained, assuming only familiarity with basic polynomial arithmetic.

In this talk, I will present our new result on approximating broadcast scheduling problem. In the problem, there is a single server that can hold $n$ pages of unit size, and multiple requests for these pages arrive over time. At each time slot the server can broadcast one page which satisfies all the outstanding requests for this page at that time. The goal is to find a schedule to minimize the average response time of the requests, i.e. the duration since a request arrives until it is satisfied. We give an $\tilde{O}(\log^{1.5} n)$ approximation algorithm for the problem improving upon the previous $\tilde{O}(\log^2 n)$ approximation. We also show an $\Omega(\log^{1/2-\eps} n)$ hardness result, and an integrality gap of $\Omega(\log n)$ for the natural LP relaxation for the problem. Prior to our work, only NP-Hardness and a (tiny) constant integrality gap was known. These results are based on establishing a close connection to the discrepancy minimization problem for permutation set-systems. Specifically, our improved approximation is based on using recent algorithmic ideas developed for discrepancy minimization. Our integrality gap is obtained from the $\Omega(\log n)$-lower bound on the discrepancy of 3-permutations, while our hardness result is based on establishing the first hardness result for the discrepancy of $\ell$-permutations.
Based on joint work with Nikhil Bansal, Moses Charikar and Ravishankar Krishnaswamy. In SODA 2014.

In this talk, we discuss some of our recent research work and findings on clustering structures of biomedical objects and their relations to diseases. First, we show how density-based clustering patterns of dendritic cells in images of lymph nodes are related to the status and prognosis of breast cancer. Second, we propose a new model of Voronoi diagram, called clustering induced Voronoi diagram (CIVD), to study the collective influence of clustered objects to their surrounding areas, and sketch efficient approximation algorithms for several types of CIVD in the d-D space (for any positive constant integer d). Third, we show that with a CIVD, we can capture the "context" of immune cells in a quantitative manner, which helps identify immune cells on H&E staining images with much improved accuracy, for the study of bowel inflammation diseases. H&E staining images are routinely used in clinical practice. Our studies may reveal possible connections between the clustering of immune cells and the functionality of the immune system, and lay a key foundation for the diagnosis and prognosis of different diseases.

The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In the information theoretic setting, although existence of such codes for various rich classes of tampering functions is known, explicit constructions exist only for highly structured family of tampering functions. Prior explicit constructions of non-malleable codes rely on the ``compartmentalized'' structure of the tampering function, i.e., the codeword is partitioned into ` a priori fixed' blocks and each block can `only' be tampered independently. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. We consider an infinitely large natural class of non-compartmentalized tampering functions. In our model, the tampering function can permute the bits of the encoding and (optionally) perturb them. We provide an `explicit' and `efficient' rate 1 non-malleable code for multi-bit messages. Lack of explicit constructions of non-malleable codes for non-compartmentalized tampering functions severely inhibits their utility in cryptographic protocols. As a motivation for our construction, we show application of non-malleable codes to cryptographic protocols. In an idealized setting, we show how string commitments can be based on one-bit commitments, if non-malleable codes exist. Further, as an example of a non-trivial use of non-malleable codes in standard cryptographic protocols (not in an idealized model), we show that if explicit non-malleable codes are obtained for a slightly larger class of tampering functions than we currently handle, one can obtain a very simple non-malleable commitment scheme, under somewhat strong assumptions.
Joint work with Divya Gupta (UCLA), Hemanta K Maji (UCLA), Omkant Pandey (UIUC) and Manoj Prabhakaran (UIUC).

k-center problem is a variant of classical facility location problem, where objective function is to minimize the maximum distance of client to the closest facility. Formally, it can be defined as given a graph and a parameter k, we need to pick k-vertices(facilities/centers) and map every other vertex(clients/locations) to some facility s.t. maximum of the client to facility distance is minimized. This problem has an easy tight approximation algorithm with approximation ratio 2. But, if we add an extra constraint of putting bound on capacities to the facilities/centers(number of clients/locations mapped to it), problem become surprisingly hard. First constant(large) factor approximation algorithm was obtained recently by using intricate rounding algorithm. We provide a simpler algorithm and bound integrality gap by 9(lower bound is 7). Algorithm reduce a general instance to special tree instances and then solves tree instances optimally. Our concepts can also be applied to several variants of capacitated k-center problem.
Joint work with Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Ola Svensson

A good property of a problem instance is that it's easy to solve. And even better property is resilience: that the instance remains easy to solve under arbitrary (but minor) perturbations. We informally define the resilience of an instance of a combinatorial problem, and discuss recent work on resilient promise problems, including resilient satisfiability and resilient graph coloring.
Joint work with Lev Reyzin.

Traditional models of computation assume inputs are given honestly. Real computational systems, however, are often economic in nature, and private incentives can preclude truth-telling. Even simple, commonly-employed resource allocation mechanisms such as the first price auction can exhibit equilibrium behavior which is difficult to precisely characterize. Through the lens of approximation, we lower-bound the social welfare in the first price auction without explicitly solving for equilibrium. By proving this approximation result in a restricted way, we further show how to extend such results to the objective of revenue, even in more general settings such as many auctions running simultaneously.
Joint with Jason Hartline and Darrell Hoy.

Given an implicit matrix A with oracle access x^TA x for any x\in \R^n, we study the query complexity of randomized algorithms for estimating the trace of the matrix. This problem has many applications in quantum physics, streaming algorithms, machine learning, and pattern matching. Two metrics are commonly used for evaluating the estimators: i) variance; ii) a high probability multiplicative-approximation guarantee. In this talk, I will give an estimator which is provably the minimum variance unbiased estimator among all linear nonadaptive estimators, and show some other negative results.
Joint work with Karl Wimmer and Yi Wu.

In the Palindrome Problem one tries to find all palindromes (palindromic substrings) in a given string. A palindrome is defined as a string which reads forwards the same as backwards, e.g., the string “racecar”. A related problem is the Longest Palindromic Substring Problem in which finding an arbitrary one of the longest palindromes in the given string suffices. We regard the streaming version of both problems. In the streaming model the input arrives over time and at every point in time we are only allowed to use sublinear space. The main algorithms in this paper are the following: The first one is a one-pass randomized algorithm that solves the Palindrome Problem. It has an additive error and uses O(n sqrt(n)) space. The second algorithm is a two-pass algorithm which determines the exact locations of all longest palindromes. It uses the first algorithm as the first pass. The third algorithm is again a one-pass randomized algorithm, which solves the Longest Palindromic Substring Problem. It has a multiplicative error using only O(log(n)) space. We also give two variants of the first algorithm which solve other related practical problems.
Joint work with Petra Berenbrink, Funda Ergün, and Frederik Mallmann-Trenn.