Computer Science/Discrete Mathematics

Locally Decodable Codes (LDCs) are a special type of error correcting codes which are constructed from finite point sets that support many small linear dependencies (e.g. many collinear triples). Despite their importance, there are still huge gaps...

Tensor decomposition is the task of writing an n x n x n input tensor T as \sum_{i = 1}^r a_i \otimes b_i \otimes c_i for the smallest possible r (called the rank of T). This problem is NP-hard in general. Jennrich's algorithm succeeds if a_is, b_is...

We consider the problem of explicitly constructing binary linear codes achieving the optimal rate-distance tradeoff.  In 2017, Ta-Shma gave an almost-optimal construction in the low-rate regime, i.e., he gave a construction of binary linear codes...