All reports by Author Kai-Min Chung:

__
TR20-090
| 10th June 2020
__

Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian#### Tight Quantum Time-Space Tradeoffs for Function Inversion

Revisions: 1

__
TR14-149
| 10th November 2014
__

Kai-Min Chung, Xin Li, Xiaodi Wu#### Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications

__
TR09-109
| 3rd November 2009
__

Kai-Min Chung, Feng-Hao Liu#### Tight Parallel Repetition Theorems for Public-coin Arguments

__
TR07-030
| 29th March 2007
__

Kai-Min Chung, Omer Reingold, Salil Vadhan#### S-T Connectivity on Digraphs with a Known Stationary Distribution

Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian

In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>>

Kai-Min Chung, Xin Li, Xiaodi Wu

We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new ... more >>>

Kai-Min Chung, Feng-Hao Liu

Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition ... more >>>

Kai-Min Chung, Omer Reingold, Salil Vadhan

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... more >>>