Locally Testable Codes and L_1 Embeddings of Cayley Graphs

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



Duration: 1:13:00
92 views
0


A locally testable code (LTC) is an error correcting code which admits a very efficient procedure for testing membership in the code: a local tester queries few locations in the received word but still distinguishes codewords from words that are far from the code. The main open questions about LTCs are about the tradeoffs possible between rate, distance and query complexity. We show that the local testability of a binary linear code is related (and in fact equivalent) to the L_1 embeddability of a related Cayley graph. Thus one can reformulate existential questions about LTCs as questions about the existance of certain Cayley graphs that admit constant distortion embeddings into L_1. We discuss what this tells us about existing results on LTCs and what it might tell us about new results. Joint work with Salil Vadhan (Harvard) and Yuan Zhou (CMU).




Other Videos By Microsoft Research


2016-08-08The 3rd Age of Computing
2016-08-08Computational Fair Division: From Cake Cutting to Cluster Computing
2016-08-08Student Session: Learning Cloud Computing, Environmental Science, and You
2016-08-08Machine Learning Day 2013 - Deep Learning; A Bayesian Information Criterion for Singular Models
2016-08-08IEEE eScience Keynote: From Genes to Stars
2016-08-08Large-Scale Data Analysis for Biomedical and Social Sciences - Tom Cai
2016-08-08Large-Scale Data Analysis for Biomedical and Social Sciences - Takayuki Okatani
2016-08-08Tutorial 2 - Kinect for Windows in Science Applications - SDK Introduction
2016-08-08Machine Learning Day 2013 - Clustering; Geometry Preserving Non-Linear Dimension Reduction
2016-08-08From Smart Sensors to City OS (II) - Panel Discussion
2016-08-08Locally Testable Codes and L_1 Embeddings of Cayley Graphs
2016-08-08Interactive Visual Analytics for Scientific Discovery - Solving Problems with Visual Analytics
2016-08-08Big Planet Big Questions, Big Data Big Science - Fetch Climate
2016-08-08From Smart Sensors to City OS (II) - Lei Chen
2016-08-08Tutorial 1: Azure Platform for Cloud Computing - Windows Azure Virtual Machines
2016-08-08From Smart Sensors to City OS (II) - Zhen Liu
2016-08-08Tutorial 1: Azure Platform for Cloud Computing - Windows Azure SOI Database and Storage
2016-08-08From Smart Sensors to City OS (I) - Geospatial Service Web
2016-08-08From Smart Sensors to City OS-How to Design for Long-Term Usage in Behavior Sensing and Feedback
2016-08-08Data Driven Applications - Power BI
2016-08-08Victor Bahl�s SIGMOBILE 2013 Outstanding Contributions Award Talk



Tags:
microsoft research