Theory Day in Taiwan

─ Post X-mas Special (2018)

Date: Wednesday - Thursday, 26-27 December, 2018
Location: Auditorium 101/106, New Building, Institute of Information Science, Academia Sinica, Taipei



Past Theory Days in Taiwan: 2016A@Taipei, 2016B@HsinChu, 2017A@Taipei, 2017B@HsinChu, 2017C@Taipei, 2018@Taipei

The Theory Day in Taiwan is an experimental one-day event that aims to stimulate interaction and discussion for TCS researchers in Taiwan and nearby countries. We plan to host 3-4 hour-long talks in general TCS area with long breaks for interaction. The meeting is free and open to everyone; in particular, students are encouraged to attend. We also create mailing lists for disseminating theory-related events in Taiwan. Please subscribe NOW for more information about Theory Day and Theory Event in Taiwan!!

Speakers: Hubert T.H. Chan, Hoeteck Wee, Pasin Manurangsi, Nai-Hui Chia, Wei-Kai Lin, Luca Trevisan, Elaine Shi

Subscribe to the Mailing List !

Subscribe


We create two mailing lists:
Theory Event Announcement for announcement of theory events.
Theory Talk Announcement for announcement of talks in TCS.

Theory Day Information

Date: Wednesday - Thursday, 26-27 December, 2018
Location:Auditorium 101/106, New Building, Institute of Information Science, Academia Sinica

Schedule

Speaker: Hoeteck Wee, Nai-Hui Chia, Hubert T.H. Chan, Wei-Kai Lin, Pasin Manurangsi, Luca Trevisan, Elaine Shi


Day 1, 26 Dec.
 Location: Auditorium 101
09:50 - 10:50 (Day 1)
 
 Talk 1: Hoeteck Wee, Attribute-Based Encryption and Information-Theoretic Crypto
10:50 - 11:10 (Day 1)
 
 Break and Discussion
11:10 - 12:10 (Day 1)
 
 Talk 2: Nai-Hui Chia, Quantum-Inspired Sublinear Classical Algorithms for Solving Low-Rank Linear Systems
12:10 - 13:30 (Day 1)
 
Lunch
13:30 - 14:30 (Day 1)
 
 Talk 3: Hubert T.H. Chan, Perfectly Secure Oblivious Algorithms in the Multi-Server Setting
14:30 - 15:00 (Day 1)
 
 Break and Discussion
15:00 - 16:00 (Day 1)
 
 Talk 4: Wei-Kai Lin, OptORAMa: Optimal Oblivious RAM
16:00 - 16:30 (Day 1)
 
 Break and Discussion
16:30 - 17:30 (Day 1)
 
 Talk 5: Pasin Manurangsi, Parameterized Inapproximability
Day 2, 27 Dec.
 Location: Auditorium 106
09:50 - 10:50 (Day 2)
 
 Talk 6: Luca Trevisan, Graph Sparsifiers
10:50 - 11:10 (Day 2)
 
 Break and Discussion
11:10 - 12:10 (Day 2)
 
 Talk 7: Elaine Shi, Synchronous, with a Chance of Partition Tolerance

Talk Abstracts.

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.


About

The Theory Day in Taiwan is an experimental one-day event that aims to stimulate interaction and discussion for TCS researchers in Taiwan and nearby countries. We plan to host 3-4 hour-long talks in general TCS area with long breaks for interaction. The meeting is free and open to everyone; in particular, students are encouraged to attend.
Please contact theoryday.tw@gmail.com if you have any question.

Organizers
Ho-Lin Chen (NTU), Yu-Chi Chen (YZU),
Kai-Min Chung (Academia Sinica), and Chung-Shou Liao (NTHU)