I am a third-year PhD student at Carnegie Mellon University's Computer Science Department and a member of Algorithms and Complexity group particiapating in Algorithms, Combinatorics, and Optimization (ACO) program. I am very fortunate to be advised by Bernhard Haeupler.

I am broadly interested in algorithmic and combinatorial aspects of theoretical computer science. I have been recently working on communication problems concerning synchronization errors.

## Publications

### Conference Papers

Synchronization strings: Codes for Insertions and Deletions Approaching the Singleton Bound
with Bernhard Haeupler
Proceedings of the Annual Symposium on Theory of Computing (STOC), 2017.
[ arXiv ] [ AbstractHide Abstract ]

We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to deal with than commonly considered half-errors, i.e., symbol corruptions and erasures. For every $$\epsilon >0$$, synchronization strings allow to index a sequence with an $$\epsilon^{-O(1)}$$ size alphabet such that one can efficiently transform $$k$$ synchronization errors into $$(1+\epsilon)k$$ half-errors. This powerful new technique has many applications. In this paper, we focus on designing insdel codes, i.e., error correcting block codes (ECCs) for insertion deletion channels.
While ECCs for both half-errors and synchronization errors have been intensely studied, the later has largely resisted progress. Indeed, it took until 1999 for the first insdel codes with constant rate, constant distance, and constant alphabet size to be constructed by Schulman and Zuckerman. Insdel codes for asymptotically large or small noise rates were given in 2016 by Guruswami et al. but these codes are still polynomially far from the optimal rate-distance tradeoff. This makes the understanding of insdel codes up to this work equivalent to what was known for regular ECCs after Forney introduced concatenated codes in his doctoral thesis 50 years ago.
A direct application of our synchronization strings based indexing method gives a simple black-box construction which transforms any ECC into an equally efficient insdel code with a slightly larger alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs over large constant alphabets into the realm of insdel codes. Most notably, we obtain efficient insdel codes which get arbitrarily close to the optimal rate-distance tradeoff given by the Singleton bound for the complete noise spectrum.

Critical Graphs in Index Coding
with Mehrdad Tahmasbi and Amin Gohari
Proceedings of IEEE International Symposium on Information Theory (ISIT), 2014.
[ arXiv ] [ AbstractHide Abstract ]

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. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. Next, we identify a few graph structures that are critical. We also generalize some of our results to the groupcast problem. In addition, we show that the capacity region of the index coding is additive for union of disjoint graphs.

### Journal Papers

Critical Graphs in Index Coding
with Mehrdad Tahmasbi and Amin Gohari
IEEE Journal on Selected Areas in Communications (JSAC), 2015.
[ arXiv ] [ AbstractHide Abstract ]

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. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. Next, we identify a few graph structures that are critical. We also generalize some of our results to the groupcast problem. In addition, we show that the capacity region of the index coding is additive for union of disjoint graphs.

### Manuscripts

Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
with Bernhard Haeupler and Ellen Vitercik
In submission
[ arXiv ] [ AbstractHide Abstract ]

We present many new results related to reliable (interactive) communication over insertion-deletion channels. Synchronization errors, such as insertions and deletions, strictly generalize the usual symbol corruption errors and are much harder to protect against.
We show how to hide the complications of synchronization errors in many applications by introducing very general channel simulations which efficiently transform an insertion-deletion channel into a regular symbol corruption channel with an error rate larger by a constant factor and a slightly smaller alphabet. We generalize synchronization string based methods which were recently introduced as a tool to design essentially optimal error correcting codes for insertion-deletion channels. Our channel simulations depend on the fact that, at the cost of increasing the error rate by a constant factor, synchronization strings can be decoded in a streaming manner that preserves linearity of time. We also provide a lower bound showing that this constant factor cannot be improved to $$1+\epsilon$$, in contrast to what is achievable for error correcting codes. Our channel simulations drastically generalize the applicability of synchronization strings.
We provide new interactive coding schemes which simulate any interactive two-party protocol over an insertion-deletion channel. Our results improve over the interactive coding scheme of Braverman et al. which achieves a small constant rate and requires exponential time computations. We provide the first computationally efficient interactive coding schemes for synchronization errors, the first coding scheme with a rate approaching one for small noise rates, and also improve over the maximal tolerable error rate. We also show tight connections between synchronization strings and edit-distance tree codes which allow us to transfer results from tree codes directly to edit-distance tree codes.

Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
with Bernhard Haeupler
In submission
[ arXiv ] [ AbstractHide Abstract ]

This paper gives new results for synchronization strings, a powerful combinatorial object that allows to efficiently deal with insertions and deletions in various communication problems:

• We give a deterministic, linear time synchronization string construction, improving over an $$O(n^5)$$ time randomized construction. Independently of this work, a deterministic $$O(n \log^2 \log n)$$ time construction proposed by Cheng, Li, and Wu.
• We give a deterministic construction of an infinite synchronization string which outputs the first $$n$$ symbols in $$O(n)$$ time. Previously it was not known whether such a string was computable.
• Both synchronization string constructions are highly explicit, i.e., the $$i^{th}$$ symbol can be deterministically computed in $$O(\log i)$$ time.
• This paper also introduces a generalized notion we call long-distance synchronization strings. Such strings allow for local and very fast decoding. In particular, only $$O(\log^3 n)$$ time and access to logarithmically many symbols is required to decode any index.
The paper also provides several applications for these improved synchronization strings:
• For any $$\delta < 1$$ and $$\epsilon > 0$$ we provide an insdel error correcting block code with rate $$1 - \delta - \epsilon$$ which can correct any $$O(\delta)$$ fraction of insertion and deletion errors in $$O(n \log^3 n)$$ time. This near linear computational efficiency is surprising given that we do not even know how to compute the (edit) distance between the decoding input and output in sub-quadratic time.
• We show that local decodability implies that error correcting codes constructed with long-distance synchronization strings can not only efficiently recover from $$\delta$$ fraction of insdel errors but, similar to [Schulman, Zuckerman; TransInf'99], also from any $$O(\delta / \log n)$$ fraction of block transpositions and block replications. These block corruptions allow arbitrarily long substrings to be swapped or replicated anywhere.
• We show that highly explicitness and local decoding allow for infinite channel simulations with exponentially smaller memory and decoding time requirements. These simulations can then be used to give the first near linear time interactive coding scheme for insdel errors, similar to the result of [Brakerski, Naor; SODA'13] for Hamming errors.

## Teaching Assistance

#### Carnegie Mellon University

Algorithms and Advanced Data Structures (15-350): F17
Graduate Algorithms (15-750): S17

#### Sharif University of Technology

Design and Analysis of Algorithms (22-981/40-384): F13, S14
Introduction to Cryptography (22-813): F13
Introduction to Probability and Statistics (25-732): F12

## Contact

School of Computer Science
Carnegie Mellon University
Pittsburgh PA 15213-3891
Office: 9003 Gates Hillman Center
Email: s...@cs.cmu.edu