[Theory] TODAY: 7/15 Thesis Defense: Shashank Srivastava, TTIC
Mary Marre via Theory
theory at mailman.cs.uchicago.edu
Mon Jul 15 11:00:00 CDT 2024
*When*: Monday, July 15th from *1**- 3 pm CT*
*Where*: Talk will be given *live, in-person* at
TTIC, 6045 S. Kenwood Avenue
5th Floor, *Room 529*
*Virtually*: via *Zoom*
<https://uchicago.zoom.us/j/93804353690?pwd=xYnLgPPNFLrlPCi7DNLNB5QzqLmMQO.1>
*Who*: Shashank Srivastava, TTIC
------------------------------
*Title: * Continuous Optimization for Decoding Errors
*Abstract: *Error-correcting codes are one of the most fundamental objects
in pseudorandomness, with applications in communication, complexity theory,
and beyond. Codes are useful because of their ability to support decoding,
which is the task of recovering a codeword from its noisy copy. List
decoding is a relaxation where the decoder is allowed to output a list of
codewords, and has seen tremendous progress over the last 25 years. In
this thesis, we prove new algorithmic and combinatorial results about list
decoding.
We describe a list decoding framework that reduces the task of efficient
decoding to proving distance in certain restricted proof systems. We then
instantiate this framework for Tanner codes of Sipser and Spielman [IEEE
Trans. Inf. Theory 1996] and Alon-Edmonds-Luby (AEL) distance amplification
[FOCS 1995] of unique decodable base codes to get the first polynomial time
list decoding algorithms for both of these codes. We also discuss
extensions to the quantum version of AEL distance amplification, yielding
polynomial-time list decodable quantum LDPC codes.
We next give an alternate viewpoint of the list decoding framework based on
abstract regularity lemmas instead of convex hierarchies. We show how to
efficiently implement the regularity lemma for the case of Ta-Shma’s
explicit codes near the Gilbert-Varshamov bound [STOC 2017]. This leads to
a near-linear time algorithm for unique decoding for Ta-Shma’s codes.
We also give new combinatorial results that improve known list sizes beyond
the Johnson bound. Firstly, we adapt the AEL amplification to construct a
new family of explicit codes that can be combinatorially list decoded to
the optimal error correction radius. This is the first example of such a
code that does not use significant algebraic ingredients. Secondly, we
present list size improvements for Folded Reed-Solomon codes, improving the
state of the art list size among explicit list decoding capacity achieving
codes.
*Thesis Committee: *Madhur Tulsiani <madhurt at ttic.edu> (Thesis
Advisor), Pravesh
K. Kothari (Princeton University), Yury Makarychev
Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL 60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*
On Sun, Jul 14, 2024 at 12:19 PM Mary Marre <mmarre at ttic.edu> wrote:
> *When*: Monday, July 15th from *1**- 3 pm CT*
>
> *Where*: Talk will be given *live, in-person* at
> TTIC, 6045 S. Kenwood Avenue
> 5th Floor, *Room 529*
>
> *Virtually*: via *Zoom*
> <https://uchicago.zoom.us/j/93804353690?pwd=xYnLgPPNFLrlPCi7DNLNB5QzqLmMQO.1>
>
>
> *Who*: Shashank Srivastava, TTIC
>
> ------------------------------
> *Title: * Continuous Optimization for Decoding Errors
>
> *Abstract: *Error-correcting codes are one of the most fundamental
> objects in pseudorandomness, with applications in communication, complexity
> theory, and beyond. Codes are useful because of their ability to support
> decoding, which is the task of recovering a codeword from its noisy copy.
> List decoding is a relaxation where the decoder is allowed to output a list
> of codewords, and has seen tremendous progress over the last 25 years. In
> this thesis, we prove new algorithmic and combinatorial results about list
> decoding.
>
> We describe a list decoding framework that reduces the task of efficient
> decoding to proving distance in certain restricted proof systems. We then
> instantiate this framework for Tanner codes of Sipser and Spielman [IEEE
> Trans. Inf. Theory 1996] and Alon-Edmonds-Luby (AEL) distance amplification
> [FOCS 1995] of unique decodable base codes to get the first polynomial time
> list decoding algorithms for both of these codes. We also discuss
> extensions to the quantum version of AEL distance amplification, yielding
> polynomial-time list decodable quantum LDPC codes.
>
> We next give an alternate viewpoint of the list decoding framework based
> on abstract regularity lemmas instead of convex hierarchies. We show how to
> efficiently implement the regularity lemma for the case of Ta-Shma’s
> explicit codes near the Gilbert-Varshamov bound [STOC 2017]. This leads to
> a near-linear time algorithm for unique decoding for Ta-Shma’s codes.
>
> We also give new combinatorial results that improve known list sizes
> beyond the Johnson bound. Firstly, we adapt the AEL amplification to
> construct a new family of explicit codes that can be combinatorially list
> decoded to the optimal error correction radius. This is the first example
> of such a code that does not use significant algebraic ingredients.
> Secondly, we present list size improvements for Folded Reed-Solomon codes,
> improving the state of the art list size among explicit list decoding
> capacity achieving codes.
>
> *Thesis Committee: *Madhur Tulsiani <madhurt at ttic.edu> (Thesis Advisor), Pravesh
> K. Kothari (Princeton University), Yury Makarychev
>
>
>
>
> Mary C. Marre
> Faculty Administrative Support
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue, Rm 517*
> *Chicago, IL 60637*
> *773-834-1757*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
>
> On Tue, Jul 9, 2024 at 2:44 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *When*: Monday, July 15th from *1**- 3 pm CT*
>>
>> *Where*: Talk will be given *live, in-person* at
>> TTIC, 6045 S. Kenwood Avenue
>> 5th Floor, *Room 529*
>>
>> *Virtually*: via *Zoom*
>> <https://uchicago.zoom.us/j/93804353690?pwd=xYnLgPPNFLrlPCi7DNLNB5QzqLmMQO.1>
>>
>>
>> *Who*: Shashank Srivastava, TTIC
>>
>> ------------------------------
>> *Title: * Continuous Optimization for Decoding Errors
>>
>> *Abstract: *Error-correcting codes are one of the most fundamental
>> objects in pseudorandomness, with applications in communication, complexity
>> theory, and beyond. Codes are useful because of their ability to support
>> decoding, which is the task of recovering a codeword from its noisy copy.
>> List decoding is a relaxation where the decoder is allowed to output a list
>> of codewords, and has seen tremendous progress over the last 25 years. In
>> this thesis, we prove new algorithmic and combinatorial results about list
>> decoding.
>>
>> We describe a list decoding framework that reduces the task of efficient
>> decoding to proving distance in certain restricted proof systems. We then
>> instantiate this framework for Tanner codes of Sipser and Spielman [IEEE
>> Trans. Inf. Theory 1996] and Alon-Edmonds-Luby (AEL) distance amplification
>> [FOCS 1995] of unique decodable base codes to get the first polynomial time
>> list decoding algorithms for both of these codes. We also discuss
>> extensions to the quantum version of AEL distance amplification, yielding
>> polynomial-time list decodable quantum LDPC codes.
>>
>> We next give an alternate viewpoint of the list decoding framework based
>> on abstract regularity lemmas instead of convex hierarchies. We show how to
>> efficiently implement the regularity lemma for the case of Ta-Shma’s
>> explicit codes near the Gilbert-Varshamov bound [STOC 2017]. This leads to
>> a near-linear time algorithm for unique decoding for Ta-Shma’s codes.
>>
>> We also give new combinatorial results that improve known list sizes
>> beyond the Johnson bound. Firstly, we adapt the AEL amplification to
>> construct a new family of explicit codes that can be combinatorially list
>> decoded to the optimal error correction radius. This is the first example
>> of such a code that does not use significant algebraic ingredients.
>> Secondly, we present list size improvements for Folded Reed-Solomon codes,
>> improving the state of the art list size among explicit list decoding
>> capacity achieving codes.
>>
>> *Thesis Committee: *Madhur Tulsiani <madhurt at ttic.edu> (Thesis Advisor), Pravesh
>> K. Kothari (Princeton University), Yury Makarychev
>>
>>
>>
>>
>> Mary C. Marre
>> Faculty Administrative Support
>> *Toyota Technological Institute*
>> *6045 S. Kenwood Avenue, Rm 517*
>> *Chicago, IL 60637*
>> *773-834-1757*
>> *mmarre at ttic.edu <mmarre at ttic.edu>*
>>
>>
>> On Thu, Jul 4, 2024 at 1:08 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *When*: Monday, July 15th from *1**- 3 pm CT*
>>>
>>> *Where*: Talk will be given *live, in-person* at
>>> TTIC, 6045 S. Kenwood Avenue
>>> 5th Floor, *Room 529*
>>>
>>> *Virtually*: via *Zoom*
>>> <https://uchicago.zoom.us/j/93804353690?pwd=xYnLgPPNFLrlPCi7DNLNB5QzqLmMQO.1>
>>>
>>>
>>> *Who*: Shashank Srivastava, TTIC
>>>
>>> ------------------------------
>>> *Title: * Continuous Optimization for Decoding Errors
>>>
>>> *Abstract: *Error-correcting codes are one of the most fundamental
>>> objects in pseudorandomness, with applications in communication, complexity
>>> theory, and beyond. Codes are useful because of their ability to support
>>> decoding, which is the task of recovering a codeword from its noisy copy.
>>> List decoding is a relaxation where the decoder is allowed to output a list
>>> of codewords, and has seen tremendous progress over the last 25 years. In
>>> this thesis, we prove new algorithmic and combinatorial results about
>>> list decoding.
>>>
>>> We describe a list decoding framework that reduces the task of efficient
>>> decoding to proving distance in certain restricted proof systems. We then
>>> instantiate this framework for Tanner codes of Sipser and Spielman [IEEE
>>> Trans. Inf. Theory 1996] and Alon-Edmonds-Luby (AEL) distance amplification
>>> [FOCS 1995] of unique decodable base codes to get the first polynomial time
>>> list decoding algorithms for both of these codes. We also discuss
>>> extensions to the quantum version of AEL distance amplification, yielding
>>> polynomial-time list decodable quantum LDPC codes.
>>>
>>> We next give an alternate viewpoint of the list decoding framework based
>>> on abstract regularity lemmas instead of convex hierarchies. We show how to
>>> efficiently implement the regularity lemma for the case of Ta-Shma’s
>>> explicit codes near the Gilbert-Varshamov bound [STOC 2017]. This leads to
>>> a near-linear time algorithm for unique decoding for Ta-Shma’s codes.
>>>
>>> We also give new combinatorial results that improve known list sizes
>>> beyond the Johnson bound. Firstly, we adapt the AEL amplification to
>>> construct a new family of explicit codes that can be combinatorially list
>>> decoded to the optimal error correction radius. This is the first example
>>> of such a code that does not use significant algebraic ingredients.
>>> Secondly, we present list size improvements for Folded Reed-Solomon codes,
>>> improving the state of the art list size among explicit list decoding
>>> capacity achieving codes.
>>>
>>> *Thesis Committee: *Madhur Tulsiani <madhurt at ttic.edu> (Thesis Advisor), Pravesh
>>> K. Kothari (Princeton University), Yury Makarychev
>>>
>>>
>>>
>>> Mary C. Marre
>>> Faculty Administrative Support
>>> *Toyota Technological Institute*
>>> *6045 S. Kenwood Avenue, Rm 517*
>>> *Chicago, IL 60637*
>>> *773-834-1757*
>>> *mmarre at ttic.edu <mmarre at ttic.edu>*
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240715/5b353a9f/attachment-0001.html>
More information about the Theory
mailing list