Ziyang Jin

Hi there, welcome to my homepage!

I am a first year Ph.D. student at the University of Toronto, where I am very fortunate to be supervised by Akshayaram Srinivasan. Previously, I completed my M.Sc. in computer science also at UofT, under the great supervision of Mike Molloy. Before that, I obtained a B.Sc. in computer science at The University of British Columbia [1], where I was inspired by Will Evans and Nick Harvey. I am generally interested in theoretical computer science, especially cryptography, complexity theory, information theory, game theory, sublinear algorithms and streaming algorithms.

My current research focuses on:

Cryptography: I currently study secure multi-party computation (MPC). An MPC protocol allows multiple parties to jointly compute a function while keeping each party's input private. Furthermore, if an adversary corrupts some parties participating the protocol, these corrupted parties jointly cannot learn anything beyond their inputs and the function output. In the literature, there are two types of adversaries: semi-honest adversaries and malicious adversaries. Semi-honest adversaries follow the protocol but try to learn extra information from the transcript of the communication. Malicious adversaries can deviate from the protocol arbitrarily. MPC protocols that are secure against semi-honest adversaries are usually easy to build and efficient, while MPC protocols that are secure against malicious adversaries require a lot more work to make them efficient. My research aims to bridge the efficiency gap between semi-honest secure protocols and malicious secure protocols [2].
The probabilistic method: The probabilistic method is a technique for proving the existence of a combinatorial structure with certain properties, which is pioneered by Paul Erdős in the 1940s. In brief, "in order to prove the existence of a combinatorial structure with certain properties, we construct an appropriate probability space and show that a random chosen element in this space has the desired properties with positive probability" [3]. Tools that are commonly used in the probablistic method include linearity of expectation, various concentration bounds, Lovász Local Lemma, and entropy compression [4]. The main research I am currently doing is to use the probablisitc method to prove results on graph colouring problems [5].

Email: [firstname] [at] cs [dot] toronto [dot] edu

CV: my CV (last updated: March 2024)

Research

Publications

[Master Thesis] Frugal Colouring of Graphs with Girth At Least Five [8]

Talks

Date	Event	Title
2024-03-13	Theory Student Seminar	Yao's Garbled Circuits and Some Primitives in Cryptography [9]
2024-01-24	Theory Student Seminar	Frugal Colouring of Graphs with Girth At Least Five
2023-10-11	Theory Student Seminar	Graph Colouring and the Rödl Nibble
2023-06-15	Theory Reading Group	Sunflowers: From Soil to Oil [Rao23]
2023-04-26	Theory Student Seminar	The Probabilistic Method and Entropy Compression

Unpublished Write-ups

2024	Non-interactive Zero-Knowledge Proof of 3 Colouring	Notes
2024	Doubly Efficient Proof Systems [GKR08]	Notes and Slides
2023	Entropy Compression and Frugal Colouring	Notes
2022	The Puzzle Toad No. 39	Our solution

Teaching

Term	Role	Course Code	Title	Notes
University of Toronto
2024 Winter [6]	TA	CSC 310	Information Theory
2024 Winter	Lead TA	CSC 373	Algorithm Design, Analysis, and Complexity
2023 Fall	Instructor	CSC 236	Introduction to the Theory of Computation	Section `LEC5101`.
2023 Summer	Prep TA [7]	CSC 240	Enriched Introduction to the Theory of Computation
2023 Summer	TA	CSC C63 (UTSC)	Computability and Computational Complexity
2023 Winter	Instructor	CSC 373	Algorithm Design, Analysis, and Complexity	Section `LEC0301`.


The University of British Columbia
Term	Role	Course Code	Title
2019 Winter	TA	CPSC 320	Intermediate Algorithm Design and Analysis
2018 Fall	TA	CPSC 311	Definition of Programming Languages
2018 Winter	TA	CPSC 313	Computer Hardware and Operating Systems
2016 Summer, 2016 Fall	TA	CPSC 221	Basic Algorithms and Data Structures
2015 Summer, 2015 Fall, 2016 Winter	TA	CPSC 121	Models of Computation

Footnotes

[1] Not a typo. The word "The" is part of the official name of The University of British Columbia.
[2] A paper that bridges the gap between semi-honest MPC protocols and malicious MPC protocols is Founding Cryptography on Oblivious Transfer --- Efficiently by Ishai, Prabhakaran, Sahai.
[3] This sentence is taken from the preface of the book The Probabilistic Method by Alon and Spencer.
[4] The name entropy compression comes from Terence Tao's blog. The technique was introduced by Moser in his paper A constructive proof of the geneal Lovász Local Lemma.
[5] To understand more about applying the probabilistic method to graph coloring, see the book Graph Coloring and the Probablistic Method by Molloy and Reed.
[6] Winter term is from January to April. Some universities may call it Spring term but the weather is often cold in Toronto between January and April.
[7] I draft assignment questions and solutions under the supervision of Faith Ellen to prepare for CSC 240 in 2024 Winter.
[8] A masters thesis is not an official publication. We are trying to improve the result, and that is why I delay posting the full version online.
[9] I give a board talk based on the paper A Proof of Security of Yao's Protocol for Two-Party Computation by Lindell and Pinkas.