#GoldreichTestableCodesSurvey-2
"Abstract
We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Local testability refers to approximately testing large objects based on a very small
>
>number of probes, each retrieving a single bit in the representation of the object.
This yields super-fast approximate #testing of the corresponding property (ie., be a codeword or a valid proof).
We also review the related concept of local decodable [recte 'locally decodable'
>
>LG,I]
The survey consists of two independent (i.e., self-contained) parts that cover the same material at different levels of rigor and detail. Still, in spite of the repetitions, there may be a benefit in reading both parts.

Keywords
#ErrorCorrectingCodes
Probabilistically
>
>Checkable Proofs (#PCP)
Locally Testable Codes
Locally Decodable Codes
Self-Correction
Low-Degree Tests
Derandomization
Private Information Retrieval"

M.t. 'Kurzfassung
Wir geben eine Übersicht zu bekannten Ergebnissen zum Thema lokaltestbare Codes (bzw. Beweise), wobei
>

• • •

Missing some Tweet in this thread? You can try to force a refresh
 

Keep Current with Logic Geometry, Information

Logic Geometry, Information Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @LGcommaI

3 Jan
#GoldreichTestableCodesSurvey-5

"Local testability
By local testability we mean that the object can be tested for the natural property (i.e., being a codeword or a valid proof) using a small (typically constant)[Footnote: In this part, we associate local testability with tests
>
>that perform a constant number of probes.] number of probes, each recovering individual bits in a standard representation of the object. Thus, local testability allows for super-fast testing of the corresponding objects. The tests are probabilistic and hence the result
>
>is correct only with high probability.[Footnote: It is easy to see that deterministic tests will perform very poorly, and the same holds with respect to probabilistic tests that make no error.] Furthermore, correctness refers to a relaxed notion of deciding (which
>
Read 5 tweets
2 Jan
C. Teevs, ISBN 9783531164830: "[Er] ist ein Exot in der bundesdeutschen Politikerlandschaft..
Von..#Medien seit jeher gerne befragt.., ist er für die Parteiführung der #SPD zum..Ärgernis geworden.
..#Lauterbach [gehört] zu den unbeliebtesten Abgeordneten seiner Fraktion – aber
> Image
>auch zu den spannendsten[!]

Wie kam es dazu, dass der C4-Professor für Gesundheitsökonomie sein eigenes Institut hinter sich ließ und sich um ein Bundestagsmandat bewarb?
Die biografischen und strukturellen Hintergründe dieses Seiteneinstiegs werden geschildert und analysiert."
Quelle: Image
Read 5 tweets
2 Jan
#Geschichte:#History
#Lauterbach (ein wichtiger Berater von UllaSchmid)

#stern 2004 [archive.is/n97o1]: "Der große Pfusch

Zorn bei..Patienten
Zoff in..Arztpraxen..
Zank mit..Krankenkassen
Ulla Schmidts Gesetz startete chaotisch und muss nun kräftig nachgebessert werden
>
>..Morddrohungen
..Frau..im Schlamassel..
..Schmidt..unbeliebteste Politikerin
..ZDF-Politbarometer

[Versicherte], die immer noch auf Beitragssenkungen warten
[Notfallpatienten], die in der Ambulanz mehrfach zur Kasse gebeten wurden
[Gehbehinderte], denen die Kasse nicht mehr
>
>Fahrt zum Arzt bezahlen wollte
[Diabetiker, MS-Kranke und Aids-Patienten], die nicht mehr als chronisch krank gelten sollten und sich vor hohen Zuzahlungen ängstigten
[Heimbewohner], die im Januar ihr gesamtes Taschengeld für Selbstbeteiligungen ausgeben sollten
[Arbeitnehmer]
>
Read 16 tweets
2 Jan
#GoldreichTestableCodesSurvey-4

"Codes, proofs and their length
Codes are sets of strings (of equal length), typically, having a large pairwise distance. Equivalently, codes are viewed as mappings from short (𝑘-bit) strings to longer (𝑛-bit) strings, called codewords,
>
>such that the codewords are distant from one another. We will focus on codes with relative constant distance; that is, every two 𝑛-bit codewords are at distance Ω(𝑛) apart. The length of the code is measured in terms of the length of the pre-image (i.e., we are interested
>
>in the growth of 𝑛 as a function of 𝑘).
Turning to proofs, these are defined with respect to a verification procedure for assertions of a certain length, and their length is measured in terms of the length of the assertion. The verification procedure must satisfy the natural
>
Read 5 tweets
2 Jan
Isn't it odd that in their new 1972-review faz.net/aktuell/feuill…, the #FAZ doesn't mention the #MunichMassacre with even one sentence?

#Geschichte:#History
(the article as an image, but in two pieces; piece 1):
Read 4 tweets
2 Jan
Wird hier ein #Lastenausgleichsgesetz 2.0 medial vorbereitet?
Relevanter Kontext: wohlstandschmiede.com/ist-ein-neuer-…("Schon kurz nach Beginn der Pandemie im Frühjahr 2020 wurden Stimmen laut, ein[en] #Lastenausgleich für die von den Regierung verursachten Kosten durch die #Lockdown-Maßnahmen einzuführen. So sprach sich u.a. #SigmarGabriel,
>
>eh. Wirtschaftsminister für einen solchen aus. Begründet hatte er dies mit den Worten: „Wir stehen vor einer dramatischen Entwicklung in unserer Wirtschaft.“. Wohlgemerkt, im April 2020 als noch nicht im Ansatz abzusehen war, wie sich die Pandemie und die..Kosten auswirken
>
Read 4 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Or Donate anonymously using crypto!

Ethereum

0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy

Bitcoin

3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us on Twitter!

:(