All reports by Author Amirbehshad Shahrasbi:

__
TR22-068
| 5th May 2022
__

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy#### Sketching Approximability of (Weak) Monarchy Predicates

Revisions: 1

__
TR19-153
| 6th November 2019
__

Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi#### Optimally Resilient Codes for List-Decoding from Insertions and Deletions

Revisions: 1

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first ... more >>>

Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi

We give a complete answer to the following basic question: ``What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''

This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results ... more >>>