Hoeteck Wee

Title: Attribute-Based Encryption and Information-Theoretic Crypto

---

Abstract:
Can we encrypt data while enabling fine-grained access control, as is necessary to protect big, complex data? In this talk, we will survey how addressing this question led to new lower and upper bounds in information-theoretic cryptography and secret sharing, which in turn came from building new connections to communication complexity and private information-retrieval.

Nai-Hui Chia

Title: Quantum-Inspired Sublinear Classical Algorithms for Solving Low-Rank Linear Systems

---

Abstract:
In this talk, I will introduce our classical sublinear algorithm for low-rank linear systems. This algorithm is inspired by the HHL quantum algorithm for linear systems and the recent breakthrough by Tang of dequantizing quantum recommendation systems. Given a matrix A and a vector b, the problem of solving linear systems is to output a vector x such that Ax=b. Since we consider sublinear algorithms, the algorithms cannot read and write the whole matrix or the vectors. In our algorithm, A and b come with a well-known low-overhead data structure such that one can query and sample them in sublinear time, and the algorithm gives query and sampling access to the vector x. Our main result is a classical algorithm that can solve low-rank linear systems in O(polylog n) time, where n is the dimension of the matrix.

Hubert T.H. Chan

Title: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting

---

Abstract:
In this talk, we shall present some recent results on perfectly secure ORAMs. Assuming perfect encryption scheme, we first describe the basic perfectly secure ORAM scheme using 1 server that has O(log^3 N) bandwidth overhead. Then, we describe how using multiple servers can help replacing some oblivious sort operations with linear time operations such as tight stable compaction and merge to reduce the bandwidth overhead to O(log^2 N). Moreover, by using three servers, one can remove the assumption on perfect encryption scheme.
This is joint work with Jonathan Katz, Kartik Nayak, Antigoni Polychroniadou, Elaine Shi

Wei-Kai Lin

Title: OptORAMa: Optimal Oblivious RAM

---

Abstract:
Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs. To compile a general program to an oblivious counterpart, it is well-known that Ω(log N) amortized blowup is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security.
A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). Recently, my coauthor and I resolve this problem and present the first secure ORAM with O(logN) amortized blowup, assuming one-way functions.
In this talk, I will present the framework of our construction, which is based on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with O(log N · loglog N) amortized blowup, assuming one-way functions. In addition, I will also present one of our building blocks of independent interest, a linear-time deterministic oblivious algorithm for tight compaction: Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O(n) algorithm improves the previously best known deterministic or randomized algorithms whose running time is O(n · log n) or O(n · loglog n), respectively.
This is a joint work with Gilad Asharov, Ilan Komargodski, Kartik Nayak, Enoch Peserico, and Elaine Shi.

Pasin Manurangsi

Title: Parameterized Inapproximability

---

Abstract:
The area of parameterized complexity seeks a more fine-grained understanding of NP-hard problems by relaxing the notion of efficient algorithms to the so-called fixed-parameter tractability (FPT). After more than two decades of work, the parameterized complexity of many fundamental problems have been classified; that is, each problem is either shown to be in FPT or shown to be hard for some complexity class that is believed to not be in FPT. However, for most problems not in FPT, their approximability statuses remain open. Specifically, there were few techniques to prove hardness of approximation in the parameterized regime. This has somewhat changed in the last few years where more tools have been developed to tackle such problems. In this talk, I will survey some these recent developments and interesting questions that remain open.

Luca Trevisan

Title: Graph Sparsifiers

---

Abstract:
A weighted graph H is a sparsifier of a graph G if H has much fewer edges than G and, in an appropriate technical sense, "approximates" G. Sparsifiers are useful as compressed representations of graphs and to speed up certain graph algorithms. In a "cut sparsifier," the notion of approximation is that every cut is crossed by approximately the same number of edges in G as in H. In a "spectral sparsifier" a stronger, linear-algebraic, notion of approximation holds.
We discuss a new lower bound on the number of edges that any spectral sparsifier must have, and we interpret our result as a generalization of the Alon-Boppana theorem to graphs that are irregular and weighted. We also show that any compressed representation of a graph that allows to answer queries of the form "how many edges cross this cut?" with a multiplicative error 1+epsilon must use Omega(epsilon^{-2} n log n) bits, showing that known constructions of spectral sparsifiers provide a space-optimal solution to this problem.
(Based on joint work with Charles Carlson, Alexandra Kolla and Nikhil Srivastava.)

Elaine Shi

Title: Synchronous, with a Chance of Partition Tolerance

---

Abstract: Thunder is a practical instantiation of the Thunderella paradigm, enabling high-performance consensus in a decentralized, permissionless environment, and is currently being implemented by ThunderCore. I will describe the latest improvements to the Thunder protocol. Using Thunder as an example, I will explain why classical modeling techniques adopted by 30 years of distributed consensus literature are insufficient for capturing the robustness properties we care about in practical systems. I will then describe our work in which we rethink the underlying models for studying the security of consensus protocols.