Tree codes and a conjecture on exponential sums

DOI10.1145/2554797.2554813MaRDI QIDQ2988874zbMATH OpenOpenAlexFDO

Authors Cristopher Moore, Leonard J. Schulman

Publication date 19 May 2017

Published in Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.6007

zbMATH Keywords

exponential sumerror-correcting codesinteractive communication

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Combinatorial codes (94B25) Exponential sums (11T23)

Abstract: We propose a new conjecture on some exponential sums. These particular sums have not apparently been considered in the literature. Subject to the conjecture we obtain the first effective construction of asymptotically good tree codes. The available numerical evidence is consistent with the conjecture and is sufficient to certify codes for significant-length communications.

Recommendations

• Linear tree codes and the problem of explicit constructions
• Publication:4886128
• On decoding Cohen-Haeupler-Schulman tree codes
• Explicit binary tree codes with polylogarithmic size alphabet
• Towards deterministic tree code constructions

Cites work

• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Fully homomorphic encryption using ideal lattices
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(6)

• scientific article; zbMATH DE number 775615 (Why is no real title available?)
• Palette-alternating tree codes
• scientific article; zbMATH DE number 7768399 (Why is no real title available?)
• Linear tree codes and the problem of explicit constructions
• List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
• Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture

This page was built for publication: Tree codes and a conjecture on exponential sums

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