46 citations · 96 across the 8 of their papers we have counts for
10 papers
Sketching Approximability of (Weak) Monarchy Predicates
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi +2
We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals.…
Synchronization Strings and Codes for Insertions and Deletions -- a Survey
Bernhard Haeupler, Amirbehshad Shahrasbi
Already in the 1960s, Levenshtein and others studied error-correcting codes that protect against synchronization errors, such as symbol insertions and deletions. However, despite s…
Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes
Bernhard Haeupler, Amirbehshad Shahrasbi
This paper presents general bounds on the highest achievable rate for list-decodable insertion-deletion codes. In particular, we give novel outer and inner bounds for the highest a…
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
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 -ary list-decodable codes with non-vanishing inf…
Near-Linear Time Insertion-Deletion Codes and (1+)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
We introduce fast-decodable indexing schemes for edit distance which can be used to speed up edit distance computations to near-linear time if one of the strings is indexed by an i…
Synchronization Strings: List Decoding for Insertions and Deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
We study codes that are list-decodable under insertions and deletions. Specifically, we consider the setting where a codeword over some finite alphabet of size may suffer from…
Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler, Amirbehshad Shahrasbi
This paper gives new results for synchronization strings, a powerful combinatorial object that allows to efficiently deal with insertions and deletions in various communication set…
Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, Ellen Vitercik
We present many new results related to reliable (interactive) communication over insertion-deletion channels. Synchronization errors, such as insertions and deletions, strictly gen…
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Bernhard Haeupler, Amirbehshad Shahrasbi
We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more gen…
Critical Graphs in Index Coding
Mehrdad Tahmasbi, Amirbehshad Shahrasbi, Amin Gohari
In this paper we define critical graphs as minimal graphs that support a given set of rates for the index coding problem, and study them for both the one-shot and asymptotic setups…