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 ]

Manuscripts

Constant-round Concurrent Zero-knowledge from Falsifiable Assumptions,

with Huijia Rachel Lin, and Rafael Pass

In submission.

[ Full version ]

Non-black-box Simulation from One-way Functions and Applications to Resettable Security,

With Karn Seth, and Rafael Pass

In submission.

[ Full version ]

Unprovable Security of Two-Message Zero-Knowledge,

with Edward Lui, Mohammad Mahmoody, and Rafael Pass

Manuscript.

[ Full version ]

On the Lattice Smoothing Parameter Problem,

with Daniel Dadush, Feng-Hao Liu, and Chris Peikert

In submission.

On the (Im)Possibility of Tamper-Resilient Cryptography:

Using Fourier Analysis in Computer Viruses,

with Per Austrin, Mohammad Mahmoody, Rafael Pass, and Karn Seth

In submission.

Publications

Randomness Dependent Message Security,

with Eleanor Birrell, Rafael Pass, and Sidharth Telang

TCC 2013

[ Full version ]

On the Power of Non-uniform Proofs of Security,

with Huijia Rachel Lin, Mohammad Mahmoody, and Rafael Pass

ITCS 2013

[ Conference version ]

A Cryptographic Treatment of Forecast Testing,

with Edward Lui, and Rafael Pass

ITCS 2013

[ Full 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

[ Conference 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

[ Conference version, Draft full version ] (See also my Ph.D. thesis)

Parallel Repetition Theorems for Interactive Arguments,

with Feng-Hao Liu

TCC 2010, Best Student Paper Award

[ Conferece version ] (See my Ph.D. thesis for full 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)

[ Conference version, 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