BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Relaxed Locally Decodable and Correctable Codes Do Not Need Adapti
 vity and Two-Sided Error - Guy Goldberg (Weizmann Institute)
DTSTART:20250408T130000Z
DTEND:20250408T140000Z
UID:TALK228967@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION: Relaxed locally decodable codes (RLDCs) are error-correcting 
 codes in which individual bits of the message can be recovered by querying
  only a few bits from a noisy codeword.\n\nFor uncorrupted codewords\, and
  for every bit\, the decoder must decode the bit correctly with high proba
 bility.\nHowever\, for a noisy codeword\, a relaxed local decoder is allow
 ed to output a ``rejection'' symbol\, indicating that the decoding failed.
 \n\nWe study the power of adaptivity and two-sided error for RLDCs.\nOur m
 ain result is that if the underlying code is linear\, *adaptivity and two-
 sided error do not give any power to relaxed local decoding.*\nWe construc
 t a reduction from adaptive\, two-sided error relaxed local decoders to no
 n-adaptive\, one-sided error ones.\nThat is\, the reduction produces a rel
 axed local decoder that never errs or rejects if its input is a valid code
 word and makes queries based on its internal randomness (and the requested
  index to decode)\, independently of the input.\nThe reduction essentially
  maintains the query complexity\, requiring at most one additional query.\
 nFor any input\, the decoder's error probability increases at most two-fol
 d.\nFurthermore\, assuming the underlying code is in systematic form\, whe
 re the original message is embedded as the first bits of its encoding\, th
 e reduction also conserves both the code itself and its rate and distance 
 properties\n\nWe base the reduction on our new notion of *additive* promis
 e problems.\nA promise problem is additive if the sum of any two YES-insta
 nces is a YES-instance and the sum of any NO-instance and a YES-instance i
 s a NO-instance.\nThis novel framework captures both linear RLDCs and prop
 erty testing (of linear properties)\, despite their significant difference
 s.\n\nWe prove that in general\, algorithms for *any* additive promise pro
 blem do not gain power from adaptivity or two-sided error\, and obtain the
  result for RLDCs as a special case.\nThe result also holds for relaxed lo
 cally *correctable* codes (RLCCs)\, where a *codeword* bit should be recov
 ered.\n\nAs an application\, we improve the best known lower bound for lin
 ear adaptive RLDCs.\nSpecifically\, we prove that such codes require block
  length of $n \\geq k^{1+\\Omega(1/q^2)}\, where k denotes the message len
 gth and q denotes the number of queries.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR