40 citations · 92 across the 28 of their papers we have counts for
4 papers · 1 filter
On the Hardness of Massively Parallel Computation
Kai-Min Chung, Kuan-Yi Ho, Xiaorui Sun
We investigate whether there are inherent limits of parallelization in the (randomized) massively parallel computation (MPC) model by comparing it with the (sequential) RAM model.…
Space-efficient classical and quantum algorithms for the shortest vector problem
Yanlin Chen, Kai-Min Chung, Ching-Yi Lai
A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conject…
Tight Bounds for Hashing Block Sources
Kai-Min Chung, Salil Vadhan
It is known that if a 2-universal hash function is applied to elements of a {\em block source} , where each item has enough min-entropy conditioned on the…
AMS Without 4-Wise Independence on Product Domains
Vladimir Braverman, Kai-Min Chung, Zhenming Liu +2
In their seminal work, Alon, Matias, and Szegedy introduced several sketching techniques, including showing that 4-wise independence is sufficient to obtain good approximations of…