Direct sum fails for zero error average communication

DOI10.1145/2554797.2554844MaRDI QIDQ2988905zbMATH OpenOpenAlexWikidataFDO

Authors Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

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://doi.org/10.1145/2554797.2554844

zbMATH Keywords

information theorycommunication complexityamortized complexitydirect suminformation complexitypromise problemsaverage-case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Direct sum fails for zero-error average communication
• Push-Sum With Transmission Failures
• Worst Case Nonzero-Error Interactive Communication
• scientific article; zbMATH DE number 1421021
• scientific article; zbMATH DE number 2038719
• On multiparty communication with large versus unbounded error
• Zero-Error Relaying for Primitive Relay Channels
• Toward coding for maximum errors in interactive communication
• Multiplexing Zero-Error and Rare-Error Communications Over a Noisy Channel
• Estimation d'erreurs dans un problème de transmission

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

(1)

• Direct sum fails for zero-error average communication

This page was built for publication: Direct sum fails for zero error average communication

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