Outlaw distributions and locally decodable codes

DOI10.4086/TOC.2019.V015A012zbMATH Open1477.94080OpenAlexW3132630448MaRDI QIDQ5204830FDOQ5204830

Authors: Jop Briët, Zeev Dvir, Sivakanth Gopi 

Publication date: 5 December 2019

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2019.v015a012

Recommendations

• Outlaw distributions and locally decodable codes
• Corruption and Recovery-Efficient Locally Decodable Codes
• 3-query locally decodable codes of subexponential length
• Private Locally Decodable Codes
• 3-query locally decodable codes of subexponential length

zbMATH Keywords

influencehypergraphsincidence geometrypseudorandomnessBoolean functionslocally decodable codesGaussian width

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)

Cited In (4)

• High-entropy dual functions over finite fields and locally decodable codes
• Outlaw distributions and locally decodable codes
• On the threshold for Szemerédi's theorem with random differences
• Subspaces of tensors with high analytic rank

This page was built for publication: Outlaw distributions and locally decodable codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204830)