research
∙
08/29/2023
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
A code C {0,1}^k →{0,1}^n is a q-locally decodable code (q-LDC) if one c...
share
research
∙
08/25/2023
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
A simple, recently observed generalization of the classical Singleton bo...
research
∙
07/06/2023
Improved rate-distance trade-offs for quantum codes with restricted connectivity
For quantum error-correcting codes to be realizable, it is important tha...
research
∙
05/04/2023
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble
We present an explicit construction of a sequence of rate 1/2 Wozencraft...
research
∙
04/19/2023
Randomly punctured Reed–Solomon codes achieve list-decoding capacity over linear-sized fields
Reed–Solomon codes are a classic family of error-correcting codes consis...
research
∙
12/12/2022
Binary Error-Correcting Codes with Minimal Noiseless Feedback
In the setting of error-correcting codes with feedback, Alice wishes to ...
research
∙
11/15/2022
SDPs and Robust Satisfiability of Promise CSP
For a constraint satisfaction problem (CSP), a robust satisfaction algor...
research
∙
11/15/2022
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓ_p Norms
We prove that the Minimum Distance Problem (MDP) on linear codes over an...
research
∙
07/10/2022
Accelerating Polarization via Alphabet Extension
Polarization is an unprecedented coding technique in that it not only ac...
research
∙
05/13/2022
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number
Let ℋ(k,n,p) be the distribution on k-uniform hypergraphs where every su...
research
∙
05/13/2022
Sparsity and ℓ_p-Restricted Isometry
A matrix A is said to have the ℓ_p-Restricted Isometry Property (ℓ_p-RIP...
research
∙
12/18/2021
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
We consider the problem of designing low-redundancy codes in settings wh...
research
∙
09/24/2021
Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity
We prove the existence of Reed-Solomon codes of any desired rate R ∈ (0,...
research
∙
09/09/2021
Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
We present an algorithm for strongly refuting smoothed instances of all ...
research
∙
08/31/2021
ℓ_p-Spread Properties of Sparse Matrices
Random subspaces X of ℝ^n of dimension proportional to n are, with high ...
research
∙
08/28/2021
Visible Rank and Codes with Locality
We propose a framework to study the effect of local recovery requirement...
research
∙
08/12/2021
CNF Satisfiability in a Subspace and Related Problems
We introduce the problem of finding a satisfying assignment to a CNF for...
research
∙
07/16/2021
Linear Programming Bounds for Almost-Balanced Binary Codes
We revisit the linear programming bounds for the size vs. distance trade...
research
∙
06/09/2021
The zero-rate threshold for adversarial bit-deletions is less than 1/2
We prove that there exists an absolute constant δ>0 such any binary code...
research
∙
02/23/2021
Conditional Dichotomy of Boolean Ordered Promise CSPs
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of...
research
∙
12/14/2020
Improved Maximally Recoverable LRCs using Skew Polynomials
An (n,r,h,a,q)-Local Reconstruction Code is a linear code over 𝔽_q of le...
research
∙
11/10/2020
AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing
The first part of the paper presents a review of the gold-standard testi...
research
∙
09/17/2020
Strongly refuting all semi-random Boolean CSPs
We give an efficient algorithm to strongly refute semi-random instances ...
research
∙
09/11/2020
Linear Shannon Capacity of Cayley Graphs
The Shannon capacity of a graph is a fundamental quantity in zero-error ...
research
∙
09/09/2020
Sharp threshold rates for random codes
Suppose that 𝒫 is a property that may be satisfied by a random code C ⊂Σ...
research
∙
08/17/2020
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture
A famous conjecture of Tuza states that the minimum number of edges need...
research
∙
07/21/2020
Explicit two-deletion codes with redundancy matching the existential bound
We give an explicit construction of length-n binary codes capable of cor...
research
∙
07/17/2020
Efficient Linear and Affine Codes for Correcting Insertions/Deletions
This paper studies linear and affine error-correcting codes for correcti...
research
∙
04/28/2020
Bounds for list-decoding and list-recovery of random linear codes
A family of error-correcting codes is list-decodable from error fraction...
research
∙
02/06/2020
A locality-based approach for coded computation
Modern distributed computation infrastructures are often plagued by unav...
research
∙
11/10/2019
Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity
Let W be a binary-input memoryless symmetric (BMS) channel with Shannon ...
research
∙
09/24/2019
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
We give a complete answer to the following basic question: "What is the ...
research
∙
07/09/2019
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
In the field of constraint satisfaction problems (CSP), promise CSPs are...
research
∙
07/09/2019
Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization
Minimum storage regenerating (MSR) codes are MDS codes which allow for r...
research
∙
05/16/2019
Parameterized Inapproximability of Exact Cover and Nearest Codeword
The k-ExactCover problem is a parameterized version of the ExactCover pr...
research
∙
04/09/2019
Bridging between 0/1 and Linear Programming via Random Walks
Under the Strong Exponential Time Hypothesis, an integer linear program ...
research
∙
02/17/2019
Non-Malleable Secret Sharing against Affine Tampering
Non-malleable secret sharing was recently studied by Goyal and Kumar in ...
research
∙
02/13/2019
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
We study the complexity of Boolean constraint satisfaction problems (CSP...
research
∙
01/16/2019
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
An (n,k,ℓ)-vector MDS code is a F-linear subspace of (F^ℓ)^n (for some f...
research
∙
11/12/2018
Streaming Hardness of Unique Games
We study the problem of approximating the value of a Unique Game instanc...
research
∙
10/09/2018
Polar Codes with exponentially small error at finite block length
We show that the entire class of polar codes (up to a natural necessary ...
research
∙
10/09/2018
Explicit optimal-length locally repairable codes of distance 5
Locally repairable codes (LRCs) have received significant recent attenti...
research
∙
10/03/2018
Algorithmic Polarization for Hidden Markov Models
Using a mild variant of polar codes we design linear compression schemes...
research
∙
08/14/2018
Constructions of maximally recoverable local reconstruction codes via function fields
Local Reconstruction Codes (LRCs) allow for recovery from a small number...
research
∙
08/09/2018
Secret Sharing with Binary Shares
Secret sharing is a fundamental cryptographic primitive. One of the main...
research
∙
07/13/2018
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
Promise CSPs are a relaxation of constraint satisfaction problems where ...
research
∙
07/03/2018
ε-MSR Codes: Contacting Fewer Code Blocks for Exact Repair
ϵ-Minimum Storage Regenerating (ϵ-MSR) codes form a special class of Max...
research
∙
07/03/2018
How long can optimal locally repairable codes be?
A locally repairable code (LRC) with locality r allows for the recovery ...
research
∙
05/10/2018
Beating Fredman-Komlós for perfect k-hashing
We say a subset C ⊆{1,2,...,k}^n is a k-hash code (also called k-separat...
research
∙
04/10/2018