Buchumschlag

Communication with Imperfectly Shared Randomness

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Canonne, Clément L., Guruswami, Venkatesan, Meka, Raghu, Sudan, Madhu
Format:	Preprint
Veröffentlicht:	2014
Schlagworte:	Computational Complexity Information Theory Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Punctured Low-Bias Codes Behave Like Random Linear Codes
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2025)

Algebra in Algorithmic Coding Theory
von: Sudan, Madhu
Veröffentlicht: (2025)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

Explicit Constant-Alphabet Subspace Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2026)

Improved PIR Schemes using Matching Vectors and Derivatives
von: Ghasemi, Fatemeh, et al.
Veröffentlicht: (2024)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
von: Li, Cheuk Ting
Veröffentlicht: (2024)

Explicit optimal-length locally repairable codes of distance 5
von: Beemer, Allison, et al.
Veröffentlicht: (2018)

The Optimal Approximation Factor in Density Estimation
von: Bousquet, Olivier, et al.
Veröffentlicht: (2019)

Bounds for list-decoding and list-recovery of random linear codes
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2020)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

Smoothed Agnostic Learning of Halfspaces over the Hypercube
von: Kou, Yiwen, et al.
Veröffentlicht: (2025)

New constructions of pseudorandom codes
von: Ghentiyala, Surendra, et al.
Veröffentlicht: (2024)

Baby PIH: Parameterized Inapproximability of Min CSP
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Strong Inapproximability for a Promise Rank Problem
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2026)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
von: Bhattiprolu, Vijay, et al.
Veröffentlicht: (2025)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2025)

The Optimization of Random Tree Codes for Limited Computational Resources
von: Bacinoglu, B. Tan
Veröffentlicht: (2025)

The Quantumly Fast and the Classically Forrious
von: Canonne, Clément L., et al.
Veröffentlicht: (2026)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
von: Gamarnik, David, et al.
Veröffentlicht: (2023)

Computational lower bounds for multi-frequency group synchronization
von: Kireeva, Anastasia, et al.
Veröffentlicht: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
von: Kelner, Jonathan, et al.
Veröffentlicht: (2024)

Lines in Every Direction with No ee-Random Points
von: Lutz, Neil, et al.
Veröffentlicht: (2025)

Classification of Non-redundancy of Boolean Predicates of Arity 4
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2025)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
von: Tulsiani, Madhur, et al.
Veröffentlicht: (2024)

Low-Degree Testing Over Grids
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2023)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
von: Doron, Dean, et al.
Veröffentlicht: (2024)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
von: Bennett, Huck, et al.
Veröffentlicht: (2022)

Secret Sharing on Superconcentrator
von: Li, Yuan
Veröffentlicht: (2023)

Scheduling Problems with Constrained Rejections
von: Davies, Sami, et al.
Veröffentlicht: (2025)

Random ensembles of symplectic and unitary states are indistinguishable
von: West, Maxwell, et al.
Veröffentlicht: (2024)

Quantum Advantages in (n,d)->1 Random Access Codes
von: Ambainis, Andris, et al.
Veröffentlicht: (2015)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
von: Błasiok, Jarosław, et al.
Veröffentlicht: (2026)

Symmetric Perceptrons, Number Partitioning and Lattices
von: Vafa, Neekon, et al.
Veröffentlicht: (2025)

Average-Case Reductions for $k$-XOR and Tensor PCA
von: Bresler, Guy, et al.
Veröffentlicht: (2026)

Pseudorandom Permutations from Random Reversible Circuits
von: He, William, et al.
Veröffentlicht: (2024)

Interactive Proofs For Distribution Testing With Conditional Oracles
von: Biswas, Ari, et al.
Veröffentlicht: (2025)