Malone 228

\nThe thesis focus on two proble ms about pseudorandom constructions.

\nThe first problem is how to c ompute pseudorandom constructions by constant depth circuits. Pseudorandom constructions are deterministic functions which are used to substitute ra ndom constructions in various computational tasks. Constant depth circuits here refer to the computation model which can compute functions using cir cuits of AND \, OR and negation gates\, with constant depth\, unbounded fa n-in\, taking function inputs by input wires and giving function outputs b y output wires. They can be simulated by fast parallel algorithms. We stud y such constructions mainly for randomness extractors\, secret sharing sch emes and their applications. Randomness extractors are functions which tra nsform biased random bits to uniform ones. They can be used to recycle ran dom bits in computations if there are some entropies remaining. Secret sha ring schemes efficiently share secrets among multi-parties s.t. the collus ion of a bounded number of parties cannot recover any information of the s ecret while a certain larger number of parties can recover the secret. Our work constructs these objects with near optimal parameters and explores t heir applications.

\nThe second problem is about applying pseudorand om constructions to build error correcting codes (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. They are widely used in both t he theoretical and practical part of computer science. Classic errors are hamming errors which are substitutions and erasures of symbols. They are w ell studied by numerous literatures before. We consider one kind of more g eneral errors i.e. edit errors\, consists of insertions 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 c onstructions utilize document exchange protocols which can let two party s ynchronize their strings with bounded edit distance\, by letting one party send a short sketch of its string to the other. We apply various pseudora ndom constructions to get deterministic document exchange protocols from r andomized ones. Then we construct ECCs using them. We also extend these co nstructions to handle block insertions/deletions and transpositions. All t hese constructions have near optimal parameters.

\nI a m a PhD candidate at Johns Hopkins University\, Computer Science Departmen t\, advised by Xin Li.

\nMy current research is about Randomness and
Combinatorics in Computation\, and their applications to Complexity Theor
y\, Information Theory\, etc.

\nMachine Learning\, Networks and other
topics in Computer Science are also interesting to me.

Before Hop kins\, I received a MSE degree from Tsinghua University and a B.E. degree from Shandong University.

\nI like playing soccer\, basketball\, mus ic and travelling in my spare time.

\nProf. Xin Li

\n END:VEVENT END:VCALENDAR