Kai-Min Chung

Postdoctoral Research Associate

Department of Computer Science, Cornell University

Upson Hall 4108

Ithaca, NY 14850

chung [at] cs.cornell.edu

I am a postdoc at Cornell University working under the supervision of Rafael Pass and supported by Simons Postdoctoral Fellowship. I received my Ph.D. in computer science at Harvard University, where I was very fortunate to have Salil Vadhan as my advisor. My research interests are in the fields of cryptography, complexity theory, and pseudorandomness.

Before my Ph.D., I grew up in Taiwan, and received my bachelor degree from National Taiwan University. During my undergraduate studies, I worked on algorithms and machine learning.

Please check here for my CV (updated 1/11/2012).

Ph.D. Thesis

Efficient Parallel Repetition Theorems with Applications to Security Amplification,

Ph.D. Thesis (March 2011)

[ pdf ]

Selected Publications (Full List)

The Randomness Complexity of Parallel Repetition,

with Rafael Pass

FOCS 2011

[ full-version ]

Memory Delegation,

with Yael Tauman Kalai, Feng-Hao Liu, Ran Raz

CRYPTO 2011

[ full-version ]

Parallel Repetition Theorems for Interactive Arguments,

with Feng-Hao Liu

TCC 2010, Best Student Paper Award

[ conf-version ] (See my Ph.D. thesis for all details)

Full Publications

A Computational Incompleteness Theorem for Forecast Testing,

with Edward Lui, and Rafael Pass

in submission to STOC 2012 [ submit-version ]

The Knowledge Tightness of Parallel Zero-Knowledge,

with Rafael Pass, and Wei-Lung Dustin Tseng

TCC 2012

[ full-version ]

Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified,

with Henry Lam, Zhenming Liu, and Michael Mitzenmacher

STACS 2012

[ full-version ]

The Randomness Complexity of Parallel Repetition,

with Rafael Pass

FOCS 2011

[ full-version ]

Memory Delegation,

with Yael Tauman Kalai, Feng-Hao Liu, Ran Raz

CRYPTO 2011

[ full-version ]

Efficient Secure Two-Party Exponentiation,

with Ching-Hua Yu, Sherman S.M. Chow, and Feng-Hao Liu

CT-RSA 2011

[ conf-version ]

Improved Delegation of Computation Using Fully Homomorphic Encryption,

with Yael Tauman Kalai, and Salil P. Vadhan

CRYPTO 2010

[ full-version ]

Efficient String-Commitment from Weak Bit-Commitment,

with Feng-Hao Liu, Chi-Jen Lu, and Bo-Yin Yang

AsiaCrypt 2010

[ conf-version, preliminary-full-version ]

Parallel Repetition Theorems for Interactive Arguments,

with Feng-Hao Liu

TCC 2010, Best Student Paper Award

[ conf-version ] (See my Ph.D. thesis for all details)

AMS Without 4-Wise Independence on Product Domains,

with Vladmir Braverman, Zhenming Liu, Michael Mitzenmacher, and Rafail Ostrovsky

STACS 2010 (this paper is a result of a merge)

[ original version ]

Tight Bounds for Hashing Block Sources,

with Salil P. Vadhan

RANDOM 2008

[ full-version ]

S-T Connectivity on Digraphs with a Known Stationary Distribution,

with Omer Reingold, and Salil P. Vadhan

CCC 2007, ACM Transactions on Algorithms 2011

[ full-version ]

An Optimal Algorithm for the Maximum-Density Segment Problem,

with Hsueh-I Lu

ESA 2003, SIAM J. on Computing 2004

[ full-version ]

Decomposition Methods for Linear Support Vector Machines,

with Wei-Chun Kao, Chia-Liang Sun, and Chih-Jen Lin

ICASSP 2003, Neural Computation 2004

[ full-version ]

Radius Margin Bounds for Support Vector Machines with the RBF Kernel,

with Wei-Chun Kao, Chia-Liang Sun, Li-Lun Wang, and Chih-Jen Lin

ICONIP 2002, Neural Computation 2003

[ full-version ]

Teaching

Teaching Fellow for CS225 Pseudorandomness, Spring 07 and 09, taught by Prof. Salil Vadhan

Received Certificate of Distinction in Teaching in Spring 09