Outlaw distributions and locally decodable codes

DOI10.4086/TOC.2019.V015A012MaRDI QIDQ5204830zbMATH OpenOpenAlexFDO

Authors Jop Briët, Zeev Dvir, Sivakanth Gopi

Publication date 5 December 2019

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

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)