Malone 228

\nThe thesis focus on two problems about pseudorandom constructions.

\nTh e first problem is how to compute pseudorandom constructions by constant d epth circuits. Pseudorandom constructions are deterministic functions whic h are used to substitute random constructions in various computational tas ks. Constant depth circuits here refer to the computation model which can compute functions using circuits of AND \, OR and negation gates\, with co nstant depth\, unbounded fan-in\, taking function inputs by input wires an d giving function outputs by output wires. They can be simulated by fast p arallel algorithms. We study such constructions mainly for randomness extr actors\, secret sharing schemes and their applications. Randomness extract ors are functions which transform biased random bits to uniform ones. They can be used to recycle random bits in computations if there are some entr opies remaining. Secret sharing schemes efficiently share secrets among mu lti-parties s.t. the collusion of a bounded number of parties cannot recov er any information of the secret while a certain larger number of parties can recover the secret. Our work constructs these objects with near optima l parameters and explores their applications.

\nThe second problem i s about applying pseudorandom constructions to build error correcting code s (ECCs) for edit distance. ECCs project messages to codewords in a metric space s.t. one can recover the codewords even if there are bounded number of errors which can drive the codeword away by some bounded distance. The y are widely used in both the theoretical and practical part of computer s cience. Classic errors are hamming errors which are substitutions and eras ures of symbols. They are well studied by numerous literatures before. We consider one kind of more general errors i.e. edit errors\, consists of in sertions and deletions that may change the positions of symbols. Our work give explicit constructions of binary ECCs for edit errors with redundancy length near optimal. The constructions utilize document exchange protocol s which can let two party synchronize their strings with bounded edit dist ance\, by letting one party send a short sketch of its string to the other . We apply various pseudorandom constructions to get deterministic documen t exchange protocols from randomized ones. Then we construct ECCs using th em. We also extend these constructions to handle block insertions/deletion s and transpositions. All these constructions have near optimal parameters .

\nI am a PhD candidate at Johns Hopkins University\, Computer Science Department\, advised by Xin Li.

\nMy current resea
rch is about Randomness and Combinatorics in Computation\, and their appli
cations to Complexity Theory\, Information Theory\, etc.

\nMachine Le
arning\, Networks and other topics in Computer Science are also interestin
g to me.

Before Hopkins\, I received a MSE degree from Tsinghua Un iversity and a B.E. degree from Shandong University.

\nI like playin g soccer\, basketball\, music and travelling in my spare time.

\nProf. Xin Li

DTSTART;TZID=America/New_York:20190521T100000 DTEND;TZID=America/New_York:20190521T120000 SEQUENCE:0 SUMMARY:Computer Science Student Defense: Kuan Cheng\, Johns Hopkins Univer sity – “Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance” URL:https://www.cs.jhu.edu/events/computer-science-student-defense-kuan-che ng-johns-hopkins-university-pseudorandom-constructions-computing-in-parall el-and-applications-to-edit-error-correction/ END:VEVENT END:VCALENDAR