2020台灣理論日_Day5
 20200112 (Sun.) 09:30 – 20200112 (Sun.) 16:00
 資訊所新館107演講廳
摘要
Theory Day 2020 New Year Special Day 5 January 12 (Sun.), 2020 Conference Room N106, N107 at IIS, Academia Sinica 

Time 
Topics 
09:3010:00 
Breakfast 
10:0011:00 
Talk 1: Kazuo Iwama, Narrowing small complexity gaps
Abstract:
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 averagecase complexity over the worstcase complexity. 
11:0012:00 
Talk 2: Brabeeba Wang, An algorithmic introduction to theoretical neuroscience
Abstract: 
12:0013:30 
Lunch time, AACT Annual Meeting 
13:3014:30 
Talk 3: HsiangHsuan Liu, Wait for better chances — online with delays
Abstract:
The online problems with delays have been of interest recently. In the onlinewithdelays 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 Mincost 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 Mincost 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 moatgrowing framework, which is developed originally for (offline) constrained connectivity problems. 
14:3015:00 
Tea break 
15:0016:00 
Talk 4: HanHsuan Lin, A QuantumProof NonMalleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries
Abstract:
We give the first construction of a nonmalleable 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 minentropy rates larger than 1/2. Combining this construction with a quantumproof 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. 