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

Boolean functionsGaussian widthhypergraphsincidence geometryinfluencelocally decodable codespseudorandomness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) 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

(6)

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

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)