Explicit, almost optimal, epsilon-balanced codes

DOI10.1145/3055399.3055408MaRDI QIDQ4977975zbMATH OpenOpenAlexWikidataFDO

Authors Amnon Ta-Shma

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3055399.3055408

zbMATH Keywords

epsilon-biaswide replacement productzig-zag product

Mathematics Subject Classification ID

Random walks on graphs (05C81) Linear codes (general theory) (94B05)

Recommendations

• Efficient m-ary balanced codes
• On error-correcting balanced codes
• scientific article; zbMATH DE number 3463503
• Error-Correcting Balanced Knuth Codes
• Efficient balanced codes
• On balanced codes
• Design of efficient balanced codes
• \(e\)-perfect codes
• On efficient balanced codes over the mth roots of unity
• On optimal binary codes with unbalanced coordinates

Cited in

(37)

• On the ring-LWE and polynomial-LWE problems
• Essential components in vector spaces over finite fields
• Quasi-random multilinear polynomials
• Simple and efficient batch verification techniques for verifiable delay functions
• The remote point problem, small bias spaces, and expanding generator sets
• Expanding Generating Sets for Solvable Permutation Groups
• Constructing small-bias sets from algebraic-geometric codes
• scientific article; zbMATH DE number 3463503 (Why is no real title available?)
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Constructing small-bias sets from algebraic-geometric codes
• Optimal -biased sets with just a little randomness
• List-Decoding with Double Samplers
• Paradigms for Unconditional Pseudorandom Generators
• Random walks on rotating expanders
• A high dimensional Goldreich-Levin theorem
• Nearly optimal pseudorandomness from hardness
• Strong blocking sets and minimal codes from expander graphs
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Non-malleable codes with optimal rate for poly-size circuits
• Traceable secret sharing: strong security and efficient constructions
• Pseudorandom error-correcting codes
• Deterministic sparse Fourier transform with an _ guarantee
• Parameterized approximation for robust clustering in discrete geometric spaces
• Pseudorandom linear codes are list-decodable to capacity
• Almost-Ramanujan expanders from arbitrary expanders via operator amplification
• Sparse high dimensional expanders via local lifts
• When do low-rate concatenated codes approach the Gilbert-Varshamov bound?
• Optimal pseudorandom generators for low-degree polynomials over moderately large fields
• The expander hitting property when the sets are arbitrarily unbalanced
• Range avoidance for low-depth circuits and connections to pseudorandomness
• Adaptive exact learning of decision trees from membership queries
• Pseudobinomiality of the sticky random walk
• A simplified reduction for error correcting matrix multiplication algorithms
• Fooling near-maximal decision trees
• Pseudorandomness of expander walks via Fourier analysis on groups
• An optimal error-correcting reduction for matrix multiplication

This page was built for publication: Explicit, almost optimal, epsilon-balanced codes

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