Events

Qualifying Exam Computational Aspects and Implications of Error-correcting Codes
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Monday, October 27, 2025, 12:45pm - 02:30pm

Speaker: Mursalin Habib

Bio

Location : CoRE 305

Committee: 

Assistant Professor Karthik Srikanta

Assistant Professor Roie Levin

Assistant Professor Akash Kumar Sengupta

Associate Professor Konstantinos Michmizos

Event Type: Qualifying Exam

Abstract: Error-correcting codes are large collections of strings that are pairwise far apart. Codes, by design, enjoy certain robustness guarantees, making them suitable for applications in communication, pseudorandomness, hardness of approximation, and beyond. At the same time, they give rise to a rich mathematical theory at the intersection of combinatorics, algebra, and geometry.In this talk, I will discuss various computational aspects and implications of error-correcting codes, highlighting three recent results.The first part of the talk will be devoted to permutation codes under the Ulam distance, a metric that has recently garnered attention due to applications in flash memory storage. The main highlight will be a new explicit construction of positive constant-rate codes with relative distance arbitrarily close to 1, overcoming the 1/3-distance barrier of prior constructions.The second part of the talk will concern isometric embeddings of the Hamming metric into the edit metric. Here, the main challenge is to maximize the rate, i.e., the ratio between the lengths of the input and output strings, of such embeddings. The focus will be on the first-ever constant-rate isometric embedding, along with consequences for lower bounds for problems in the edit metric.The final part of the talk will address Folded Reed-Solomon (FRS) codes — a well-studied class of codes known to achieve list-decoding capacity. The main focus will be the first fully polynomial-time algorithm running in poly(1/ε)·n·polylog(n) time for list decoding rate-R FRS codes up to radius 1-R-ε. In addition, we will see a deterministic decoder with running time f(ε)·n·polylog(n) that breaks the longstanding n^{1/ε} bound for deterministic decoding.

Organization: 

Contact  Assistant Professor Karthik Srikanta

Zoom Link: https://rutgers.zoom.us/j/97766325975?pwd=zAHam7nSBaVoTUNGjQHa5q4VCYWlSe.1