Low distortion embeddings for edit distance

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=tWIK1FVhjGk


Duration: 52:43
175 views
4

We show a computationally efficient low distortion embedding of the binary cube endowed with edit distance into $\ell_1$. This yields solutions to various computational problems involving edit distance. They include sketching, communication complexity, and nearest neighbor search. For all these problems, we improve upon previous bounds. This is joint work with Rafail Ostrovsky of UCLA.



Other Videos By Microsoft Research


2016-09-07Understanding Group Effectiveness in a Newly Formed Online Community
2016-09-07Supporting Collaboration through Human-Centered Design
2016-09-07Scaling Laws and Tradeoffs in Peer-to-Peer Live Multimedia Streaming
2016-09-07Conference XP - Virrtual Product Development Team Update
2016-09-07The Alice Project: A Different Way to Teach Introductory Computer Science [1/2]
2016-09-07THE TROUBLE WITH PHYSICS
2016-09-07Human Detection and Pose from Images and Videos
2016-09-07The Role of Skill in Internet Use
2016-09-07Conference XP Brasil Report
2016-09-07Learn about Woodland Park ZooΓÇÖs successful programs protecting wildlife
2016-09-07Low distortion embeddings for edit distance
2016-09-07Energy and Bandwidth Efficiency in Wireless Networks
2016-09-07How Helpful is Network Coding?
2016-09-07A Data-Oriented Networking Architecture; RCP: Congestion Control to Minimize Download Time [1/8]
2016-09-07LEAVING MICROSOFT TO CHANGE THE WORLD [1/2]
2016-09-07Visual Recognition and Tracking for Perceptive Interfaces
2016-09-07Filtering of a Group Delay Equalized Delta-Sigma Modulated Envelope Signal in an EER Architecture
2016-09-07P2P Live Streaming: Practice and Theory
2016-09-07Attacks On and From P2P File-Sharing Systems
2016-09-07Microsoft Research: turning ideas into reality for 15 years - Keynote and Demos
2016-09-07The Global Challenge: Giving Students the Tools and Confidence to Solve Global Problems - Together


Tags:
microsoft research