Error detection and correction

Locally testable code

A locally testable code is a type of error-correcting code for which it can be determined if a string is a word in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly. In contrast, locally decodable codes use a small number of bits of the codeword to probabilistically recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable. Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy. (Wikipedia).

Video thumbnail

Locally testable codes with constant rate, distance, and locality, Part I - Irit Dinur

Computer Science/Discrete Mathematics Seminar I Topic: Locally testable codes with constant rate, distance, and locality, Part I Speaker: Irit Dinur Affiliation: Weizmann Institute Date: October 25, 2021 A locally testable code (LTC) is an error correcting code that admits a very efficie

From playlist Mathematics

Video thumbnail

Locally testable codes with constant rate, distance, and locality, Part II - Irit Dinur

Computer Science/Discrete Mathematics Seminar II Topic: Locally testable codes with constant rate, distance, and locality, Part II Speaker: Irit Dinur Affiliation: Weizmann Institute Date: October 26, 2021 A locally testable code (LTC) is an error correcting code that admits a very effic

From playlist Mathematics

Video thumbnail

Using the vertical line test to determine if a graph is a function or not

๐Ÿ‘‰ Learn how to determine whether relations such as equations, graphs, ordered pairs, mapping and tables represent a function. A function is defined as a rule which assigns an input to a unique output. Hence, one major requirement of a function is that the function yields one and only one r

From playlist What is the Domain and Range of the Function

Video thumbnail

How to determine if a set of points is a function, onto, one to one, domain, range

๐Ÿ‘‰ Learn how to determine whether relations such as equations, graphs, ordered pairs, mapping and tables represent a function. A function is defined as a rule which assigns an input to a unique output. Hence, one major requirement of a function is that the function yields one and only one r

From playlist What is the Domain and Range of the Function

Video thumbnail

Determine the domain, range and if a relation is a function

๐Ÿ‘‰ Learn how to determine whether relations such as equations, graphs, ordered pairs, mapping and tables represent a function. A function is defined as a rule which assigns an input to a unique output. Hence, one major requirement of a function is that the function yields one and only one r

From playlist What is the Domain and Range of the Function

Video thumbnail

Determine if the equation represents a function

๐Ÿ‘‰ Learn how to determine whether relations such as equations, graphs, ordered pairs, mapping and tables represent a function. A function is defined as a rule which assigns an input to a unique output. Hence, one major requirement of a function is that the function yields one and only one r

From playlist What is the Domain and Range of the Function

Video thumbnail

Importing and Manipulating Data Sets

Get a Free Trial: https://goo.gl/C2Y9A5 Get Pricing Info: https://goo.gl/kDvGHt Ready to Buy: https://goo.gl/vsIeA5 Import test data for estimating the model and validating results. For more videos, visit http://www.mathworks.com/products/sysid/examples.html

From playlist Control System Design and Analysis

Video thumbnail

How to determine if an ordered pair is a function or not

๐Ÿ‘‰ Learn how to determine whether relations such as equations, graphs, ordered pairs, mapping and tables represent a function. A function is defined as a rule which assigns an input to a unique output. Hence, one major requirement of a function is that the function yields one and only one r

From playlist What is the Domain and Range of the Function

Video thumbnail

Lifting small locally testable codes (LTCs) to large LTCs via HDXs - Prahladh Harsha

Computer Science/Discrete Mathematics Seminar I Topic: Lifting small locally testable codes (LTCs) to large LTCs via HDXs Speaker: Prahladh Harsha Affiliation: Tata Institute of Fundamental Research Date: November 25, 2019 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Locally testable and locally correctable codes approaching the GV bound - Shubhangi Saraf

Computer Science/Discrete Mathematics Seminar I Topic: Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound Speaker: Shubhangi Sara Affiliation: Rutgers University Date: November 27, 2017 For more videos, please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

2 Minute Quickie - How to make your own QR code using Mathematica

In this two minute quickie I am going to show you how to make your own QR code using Mathematica. Here is what I type: b = BarcodeImage["http://www.partridgegetslucky.com/", "QR"] r = BarcodeRecognize[b]; SystemOpen[r] For information on private tutoring, see the about section of my c

From playlist Mathematica Programming

Video thumbnail

Stability and testability - a computational perspectiveJonathan Mosheiff

Stability and Testability Topic: Stability and testability - a computational perspective Speaker: Jonathan Mosheiff Affiliation: Carnegie Mellon University Date: October 21, 2020 For more video please visit http://video.ias.edu

From playlist Stability and Testability

Video thumbnail

Workshop 1 "Operator Algebras and Quantum Information Theory" - CEB T3 2017 - A.Harrow

Aram Harrow (MIT) / 15.09.17 Title: Local Hamiltonians Whose Ground States are Hard to Approximate Abstract: Ground states of local Hamiltonians are typically highly entangled: any quantum circuit that generates them (even approximately) must be sufficiently deep to allow coupling (entan

From playlist 2017 - T3 - Analysis in Quantum Information Theory - CEB Trimester

Video thumbnail

New Locally Decodable Codes from Lifting - Madhu Sudan

Madhu Sudan Microsoft Research March 25, 2013 Locally decodable codes (LDCs) are error-correcting codes that allow for highly-efficient recovery of "pieces" of information even after arbitrary corruption of a codeword. Locally testable codes (LTCs) are those that allow for highly-efficient

From playlist Mathematics

Video thumbnail

The PCP theorem, locally testable codes, and property testing - Irit Dinur

Stability and Testability Topic: The PCP theorem, locally testable codes, and property testing Speaker: Irit Dinur Affiliation: Weizmann Institute of Science Date: January 13, 2021 For more video please visit http://video.ias.edu

From playlist Stability and Testability

Video thumbnail

High Dimensional Expansion and Error Correcting Codes - Irit Dinur

Hermann Weyl Lectures Topic: High Dimensional Expansion and Error Correcting Codes Speaker: Irit Dinur Affiliation: Weizmann Institute of Science; Visiting Professor, School of Mathematics Date: November 19, 2019 For more video please visit http://video.ias.edu

From playlist Hermann Weyl Lectures

Video thumbnail

Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity - Eli Ben-Sasson

Eli Ben-Sasson Technion; Massachusetts Institute of Technology March 18, 2013 The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a s

From playlist Mathematics

Video thumbnail

Learn how to determine the domain and range from a table and from a graph

๐Ÿ‘‰ functions are the possible output values (y-values) of the function. To find the domain of a function from a table we list out the set of the input values and for the range we list out the set of output values. To find the domain and the range of a function from a graph, we use the behav

From playlist What is the Domain and Range of the Function

Related pages

Long code (mathematics) | Hamming distance | Gilbertโ€“Varshamov bound | Hamming code | Code word | Expander code | Locally decodable code | Hadamard code | String (computer science)