Computer Science/Discrete Mathematics

Date:
Apr
27
2026

Computer Science/Discrete Mathematics Seminar I

Locally Decodable Codes and Representations of Finite Groups
Zeev Dvir
11:00am|Simonyi Hall 101 and Remote Access

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...

Apr
28
2026

Computer Science/Discrete Mathematics Seminar II

Algorithms for Overcomplete Tensor Decomposition
Pravesh Kothari
10:30am|Simonyi 101 and Remote Access

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...

Apr
30
2026

Computer Science/Discrete Mathematics Seminar I

How to Amplify the Distance of a Code Optimally
Sidhanth Mohanty
11:00am|Simonyi Classroom (S-114)

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...