Zhijun Zhang will present his General Exam on May 12, 2022 at 10am via Zoom.
The members of his committee are as follows: Gillat Kol (adviser), Mark Braverman, and Ran Raz
I will survey my work in the fields of distributed sketching and interactive coding.
Distributed sketching: The shared blackboard model is (arguably) the most basic model for distributed computing. It can also be viewed as a multi-round version of the well-studied sketching model. My recent work gives the first super-constant round lower bounds for some fundamental problems like MIS (minimal independent set), approximate matching, and approximate vertex cover, in the shared blackboard model. These bounds are tight (at least in some settings).
Interactive coding: In the classical setting for error correcting codes, one party (the “sender”) wishes to send a message x to a second party (the “receiver”) over a noisy channel. We consider the coding question over the two-way noisy channel. Here, the sender and receiver can communicate back-and-forth with the goal of the receiver learning x. While it is well known that no binary error correcting code over the (one-way) bit flipping channel can tolerate more than 1/4 fraction of adversarial errors, my work shows that error resilience strictly better than 1/4 can be obtained over the two-way channel.