Theory Day in Taiwan (2020)

Kazuo Iwama (RIMS, Kyoto University)

Title: Narrowing small complexity gaps

---

Abstract:

Suppose that we have an algorithm which runs in time O(n). This algorithm is optimal in the usual sense and there is little room for further improvements. Nevertheless one may be interested in the constant factor that is hidden by the big-O notation, but that would cause nasty issues about machine models. On the other hand, there are several other complexity measures that are more accurate and cleaner than the number of computation steps. One of them is the number of comparisons for evaluating sorting algorithms. In many textbooks, it is just written that fast algorithms need O(nlogn) comparisons (log means the logarithm of base 2 here), which is optimal. It turns out, however, that its information theoretic lower bound is log(n!), which is approximately equal to nlogn - 1.4426n + O(logn). For instance, it is easy to prove that the simple binary sertion sort needs at most nlogn comparisons, but it is much harder to specifically bound the linear term or to bound its constant factor. The previous best upper bound for that constant factor is -1.32 due to Ford and Johnson that was published in 1959! Another example of such measure is the number of oracle calls for reconstruction of strings which is a model of sequence by hybridization. Again the previous upper bound is n + 2logn and it is a long-standing open question whether the logn term can be emoved.

This talk is about our two recent results on improved upper bounds for those two complexity measures. Such a small improvement may be useless in practice, but it needs a lot of new algorithmic techniques that may be useful in other problems. Even more importantly, those are nice examples to demonstrate the power of randomization and/or the advantage of the average-case complexity over the worst-case complexity.

Brabeeba Wang (MIT)

Title: An algorithmic introduction to theoretical neuroscience

---

Abstract:

Brain is constituted by a network of neurons. Although each neuron is relatively simple to understand, as a network, brain demonstrates phenomenal capacity including understanding languages, solving math problems, creating art, and even possessing consciousness. Through the lens of neuroscience, brain is inherently very difficult to study because it has many levels of emergent properties. From molecules to neurons, from neurons to system and from system to cognition, vertically integrating all these aspects experimentally seems impossible. This creates an urgent need for a theory to vertically integrate different levels of brains in order to understand the brain. In the first half of this talk, I will briefly talk about the high level overview of theoretical neuroscience and for the second half of the talk, I will briefly talk about works that provides algorithmic insights to neuroscience and future directions to work on.

Hsiang-Hsuan Liu (Utrecht University)

Title: Wait for better chances — online with delays

---

Abstract:

Online optimization deals with various optimization problems without knowledge about the future. Generally, in online optimization problems, some irrevocable decision is made upon seeing a current request, and it is not clear if there will be a better choice in the future. The performance of an online algorithm is measured by the competitive ratio, that is, the ratio between the cost of the online algorithm and the one of an optimal offline algorithm, which has unlimited computational resources and knows the future.

The online problems with delays have been of interest recently. In the online-with-delays model, the online decision can be postponed for a better choice. However, the delays are also taking into account in the final cost. The goal is to minimize the sum of the total cost incurred by the problem and the total delays cost. Hence, the challenge is to balance the delays cost and the quality of choice. The problems which are discussed so far are Min-cost Perfect Matching with Delays, Online Service with Delays, Set Cover with Delays, and Bin Packing with Delays.

In this talk, we will go through the basic ideas of online models and then focus on the Min-cost Perfect Matching with Delays (MPMD) problem. Formally, in the MPMD problem, 2m requests arrive over time at points of a metric space. An online algorithm has to connect these requests in pairs, but a decision to match may be postponed till a more suitable matching pair is found. The goal is to eventually match all requests and minimize the joint cost of connection and the total waiting time of all requests. We present an O(m)-competitive algorithm based on linear programming by adapting the moat-growing framework, which is developed originally for (offline) constrained connectivity problems.

Han-Hsuan Lin (UT Austin)

Title: A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries

---

Abstract:

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, Dodis and Wichs (STOC'09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor.

We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS'12), and is able to extract from source of min-entropy rates larger than 1/2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, shown by Cohen and Vidick (unpublished), we obtain the first privacy amplification protocol secure against active quantum adversaries.