2020 Winter Theory

Workshop

Date: December 29, 2020 - January 6, 2021 (GMT+8)
(December 28, 2020 - January 5, 2021 EST/GMT-5)
Location: Virtual and Auditorium 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, 2018B@Taipei, 2019@HsinChu

In the last few years, we invited our theory friends to visit us in Taiwan at the year-end to share their research works in theory day(s) events. This year, however, due to the pandemic, such visits and gatherings are not possible. Nevertheless, thanks to the great initiative by our old friend Elaine Shi, we decide to continue this tradition virtually and invite more friends!

Joint with Elaine, we co-host this virtual 5 days winter theory workshop in the Taiwan-US timezone, where we invite friends to present their works that cover a wide range of topics --- cryptography, algorithm, quantum, and theoretical machine learning. It is meant to be casual and interactive with talks scheduled at 9:30-11:30 am Taiwan time and 8:30-10:30 pm Eastern time. The workshop is free and open to everyone; in particular, students are encouraged to attend. We will host a physical site at N106, IIS, Academia Sinica, Taipei. For online participants, please register with the google form below to receive the link to join online.

Speakers:
Speakers: Elaine Shi (CMU), Kai-Min Chung (Academia Sinica), Hubert Chan (HKU), Zhao Song (IAS), Feng-Hao Liu (FAU), Ho-Lin Chen (NTU), Chi-Ning Chou (Harvard University), Nai-Hui Chia (QulCS), Xiong Fan (UMD),Bo-Yin Yang (Academia Sinica) and Xiaorui Sun (UIC)

Registration


You could join us on-site or virtual, and please register to participate.
You will get the virtual link after registration.

Registration

Workshop Information

Date: December 29, 2020 - January 6, 2021 (GMT+8)
(December 28, 2020 - January 5, 2021 EST/GMT-5)
Location: Virtual and Auditorium 106, New Building, Institute of Information Science, Academia Sinica, Taipei

Schedule

Speakers: Speakers: Elaine Shi (CMU), Kai-Min Chung(Academia Sinica), Hubert Chan (HKU), Zhao Song (IAS), Feng-Hao Liu (FAU), Ho-Lin Chen (NTU), Chi-Ning Chou (Harvard University), Nai-Hui Chia (QulCS), Xiong Fan (UMD),Bo-Yin Yang (Academia Sinica) and Xiaorui Sun (UIC)


The virtual conference will open 10 minutes before the session.

29 Dec. 2020 (GMT+8)
28 Dec. 2020 (EST)
Location: Auditorium 106
09:30 - 09:32
 20:30 - 20:32
 Opening
09:32 - 09:42
 20:32 - 20:42
 Talk 1 (short talk): Elaine Shi,
Can we beat the aks sorting network
09:42 - 09:52
 20:42 - 20:52
 Talk 2 (short talk): Kai-Min Chung,
How well can a classical client delegate quantum computation?
09:52 - 10:10
 20:52 - 21:10
 Break
10:10 - 10:20
 21:10 - 21:20
 Talk 3 (short talk): Hubert Chan,
Opinion Dynamics with Varying Susceptibility to Persuasion via Non-Convex Local Search
10:20 - 10:30
 21:20 - 21:30
 Talk 4 (short talk): Zhao Song
30 Dec. 2020 (GMT+8)
29 Dec. 2020 (EST)
Location: Auditorium 106
09:30 - 10:15
 20:30 - 21:15
 Talk 1: Feng-Hao Liu,
Rivalry and Friendship between Cryptography and Quantum Science -- Challenges and New Opportunities
10:15 - 10:25
 21:15 - 21:25
 Break
10:25 - 10:55
 21:25 - 21:55
 Talk 2: Ho-Lin Chen,
Self-Stabilizing Leader Election in Population Protocols
31 Dec. 2020 (GMT+8)
30 Dec. 2020 (EST)
Location: Auditorium 106
09:30 - 10:10
 20:30 - 21:10
 Talk 1: Chi-Ning Chou,
Toward Spoofing Linear Cross-Entropy Benchmarking in Google’s Quantum Supremacy
10:10 - 10:20
 21:10 - 21:20
 Break
10:20 - 11:00
 21:20 - 22:00
 Talk 2: Nai-Hui Chia,
Quantum meets MCSP
4 Jan. 2021 (GMT+8)
3 Jan. 2021 (EST)
Location: Virtual only
09:30 - 11:00
 20:30 - 22:00
 Game Night/Day
https://netgames.io/
5 Jan. 2021 (GMT+8)
4 Jan. 2021 (EST)
Location: Auditorium 106
09:30 - 09:40
 20:30 - 20:40
 Talk 1 (short talk): Xiaorui Sun,
Fully dynamic c-edge connectivity in subpolynomial time (short talk)
09:40 - 10:25
 20:40 - 21:25
 Talk 2: Xiong Fan,
Design and Formally Verify Post-Quantum Cryptography
6 Jan. 2021 (GMT+8)
5 Jan. 2021 (EST)
Location: Auditorium 106
09:30 - 09:40
 20:30 - 20:40
 Talk 1 (short talk): Bo-Yin Yang,
Time-constant GCD and modular inversion
09:40 - 10:20
 20:40 - 21:20
 Talk 2: Zhao Song,
Optimization: From linear programming to deep learning

Talk Abstracts.

Elaine Shi (CMU)

Title: Can we beat the aks sorting network

Kai-Min Chung (Academia Sinica)

Title: How well can a classical client delegate quantum computation?

Hubert Chan (HKU)

Title: Opinion Dynamics with Varying Susceptibility to Persuasion via Non-Convex Local Search

Zhao Song (IAS)

Title: Optimization: From linear programming to deep learning

Feng-Hao Liu (FAU)

Title: Rivalry and Friendship between Cryptography and Quantum Science -- Challenges and New Opportunities

Ho-Lin Chen (NTU)

Title: Self-Stabilizing Leader Election in Population Protocols

Abstract:

Population protocols are used as a distributed model that captures the behavior of passively mobile agents. Leader election is one of the most well-studied problems in this model. In this research, we focus on the self-stabilizing leader election (SSLE) problem proposed by Angluin et al. Previously, it is known that SSLE can be performed on arbitrary rings with odd sizes, but SSLE on complete graphs requires Ω(n) states.

In this research, we propose the first SSLE population protocol for rings of arbitrary sizes. This protocol only uses a constant number of states, which solves an open question proposed in the original Angluin et al. paper. We then generalized our design to arbitrary k-regular graphs. The protocol is simple and intuitive but the number of states is exponential in the degree k, but is independent of the size of the graph. Finally, we construct an SSLE protocol for k-regular graphs in which the number of state is polynomial in k.

Chi-Ning Chou (Harvard University)

Title: Toward Spoofing Linear Cross-Entropy Benchmarking in Google’s Quantum Supremacy

Nai-Hui Chia (QuICS)

Title: Quantum meets MCSP

Xiong Fan (UMD)

Title: Design and Formally Verify Post-Quantum Cryptography

Bo-Yin Yang (Academia Sinica)

Title: Time-constant GCD and modular inversion

Xiaorui Sun (UIC)

Title: Fully dynamic c-edge connectivity in subpolynomial time

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), Kai-Min Chung (Academia Sinica), Chung-Shou Liao (NTHU), and Elaine Shi (CMU)