SCS
Student
Seminar
Series

go to the list of abstracts
abstracts

go to the list of previous talks
previous talks

go to the list of other SCS seminars
scs seminars

go to the SCS home page
SCS

go to the CMU home page
CMU

     

The Next Talk Sp'18 Talks General Info Speaking Req't

Synchronization Strings: Communication in the Presence of Insertions and Deletions

Friday, May 11th, 2018 from 12-1 pm in GHC 6501.

Amirbehshad Shahrasbi, CSD

This talk will give an introduction to synchronization strings which provide a novel way of efficiently reducing synchronization errors, such as insertions and deletions, to much more benign and better understood Hamming errors, i.e., symbol erasures and substitutions. Synchronization strings have many applications. The talk will focus on using synchronization strings as a new way to generate efficient error correcting block codes for insertions and deletions. In particular, codes that, for any 0 < eps, delta < 1, achieve a rate of 1 - delta - eps while being able to efficiently decode from a delta fraction of insertions and deletions.

Further applications of synchronization strings will also be briefly discussed including a general method of simulating symbol corruption channels over any given insertion-deletion channel, an efficient and near-optimal coding scheme for interactive communication over insertion-deletion channels, and list-decodable insertion-deletion codes.

This talk is based on a joint work with Bernhard Haeupler.

In Partial Fulfillment of the Speaking Requirement


Spring 2018 Schedule
Mon, Jan 15 GHC 6501 Expired
Fri, Jan 19 GHC 6501 Expired
Mon, Jan 22 GHC 6501 Expired
Fri, Jan 26 GHC 6501 Expired
Mon, Jan 29 GHC 6501 Expired
Fri, Feb 2 GHC 6501 Expired
Mon, Feb 5 GHC 6501 Expired
Fri, Feb 9 GHC 6501 Expired
Mon, Feb 12 GHC 6501 Expired
Fri, Feb 16 GHC 6501 Expired
Mon, Feb 19 GHC 6501 Expired
Fri, Feb 23 GHC 6501 Expired
Mon, Feb 26 GHC 6501 Expired
Fri, Mar 2 GHC 6501 Expired
Mon, Mar 5 GHC 6501 Expired
Fri, Mar 9 GHC 6501 Expired
Mon, Mar 12 GHC 6501 Expired
Fri, Mar 16 GHC 6501 Expired
Mon, Mar 19 GHC 6501 Expired
Fri, Mar 23 NSH 1507 Expired
Mon, Mar 26 GHC 6501 Brandon Bohrer CoasterX: A Case Study in Component-Driven Hybrid Systems Proof Automation
Fri, Mar 30 GHC 6501 Expired
Mon, Apr 2 GHC 6501 Expired
Fri, Apr 6 GHC 6501 Kijung Shin Why You Should Charge Your Friends for Borrowing Your Stuff
Mon, Apr 9 GHC 6501 Expired
Fri, Apr 13 GHC 6501 Expired
Mon, Apr 16 GHC 6501 Charles McGuffey Designing Algorithms to Tolerate Processor Faults
Fri, Apr 20 GHC 6501 Calvin McCarter [CANCELED] Learning a Gene Network underlying Clinical Phenotypes under Genome-wide SNP Perturbations
Mon, Apr 23 GHC 6501 Carlo Angiuli Computing with Univalence in Cartesian Cubical Type Theory
Fri, Apr 27 GHC 6501 Qing Zheng Light-Weight In-Situ Indexing For Scientific Workloads
Mon, Apr 30 GHC 6501 Eric Lei [CANCELED] Learning Mixtures of Multi-Output Regression Models By Correlation Clustering for Multi-View Data
Fri, May 4 GHC 6501 Yimeng Zhang Convolutional Neural Network Models of V1 Responses to Complex Patterns
Mon, May 7 GHC 6501 Han Zhao Multiple Source Domain Adaptation with Adversarial Learning
Fri, May 11 GHC 6501 Amirbehshad Shahrasbi Synchronization Strings: Communication in the Presence of Insertions and Deletions


General Info

The Student Seminar Series is an informal research seminar by and for SCS graduate students from noon to 1 pm on Tuesdays and Fridays. Lunch is provided by the Computer Science Department (personal thanks to Sharon Burks and Debbie Cavlovich!). At each meeting, a different student speaker will give an informal, 40-minute talk about his/her research, followed by questions/suggestions/brainstorming. We try to attract people with a diverse set of interests, and encourage speakers to present at a very general, accessible level.

So why are we doing this and why take part? In the best case scenario, this will lead to some interesting cross-disciplinary work among people in different fields and people may get some new ideas about their research. In the worst case scenario, a few people will practice their public speaking and the rest get together for a free lunch.


Guideline & Speaking Requirement Need-to-Know

Note: Step #1 below are applicable to all SSS speakers. You can schedule AT MOST THREE talks per semester.

SSS is an ideal forum for SCS students to give presentations that count toward fulfilling their speaking requirements. The specifics, though, vary with each department. For instance, students in CSD will need to be familiar with the notes in Section 8 of the Ph.D. document and follow the instructions outlined on the Speakers Club homepage. Roughly speaking, these are the steps:

  1. Schedule a talk with SSS by sending your talk title, abstract, additional info (like "Joint work with..." or "In Partial Fulfillment of the Speaking Requirement"), and a picture of yourself (preferably jpeg) to sss@cs at least TWO WEEKS before your scheduled talk.
  2. After you are confirmed with your SSS slot, go to the Speakers Club Calendar and schedule your talk at least THREE WEEKS in advance of the talk date.
  3. On the day of your talk, make sure you print Speakers Club evaluation forms for your evaluators to use.
Students outside of CSD will need to check with their respective departments regarding the procedure. As another example, ISRI students fulfill their speaking requirements by attending a semesterly Software Research Seminar and giving X number of presentations per school year. If you have experience with your department that might help others in your department, please feel free to contribute your knowledge by emailing us. Thank you!


SSS Coordinators

Armaghan Naik, Computational Biology
Lin Xiao, CSD
Qing Zheng, CSD

 


Web contact: sss+www@cs