
The zerorate threshold for adversarial bitdeletions is less than 1/2
We prove that there exists an absolute constant δ>0 such any binary code...
read it

Conditional Dichotomy of Boolean Ordered Promise CSPs
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of...
read it

Improved Maximally Recoverable LRCs using Skew Polynomials
An (n,r,h,a,q)Local Reconstruction Code is a linear code over 𝔽_q of le...
read it

ACDC: Amplification Curve Diagnostics for Covid19 Group Testing
The first part of the paper presents a review of the goldstandard testi...
read it

Strongly refuting all semirandom Boolean CSPs
We give an efficient algorithm to strongly refute semirandom instances ...
read it

Linear Shannon Capacity of Cayley Graphs
The Shannon capacity of a graph is a fundamental quantity in zeroerror ...
read it

Sharp threshold rates for random codes
Suppose that 𝒫 is a property that may be satisfied by a random code C ⊂Σ...
read it

Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture
A famous conjecture of Tuza states that the minimum number of edges need...
read it

Explicit twodeletion codes with redundancy matching the existential bound
We give an explicit construction of lengthn binary codes capable of cor...
read it

Efficient Linear and Affine Codes for Correcting Insertions/Deletions
This paper studies linear and affine errorcorrecting codes for correcti...
read it

Bounds for listdecoding and listrecovery of random linear codes
A family of errorcorrecting codes is listdecodable from error fraction...
read it

A localitybased approach for coded computation
Modern distributed computation infrastructures are often plagued by unav...
read it

Arıkan meets Shannon: Polar codes with nearoptimal convergence to channel capacity
Let W be a binaryinput memoryless symmetric (BMS) channel with Shannon ...
read it

Optimally Resilient Codes for ListDecoding from Insertions and Deletions
We give a complete answer to the following basic question: "What is the ...
read it

Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
In the field of constraint satisfaction problems (CSP), promise CSPs are...
read it

Nearoptimal Repair of ReedSolomon Codes with Low Subpacketization
Minimum storage regenerating (MSR) codes are MDS codes which allow for r...
read it

Parameterized Inapproximability of Exact Cover and Nearest Codeword
The kExactCover problem is a parameterized version of the ExactCover pr...
read it

Bridging between 0/1 and Linear Programming via Random Walks
Under the Strong Exponential Time Hypothesis, an integer linear program ...
read it

NonMalleable Secret Sharing against Affine Tampering
Nonmalleable secret sharing was recently studied by Goyal and Kumar in ...
read it

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
We study the complexity of Boolean constraint satisfaction problems (CSP...
read it

An Exponential Lower Bound on the SubPacketization of MSR Codes
An (n,k,ℓ)vector MDS code is a Flinear subspace of (F^ℓ)^n (for some f...
read it

Streaming Hardness of Unique Games
We study the problem of approximating the value of a Unique Game instanc...
read it

Polar Codes with exponentially small error at finite block length
We show that the entire class of polar codes (up to a natural necessary ...
read it

Explicit optimallength locally repairable codes of distance 5
Locally repairable codes (LRCs) have received significant recent attenti...
read it

Algorithmic Polarization for Hidden Markov Models
Using a mild variant of polar codes we design linear compression schemes...
read it

Constructions of maximally recoverable local reconstruction codes via function fields
Local Reconstruction Codes (LRCs) allow for recovery from a small number...
read it

Secret Sharing with Binary Shares
Secret sharing is a fundamental cryptographic primitive. One of the main...
read it

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
Promise CSPs are a relaxation of constraint satisfaction problems where ...
read it

εMSR Codes: Contacting Fewer Code Blocks for Exact Repair
ϵMinimum Storage Regenerating (ϵMSR) codes form a special class of Max...
read it

How long can optimal locally repairable codes be?
A locally repairable code (LRC) with locality r allows for the recovery ...
read it

Beating FredmanKomlós for perfect khashing
We say a subset C ⊆{1,2,...,k}^n is a khash code (also called kseparat...
read it

Approximating Operator Norms via Generalized Krivine Rounding
We consider the (ℓ_p,ℓ_r)Grothendieck problem, which seeks to maximize ...
read it

Inapproximability of Matrix p→ q Norms
We study the problem of computing the p→ q norm of a matrix A ∈ R^m × n,...
read it

General Strong Polarization
Arı kan's exciting discovery of polar codes has provided an altogether n...
read it

On the ListDecodability of Random Linear RankMetric Codes
The listdecodability of random linear rankmetric codes is shown to mat...
read it

On Maximally Recoverable Local Reconstruction Codes
In recent years the explosion in the volumes of data being stored online...
read it

MDS Code Constructions with Small Subpacketization and Nearoptimal Repair Bandwidth
This paper addresses the problem of constructing MDS codes that enable e...
read it

Optimal rate list decoding over bounded alphabets using algebraicgeometric codes
We give new constructions of two classes of algebraic code families whic...
read it

Agnostic Learning of Monomials by Halfspaces is Hard
We prove the following strong hardness result for learning: Given a dist...
read it
Venkatesan Guruswami
is this you? claim profile