BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Department of Computer Science - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Department of Computer Science
X-ORIGINAL-URL:https://www.cs.jhu.edu
X-WR-CALDESC:Events for Department of Computer Science
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20180311T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20181104T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20190310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20191103T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20200308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20201101T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20190521T100000
DTEND;TZID=America/New_York:20190521T120000
DTSTAMP:20260422T162848
CREATED:20210629T210719Z
LAST-MODIFIED:20210629T210719Z
UID:1962295-1558432800-1558440000@www.cs.jhu.edu
SUMMARY:Computer Science Student Defense: Kuan Cheng\, Johns Hopkins University – “Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance”
DESCRIPTION:LocationMalone 228AbstractThe thesis focus on two problems about pseudorandom constructions.The first problem is how to compute pseudorandom constructions by constant depth circuits. Pseudorandom constructions are deterministic functions which are used to substitute random constructions in various computational tasks. Constant depth circuits here refer to the computation model which can compute functions using circuits of AND \, OR and negation gates\, with constant depth\, unbounded fan-in\, taking function inputs by input wires and giving function outputs by output wires. They can be simulated by fast parallel algorithms. We study such constructions mainly for randomness extractors\, secret sharing schemes and their applications. Randomness extractors are functions which transform biased random bits to uniform ones. They can be used to recycle random bits in computations if there are some entropies remaining. Secret sharing schemes efficiently share secrets among multi-parties s.t. the collusion of a bounded number of parties cannot recover any information of the secret while a certain larger number of parties can recover the secret. Our work constructs these objects with near optimal parameters and explores their applications.The second problem is about applying pseudorandom 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 the theoretical and practical part of computer science. Classic errors are hamming errors which are substitutions and erasures of symbols. They are well studied by numerous literatures before. We consider one kind of more general 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 constructions utilize document exchange protocols which can let two party synchronize their strings with bounded edit distance\, by letting one party send a short sketch of its string to the other. We apply various pseudorandom constructions to get deterministic document exchange protocols from randomized ones. Then we construct ECCs using them. We also extend these constructions to handle block insertions/deletions and transpositions. All these constructions have near optimal parameters.BioI am a PhD candidate at Johns Hopkins University\, Computer Science Department\, advised by Xin Li.My current research is about Randomness and Combinatorics in Computation\, and their applications to Complexity Theory\, Information Theory\, etc.Machine Learning\, Networks and other topics in Computer Science are also interesting to me.Before Hopkins\, I received a MSE degree from Tsinghua University and a B.E. degree from Shandong University.I like playing soccer\, basketball\, music and travelling in my spare time.HostProf. Xin Li
URL:https://www.cs.jhu.edu/event/computer-science-student-defense-kuan-cheng-johns-hopkins-university-pseudorandom-constructions-computing-in-parallel-and-applications-to-edit-distance/
END:VEVENT
END:VCALENDAR