Ziyang Jin

 

 

Hi there, welcome to my homepage!

I am a second year Ph.D. student studying theoretical computer science (TCS) at the University of Toronto, where I am very fortunate to be supervised by Akshayaram Srinivasan to work on exciting topics in cryptography. Previously, I completed my M.Sc. in computer science also at UofT, under great supervision of Mike Molloy in graph theory. Before that, I worked as a software enigneer at Amazon. A few years ago, I obtained a B.Sc. in computer science at The University of British Columbia (UBC) [1], where I was inspired by Will Evans and Nick Harvey to study theoretical computer science. Feel free to drop me an email for your great research ideas, or just say hi to me.

More specifically, my research interest lies in:

• Secure Multiparty Computation: Secure multiparty computation (MPC) is about constructing protocols for $n$ parties to jointly compute a functionality $f(x_1,\; ...\; ,x_{\mathrm{n}})$ while keeping each party's input $x_i$ private. Furthermore, if a subset of parties are corrupted by an adversary, these corrupted parties jointly cannot learn anything beyond what can be inferred from their own private inputs and the function output. Two main types of adversaries are usually considered: semi-honest adversary and malicious adversary. A semi-honest adversary follows the protocol specification but tries to learn extra information from its transcript of communication. On the other hand, a malicious adversary can deviate from the protocol arbitrarily. Some well-known MPC protocols are [Yao86], [GMW87], [BGW88], [CCD88], [BMR90].
• Zero-Knowledge Proofs: In a common setup, there are two parties, the prover and the verifier. A zero-knowledge proof [GMR85][Babai85] allows the prover to prove a statement $x$ to the verifier such that the verifier does not learn any information (regarding how the statement is proved) other than the statement $x$ is true. This is usually done by interactions between the prover and the verifier. The verifier asks some randomized questions about the statement and if the statement is true, the prover should be able to answer these questions. If the statement is false, the prover fails to answer the questions with certain probability, even if the prover has unbounded computation power. Zero-knowledge means that if the verifier can simulate the interaction with the prover in its head such that the view of the verifier is indistinguishable between the real interaction with the prover and the simulation by the verifier itself, then the verifier does not gain "knowledge" [2].

I also like combinatorial algorithms, game theory, complexity theory, and coding theory. I am also interested in applying cryptography in real-world applications.

Email: [all-lower-case-first-name] [at] $\mathrm{cs}$ [dot] $\mathrm{toronto}$ [dot] $\mathrm{edu}$ | LinkedIn | GitHub

For incoming theory students (2025 Fall), we have a Discord server for theory students, feel free to email me so I send you the invitation link.

Thesis

1. [Master's Thesis] Frugal Colouring of Graphs with Girth At Least Five
   • We proved that for any graph with girth at least five and maximum degree $d$, there exists a $(1+o(1))(d/lnd)$-colouring such that for every vertex $v$, no colour appears more than polylog($d$) times in the neighbourhood of $v$. Our work employs a technique called the semi-random method (a.k.a. the Rödl Nibble) and bases on the proof in [Kim95] for bounding the chromatic number of girth five graphs. We use a non-trivial lopsided Lovász Local Lemma to complete the colouring.

Selected Talks

Date	Institute	Event	Title
2025-02-27	University of Toronto	Theory Student Seminar	Polishchuk-Spielman Bivariate Testing and An Application [PS94]
2025-01-17	University of Toronto	Crypto Reading Group	SNARGs under LWE via propositional proofs [JKLV24]
2025-01-10	University of Toronto	Crypto Reading Group	Universal SNARGs for NP from Proofs of Correctness [JKLM24]
2024-06-13	University of Toronto	Theory Reading Group	Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method [BKR23]
2024-01-24	University of Toronto	Theory Student Seminar	Frugal Colouring of Graphs with Girth At Least Five
2023-10-11	University of Toronto	Theory Student Seminar	Graph Colouring and the Rödl Nibble
2023-04-26	University of Toronto	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

• Reviewer: ICALP 2024, Crypto 2025

University of Toronto
Term	Role	Course Code	Title
2025 Winter	Lead TA	CSC 165	Mathematical Expression and Reasoning for Computer Science
2025 Winter	TA	CSC 263 (UTM)	Data Structures and Analysis
2024 Fall	TA	CSC WDI (UTM)	Writing Development Initiative for CSC207, CSC258, CSC236, CSC373
2024 Fall	TA	CSC 263	Data Structures and Analysis
2024 Winter	TA	CSC 310	Information Theory
2024 Winter	Lead TA	CSC 373	Algorithm Design, Analysis, and Complexity
2023 Fall	Instructor [3]	CSC 236	Introduction to the Theory of Computation
2023 Summer	Prep TA [4]	CSC 240	Enriched Introduction to the Theory of Computation
2023 Summer	TA	CSC C63 (UTSC)	Computability and Computational Complexity
2023 Winter	Instructor [3]	CSC 373	Algorithm Design, Analysis, and Complexity
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 & Fall	TA	CPSC 221	Basic Algorithms and Data Structures
2015 Summer & Fall, 2016 Winter	TA	CPSC 121	Models of Computation

• [GAAP 2024] The Toronto Graduate Application Assistance Program is a student-run, volunteer-led program to help students prepare applications to MSc and PhD program in computer science at UofT. I was a mentor in year 2024-2025, mainly for applicants who are interested in theoretical computer science.

• [Theory Website Contribution] You are welcome to contribute to the theory group's official website. Having a modern, up-to-date website is crucial for us to attract students and researchers to our group.
• [Theory Student Seminar] We are looking for speakers. If you are a researcher in theoretical computer science and would like to give a talk, feel free to email tssadmin@cs.toronto.edu
• [Life in Toronto] My personal recommendations for living in Toronto.

• [1] Not a typo. The word "The" is part of the official name of The University of British Columbia.
• [2] A YouTube video that explains the concept of zero-knowledge proofs by Amit Sahai: Computer Scientist Explains One Concept in 5 Levels of Difficulty | WIRED.
• [3] If you need one last recommendation letter for gradudate school applications, I am happy to write a letter for you. Note that I can only write about your course performance; I am unable to comment on your research abilities if you have never worked with me on research projects.
• [4] I draft assignment questions and solutions under the supervision of Faith Ellen to prepare for CSC 240 in 2024 Winter.