We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs). Denote \(n\) and \(w\) as the length and the width of an ROBP. We have the following results. For standard ROBPs, there exists an explicit \(\varepsilon\)-WPRG with seed length \(O\left(\frac{\log n \log(nw)}{\max\{1,\log \log w - \log \log n\}} + \log w \left( \log \log \log w - \log \log \max\left\{2,\frac{\log w}{\log n/\varepsilon}\right\} \right) + \log(1/\varepsilon)\right)\). When \(n = w^{o(1)}\), this is better than the construction of Hoza (RANDOM 2022), and the construction of Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC 2021). Further, by using this in a black-box way, we attain a WPRG for regular ROBPs with seed length \(O\left( \log n \left( \sqrt{\log(1/\varepsilon)} + \log w + \log \log n \right) + \log(1/\varepsilon) \right)\), which slightly improves the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). For permutation ROBPs with unbounded widths and single accept nodes, we give an explicit \(\varepsilon\)-WPRG with seed length \(O\left( \log n \left( \log \log n + \sqrt{\log(1/\varepsilon)} \right) + \log(1/\varepsilon) \right)\), improving the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). A key difference is that our result implies a WPRG with optimal seed length for short-wide ROBPs with multiple accept nodes. Specifically, after switching to multiple accept nodes in a standard way by replacing \(\varepsilon\) with \(\varepsilon/w\), this gives a WPRG with optimal seed length \(O(\log w)\) for \(n = 2^{O(\sqrt{\log w})}\), and error \(1/\operatorname{poly} w\). The only previous work attaining optimal seed lengths are Nisan-Zuckerman style PRGs which are only optimal for \(n = \operatorname{poly}\log w\), \(\varepsilon = 2^{-\log^{0.9} w}\). For regular ROBPs with \(n \le 2^{O(\sqrt{\log w})}\), \(\varepsilon = 1/\operatorname{poly}(w)\), we give a derandomization within space \(O(\log w)\), i.e., in \(\mathbf{L}\) exactly. When requiring the derandomization to be in \(\mathbf{L}\), the only previous result is again by Nisan-Zuckerman style PRGs, which can only handle \(n = \operatorname{poly}\log w\), \(\varepsilon = 2^{-\log^{0.9} w}\). If compared to the result of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), then for \(n = 2^{O(\sqrt{\log w})}\) our derandomization not only improves the space complexity to optimal, but also substantially improves the time complexity from super-polynomial to standard polynomial in \(w\). All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones.

In vision-language models (VLMs), visual tokens usually consume a significant amount of computational overhead, despite their sparser information density compared to text tokens. To address this, most existing methods learn a network to prune redundant visual tokens and require additional training data. Differently, we propose an efficient training-free token optimization mechanism dubbed SparseVLM without extra parameters or fine-tuning costs. Concretely, given that visual tokens complement text tokens in VLMs for linguistic reasoning, we select visual-relevant text tokens to rate the significance of vision tokens within the self-attention matrix extracted from the VLMs. Then we progressively prune irrelevant tokens. To maximize sparsity while retaining essential information, we introduce a rank-based strategy to adaptively determine the sparsification ratio for each layer, alongside a token recycling method that compresses pruned tokens into more compact representations. Experimental results show that our SparseVLM improves the efficiency of various VLMs across a range of image and video understanding tasks. In particular, when LLaVA is equipped with SparseVLM, it achieves a 54% reduction in FLOPs, lowers CUDA time by 37%, and maintains an accuracy rate of 97%. Our code is available at https://github.com/Gumpest/SparseVLMs.

The goal of the trace reconstruction problem is to recover a string$\mathbf {x}\in \{0,1\}^{n}$given many independenttracesofx, where a trace is a subsequence obtained from deleting bits ofxindependently with some given probability$p\in [0,1$). A recent result of Chase (STOC 2021) shows howxcan be determined (in exponential time) from$\exp ({O}(n^{1/5})\log ^{5} n)$traces. This is the state-of-the-art result on the sample complexity of trace reconstruction. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the bound of Chase, which is based on statistics of arbitrary length-ksubsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences ofcontiguous k-bit strings (a.k.a,k-mers) in the initial stringx, for$k = 2n^{1/5}$. Mazooji and Shomorony (arXiv.2210.10917) show that such statistics (calledk-mer density map) can be estimated within$\varepsilon $accuracy from$ {\mathrm {poly}} (n, 2^{k}, 1/ {\varepsilon })$traces. We call an algorithm to bek-mer-basedif it reconstructsxgiven estimates of thek-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that anyk-mer-based algorithm for trace reconstruction must use$\exp (\Omega (n^{1/5} \sqrt {\log n}))$traces, thus establishing the optimality of this number of traces. The analysis of this result also shows that the analysis technique used by Chase (STOC 2021) is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. This result is shown by considering an appropriate class of real polynomials, that have been previously studied in the context of trace estimation (De, O’Donnell, Servedio. Annals of Probability 2019; Nazarov, Peres. STOC 2017), and proving that two of these polynomials are very close to each other on an arc in the complex plane. Our proof of the proximity of such polynomials uses new technical ingredients that allow us to focus on just a few coefficients of these polynomials. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor ofnin the number of samples needed for an optimal algorithm, and show that this factor ofnloss may be necessary under general “model estimation” settings.

Tanner codes are error-correcting codes built from a bipartite graphGand a short inner codeC0. Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ ∈ [0, 1] andd0∈ N must satisfy, so thateverybipartite expanderGwith vertex expansion ratio δ andeverylinear inner codeC0with minimum distanced0together define an expander code that corrects Ω(n) errors inO(n) time? ForC0being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT’96) showed that δ > 3/4 is sufficient; later, Viderman (ACM-TOCT’13) improved this to δ > 2/3 - Ω(1) and he also showed that δ > 1/2 is necessary. For general linear codeC0, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed thatd0= Ω(cδ-2) is sufficient, wherecis the left-degree ofG. We present a near-optimal solution to the above problem for generalC0by showing that δd0> 3 is sufficient and δd0> 1 is necessary, thereby significantly improving Dowling-Gao’s result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes withδd0> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of δ,d0with δd0=1, an expander code with constant distance, that only corrects a constant number of errors.

Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph $G$ together with a linear inner code $C_0$. Expander codes are Tanner codes whose defining bipartite graph $G$ has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that $δ$ and $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(n)$ errors in $O(n)$ time? For $C_0$ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that $δ>3/4$ is sufficient; later Viderman (ACM-TOCT'13) improved this to $δ>2/3-Ω(1)$ and he also showed that $δ>1/2$ is necessary. For general linear code $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(cδ^{-2})$ is sufficient, where $c$ is the left-degree of $G$. In this paper, we give a near-optimal solution to the above question for general $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>1$ is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.

Knowledge distillation (KD) has been applied to various tasks successfully, and mainstream methods typically boost the student model via spatial imitation losses. However, the consecutive downsamplings induced in the spatial domain of teacher model is a type of corruption, hindering the student from analyzing what specific information needs to be imitated, which results in accuracy degradation. To better understand the underlying pattern of corrupted feature maps, we shift our attention to the frequency domain. During frequency distillation, we encounter a new challenge: the low-frequency bands convey general but minimal context, while the high are more informative but also introduce noise. Not each pixel within the frequency bands contributes equally to the performance. To address the above problem: (1) We propose the Frequency Prompt plugged into the teacher model, absorbing the semantic frequency context during finetuning. (2) During the distillation period, a pixel-wise frequency mask is generated via Frequency Prompt, to localize those pixel of interests (PoIs) in various frequency bands. Additionally, we employ a position-aware relational frequency loss for dense prediction tasks, delivering a high-order spatial enhancement to the student model. We dub our Frequency Knowledge Distillation method as FreeKD, which determines the optimal localization and extent for the frequency distillation. Extensive experiments demonstrate that FreeKD not only outperforms spatial-based distillation methods consistently on dense prediction tasks (e.g., FreeKD brings 3.8 AP gains for RepPoints-R50 on COCO2017 and 4.55 mIoU gains for PSPNet-R18 on Cityscapes), but also conveys more robustness to the student. Notably, we also validate the generalization of our approach on large-scale vision models (e.g., DINO and SAM).

The goal of the trace reconstruction problem is to recover a string x E {0, 1} given many independent traces of x, where a trace is a subsequence obtained from deleting bits of x independently with some given probability. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the state-of-the-art result of Chase (STOC 2021), which is based on statistics of arbitrary length-k subsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences of contiguous k-bit strings (a.k.a, k-mers) in the initial string x, for k = Mazooji and Shomorony (ISIT 2023) show that such statistics (called k-mer density map) can be estimated within accuracy from poly(n, 2k, l/e) traces. We call an algorithm to be k-mer-based if it reconstructs x given estimates of the k-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any k-mer-based algorithm for trace reconstruction must use exp n)) traces, under the assumption that the estimator requires poly(2k, 1 e) traces, thus establishing the optimality of this number of traces. Our analysis also shows that the analysis technique used by Chase is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of$n$in the number of samples needed for an optimal algorithm, and show that this factor of$n$loss may be necessary under general “model estimation” settings.

Large vision-language models (LVLMs) have recently achieved rapid progress, exhibiting great perception and reasoning abilities concerning visual information. However, when faced with prompts in different sizes of solution spaces, LVLMs fail to always give consistent answers regarding the same knowledge point. This inconsistency of answers between different solution spaces is prevalent in LVLMs and erodes trust. To this end, we provide a multi-modal benchmark ConBench, to intuitively analyze how LVLMs perform when the solution space of a prompt revolves around a knowledge point. Based on the ConBench tool, we are the first to reveal the tapestry and get the following findings: (1) In the discriminate realm, the larger the solution space of the prompt, the lower the accuracy of the answers. (2) Establish the relationship between the discriminative and generative realms: the accuracy of the discriminative question type exhibits a strong positive correlation with its Consistency with the caption. (3) Compared to open-source models, closed-source models exhibit a pronounced bias advantage in terms of Consistency. Eventually, we ameliorate the consistency of LVLMs by trigger-based diagnostic refinement, indirectly improving the performance of their caption. We hope this paper will accelerate the research community in better evaluating their models and encourage future advancements in the consistency domain.

Locally Decodable Codes (LDCs) are error-correcting codes $C:Σ^n\rightarrow Σ^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson et al. showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Insdel LDCs were first studied by Ostrovsky and Paskin-Cherniavsky, and are further motivated by recent advances in DNA random access bio-technologies, in which the goal is to retrieve individual files from a DNA storage database. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish. Our result exhibits a "phase-transition"-type behavior on the codeword length for constant-query Hamming RLDCs. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with with parameters matching those of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs.

This work continues the study of linear error correcting codes against adversarial insertion deletion errors (insdel errors). Previously, the work of Cheng, Guruswami, Haeupler, and Li \cite{CGHL21} showed the existence of asymptotically good linear insdel codes that can correct arbitrarily close to $1$ fraction of errors over some constant size alphabet, or achieve rate arbitrarily close to $1/2$ even over the binary alphabet. As shown in \cite{CGHL21}, these bounds are also the best possible. However, known explicit constructions in \cite{CGHL21}, and subsequent improved constructions by Con, Shpilka, and Tamo \cite{9770830} all fall short of meeting these bounds. Over any constant size alphabet, they can only achieve rate $< 1/8$ or correct $< 1/4$ fraction of errors; over the binary alphabet, they can only achieve rate $< 1/1216$ or correct $< 1/54$ fraction of errors. Apparently, previous techniques face inherent barriers to achieve rate better than $1/4$ or correct more than $1/2$ fraction of errors. In this work we give new constructions of such codes that meet these bounds, namely, asymptotically good linear insdel codes that can correct arbitrarily close to $1$ fraction of errors over some constant size alphabet, and binary asymptotically good linear insdel codes that can achieve rate arbitrarily close to $1/2$.\ All our constructions are efficiently encodable and decodable. Our constructions are based on a novel approach of code concatenation, which embeds the index information implicitly into codewords. This significantly differs from previous techniques and may be of independent interest. Finally, we also prove the existence of linear concatenated insdel codes with parameters that match random linear codes, and propose a conjecture about linear insdel codes.

Abstract. This paper studies linear and affine error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine insdel codes. Linear codes that can correct even a single deletion are limited to having an information rate at most [Formula: see text] (achieved by the trivial two fold repetition code). Previously, it was (erroneously) reported that more generally no nontrivial linear codes correcting [Formula: see text] deletions exist, i.e., that the [Formula: see text]-fold repetition codes and its rate of [Formula: see text] are basically optimal for any [Formula: see text]. We disprove this and show the existence of binary linear codes of length [Formula: see text] and rate just below [Formula: see text] capable of correcting [Formula: see text] insertions and deletions. This identifies rate [Formula: see text] as a sharp threshold for recovery from deletions for linear codes and reopens the quest for a better understanding of the capabilities of linear codes for correcting insertions/deletions. We prove novel outer bounds and existential inner bounds for the rate vs. (edit) distance trade-off of linear insdel codes. We complement our existential results with an efficient synchronization-string-based transformation that converts any asymptotically good linear code for Hamming errors into an asymptotically good linear code for insdel errors. Last, we show that the [Formula: see text]-rate limitation does not hold for affine codes by giving an explicit affine code of rate [Formula: see text] which can efficiently correct a constant fraction of insdel errors.

We study the classical expander codes, introduced by Sipser and Spielman, (1996). Given any constants$0 < \alpha, \varepsilon < 1/2$, and an arbitrary bipartite graph with$N$vertices on the left,$M < N$vertices on the right, and left degree$D$such that any left subset$S$of size at most$\alpha N$has at least$(1- \varepsilon)|S|D$neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly$\frac {\alpha N}{2 \varepsilon }$. This is strictly better than the best known previous result of$2(1- \varepsilon) \alpha N$Sudan, (2000), Viderman, (2013) whenever$\varepsilon < 1/2$, and improves the previous result significantly when$\varepsilon $is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever$\varepsilon < \frac {1}{4}$. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.

We study the classical expander codes, introduced by Sipser and Spielman \cite{SS96}. Given any constants $0< α, \varepsilon < 1/2$, and an arbitrary bipartite graph with $N$ vertices on the left, $M < N$ vertices on the right, and left degree $D$ such that any left subset $S$ of size at most $αN$ has at least $(1-\varepsilon)|S|D$ neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly $\frac{αN}{2 \varepsilon }$. This is strictly better than the best known previous result of $2(1-\varepsilon ) αN$ \cite{Sudan2000note, Viderman13b} whenever $\varepsilon < 1/2$, and improves the previous result significantly when $\varepsilon $ is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever $\varepsilon < \frac{1}{4}$. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.

We study two basic problems regarding edit errors, document exchange and error correcting codes. Here, two parties try to exchange two strings with length roughly n and edit distance at most k , or one party tries to send a string of length n to another party through a channel that can introduce at most k edit errors. The goal is to use the least amount of communication or redundancy possible. Both problems have been extensively studied for decades, and in this article, we focus on deterministic document exchange protocols and binary codes for insertions and deletions (insdel codes). It is known that for small k (e.g., k ≤ n/4 ), in both problems the optimal communication or redundancy size is Θ ( k log n/k). In particular, this implies the existence of binary codes that can correct ε fraction of edit errors with rate 1-Θ (ε log 1/ε )). However, known constructions are far from achieving these bounds. In this article, we significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with communication complexity O ( k log 2 n/k . This significantly improves the previous best-known deterministic protocol, which has communication complexity O ( k 2 + k log 2 n ) [ 4 ]. For binary insdel codes, we obtain the following results: (1) An explicit binary insdel code with redundancy O ( k log 2 n/k). In particular this implies an explicit family of binary insdel codes that can correct ε fraction of insertions and deletions with rate 1-O(ε log 2 (1/ε))=1-Õ(ε). This significantly improves the previous best-known result, which only achieves rate 1-Õ(√ ε) [ 14 ], [ 15 ], and is optimal up to a log (1/ε factor. (2) An explicit binary insdel code with redundancy O ( k log n ). This significantly improves the previous best-known result of Reference [ 6 ], which only works for constant k and has redundancy O ( k 2 log k log n ); and that of Reference [ 4 ], which has redundancy O ( k 2 + k log 2 n ). Our code has optimal redundancy for k ≤ n 1-α , any constant 0< α < 1. This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters k . In obtaining our results, we introduce several new techniques. Most notably, we introduce the notion of ε-self-matching hash functions and ε-synchronization hash functions . We believe our techniques can have further applications in the literature.

Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have been studied extensively in the past few decades, where a major goal is to understand the amount of redundancy that is necessary and sufficient to decode from large amounts of error, with small query complexity. Despite exciting progress, we still don't have satisfactory answers in several important parameter regimes. For example, in the case of 3-query LDCs, the gap between existing constructions and lower bounds is superpolynomial in the message length. In this work we study LDCs for insertion and deletion errors, called Insdel LDCs. Their study was initiated by Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015), who gave a reduction from Hamming LDCs to Insdel LDCs with a small blowup in the code parameters. On the other hand, the only known lower bounds for Insdel LDCs come from those for Hamming LDCs, thus there is no separation between them. Here we prove new, strong lower bounds for the existence of Insdel LDCs. In particular, we show that 2-query linear Insdel LDCs do not exist, and give an exponential lower bound for the length of all q-query Insdel LDCs with constant q. For$q$≥ 3 our bounds are exponential in the existing lower bounds for Hamming LDCs. Furthermore, our exponential lower bounds continue to hold for adaptive decoders, and even in private-key settings where the encoder and decoder share secret randomness. This exhibits a strict separation between Hamming LDCs and Insdel LDCs. Our strong lower bounds also hold for the related notion of Insdel LCCs (except in the private-key setting), due to an analogue to the Insdel notions of a reduction from Hamming LCCs to LDCs. Our techniques are based on a delicate design and analysis of hard distributions of insertion and deletion errors, which depart significantly from typical techniques used in analyzing Hamming LDCs.

The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we first consider these problems in the asymmetric streaming model introduced by Andoni, Krauthgamer and Onak [Andoni et al., 2010] (FOCS'10) and Saks and Seshadhri [Saks and Seshadhri, 2013] (SODA'13). In this model we have random access to one string and streaming access the other one. Our main contribution is a constant factor approximation algorithm for ED with memory Õ(n^δ) for any constant δ > 0. In addition to this, we present an upper bound of Õ _ε(√n) on the memory needed to approximate ED or LCS within a factor 1±ε. All our algorithms are deterministic and run in polynomial time in a single pass. We further study small-space approximation algorithms for ED, LCS, and longest increasing sequence (LIS) in the non-streaming setting. Here, we design algorithms that achieve 1 ± ε approximation for all three problems, where ε > 0 can be any constant and even slightly sub-constant. Our algorithms only use poly-logarithmic space while maintaining a polynomial running time. This significantly improves previous results in terms of space complexity, where all known results need to use space at least Ω(√n). Our algorithms make novel use of triangle inequality and carefully designed recursions to save space, which can be of independent interest.

This paper studies linear and affine error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine insdel codes. Linear codes that can correct even a single deletion are limited to have information rate at most 1/2 (achieved by the trivial 2-fold repetition code). Previously it was (erroneously) reported that more generally no non-trivial linear codes correcting k deletions exist, i.e., that the (k + 1)-fold repetition codes and its rate of 1/(k + 1) are basically optimal for any k. We disprove this and show the existence of binary linear codes of length n and rate just below 1/2 capable of correcting Ω(n) insertions and deletions. This identifies rate 1/2 as a sharp threshold for recovery from deletions for linear codes, and reopens the quest for a better understanding of the capabilities of linear codes for correcting insertions/deletions. We prove novel outer bounds and existential inner bounds for the rate vs. (edit) distance trade-off of linear insdel codes. We complement our existential results with an efficient synchronization-string-based transformation that converts any asymptotically-good linear code for Hamming errors into an asymptotically-good linear code for insdel errors. Lastly we show that the ½-rate limitation does not hold for affine codes by giving an explicit affine code of rate 1 – ∊ which can efficiently correct a constant fraction of insdel errors.

We study two fundamental problems in communication, Document Exchange (DE) and Error Correcting Code (ECC). In the first problem, two parties hold two strings, and one party tries to learn the other party's string through communication. In the second problem, one party tries to send a message to another party through a noisy channel, by adding some redundant information to protect the message. Two important goals in both problems are to minimize the communication complexity or redundancy, and to design efficient protocols or codes. Both problems have been studied extensively. In this paper we study whether asymmetric partial information can help in these two problems. We focus on the case of Hamming distance/errors, and the asymmetric partial information is modeled by one party having a vector of disjoint subsets S = (S1, …, St) of indices and a vector of integers k = (k1, …, kt), such that in each Si the Hamming distance/errors is at most ki. To our knowledge, no previous work has studied this problem systematically. We establish both lower bounds and upper bounds in this model, and provide efficient randomized constructions that achieve a min{O(t2), O((log log n)2)} factor within the optimum, with almost linear running time. We further show a connection between the above document exchange problem and the problem of document exchange under edit distance, and use our techniques to give an efficient randomized protocol with optimal communication complexity and exponentially small error for the latter. This improves the previous result by Haeupler [20] (FOCS'19), which has polynomially large error; and that by Belazzougui and Zhang [8] (FOCS'16), which is only optimal for a limited range of parameters. Our techniques are based on a generalization of the celebrated expander codes by Sipser and Spielman [36], which may be of independent interests.

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if there is a log-space hitting set for polynomial-width read-once branching programs (ROBPs), then not only does 𝐋 = 𝐑𝐋, but 𝐋 = 𝐁𝐏𝐋 as well. This answers a question raised by Hoza and Zuckerman [William M. Hoza and David Zuckerman, 2018]. Next, we consider constant-width ROBPs. We show that if there are log-space hitting sets for constant-width ROBPs, then given black-box access to a constant-width ROBP f, it is possible to deterministically estimate 𝔼[f] to within ± ε in space O(log(n/ε)). Unconditionally, we give a deterministic algorithm for this problem with space complexity O(log² n + log(1/ε)), slightly improving over previous work. Finally, we investigate the limits of this line of work. Perhaps the strongest reduction along these lines one could hope for would say that for every explicit hitting set, there is an explicit PRG with similar parameters. In the setting of constant-width ROBPs over a large alphabet, we prove that establishing such a strong reduction is at least as difficult as constructing a good PRG outright. Quantitatively, we prove that if the strong reduction holds, then for every constant α > 0, there is an explicit PRG for constant-width ROBPs with seed length O(log^{1 + α} n). Along the way, unconditionally, we construct an improved hitting set for ROBPs over a large alphabet.

Document exchange and error correcting codes are two fundamental problems regarding communications. In the first problem, Alice and Bob each holds a string, and the goal is for Alice to send a short sketch to Bob, so that Bob can recover Alice’s string. In the second problem, Alice sends a message with some redundant information to Bob through a channel that can add adversarial errors, and the goal is for Bob to correctly recover the message despite the errors. In both problems, an upper bound is placed on the number of errors between the two strings or that the channel can add, and a major goal is to minimize the size of the sketch or the redundant information. In this paper we focus on deterministic document exchange protocols and binary error correcting codes. Both problems have been studied extensively. In the case of Hamming errors (i.e., bit substitutions) and bit erasures, we have explicit constructions with asymptotically optimal parameters. However, other error types are still rather poorly understood. In a recent work [Kuan Cheng et al., 2018], the authors constructed explicit deterministic document exchange protocols and binary error correcting codes for edit errors with almost optimal parameters. Unfortunately, the constructions in [Kuan Cheng et al., 2018] do not work for other common errors such as block transpositions. In this paper, we generalize the constructions in [Kuan Cheng et al., 2018] to handle a much larger class of errors. These include bursts of insertions and deletions, as well as block transpositions. Specifically, we consider document exchange and error correcting codes where the total number of block insertions, block deletions, and block transpositions is at most k <= alpha n/log n for some constant 0<alpha<1. In addition, the total number of bits inserted and deleted by the first two kinds of operations is at most t <= beta n for some constant 0<beta<1, where n is the length of Alice’s string or message. We construct explicit, deterministic document exchange protocols with sketch size O((k log n +t) log^2 n/{k log n + t}) and explicit binary error correcting code with O(k log n log log log n+t) redundant bits. As a comparison, the information-theoretic optimum for both problems is Theta(k log n+t). As far as we know, previously there are no known explicit deterministic document exchange protocols in this case, and the best known binary code needs Omega(n) redundant bits even to correct just one block transposition [L. J. Schulman and D. Zuckerman, 1999].

Synchronization strings are recently introduced by Haeupler and Shahrasbi [1] in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronization string is an encoding of the indices of the symbols in a string, and together with an appropriate decoding algorithm it can transform insertion and deletion errors into standard symbol erasures and corruptions. This reduces the problem of constructing insdel codes to the problem of constructing standard error correcting codes, which is much better understood. Besides this, synchronization strings are also useful in other applications such as synchronization sequences and interactive coding schemes. For all such applications, synchronization strings are desired to be over alphabets that are as small as possible, since a larger alphabet size corresponds to more redundant information added. Haeupler and Shahrasbi [1] showed that for any parameter ε > 0, synchronization strings of arbitrary length exist over an alphabet whose size depends only on ε. Specifically, [1] obtained an alphabet size of O(ε−4), which left an open question on where the minimal size of such alphabets lies between Ω(ε−1) and O(ε−4). In this work, we partially bridge this gap by providing an improved lower bound of Ω (ε−3/2), and an improved upper bound of O (ε−2). We also provide fast explicit constructions of synchronization strings over small alphabets. Further, along the lines of previous work on similar combinatorial objects, we study the extremal question of the smallest possible alphabet size over which synchronization strings can exist for some constant ε < 1. We show that one can construct ε-synchronization strings over alphabets of size four while no such string exists over binary alphabets. This reduces the extremal question to whether synchronization strings exist over ternary alphabets.

Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice. While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than P. In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits (AC0), and (2) the local computation model. Previous work in these models, such as [Vio05a], [GVW15] and [BG13], only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. As an application, we use our AC0 extractors to study pseudorandom generators in AC0, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters. Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the AC0 property and small locality, and (2) a seeded randomness condenser with small locality.

We study two basic problems regarding edit errors (insertions and deletions). The first one is document exchange, where two parties Alice and Bob hold two strings x and y with a bounded edit distance k. The goal is to have Alice send a short sketch to Bob, so that Bob can recover x based on y and the sketch. The second one is the fundamental problem of designing error correcting codes for edit errors, where the goal is to construct an explicit code to transmit a message x through a channel that can add at most k worst case insertions and deletions, so that the original message x can be successfully recovered at the other end of the channel. Both problems have been extensively studied for decades, and in this paper we focus on deterministic document exchange protocols and binary codes for insertions and deletions (insdel codes). If the length of x is n, then it is known that for small k (e.g., k ≤ n/4), in both problems the optimal sketch size or the optimal number of redundant bits is Θ(k log n/k). In particular, this implies the existence of binary codes that can correct ε fraction of insertions and deletions with rate 1-Θ(ε log (1/ε). However, known constructions are far from achieving these bounds. In this paper we significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size O(k log2n/k). This significantly improves the previous best known deterministic protocol, which has sketch size O(k2+ k log2n) [2]. For binary insdel codes, we obtain the following results: 1) An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log2n/k). In particular this implies an explicit family of binary insdel codes that can correct ε fraction of insertions and deletions with rate 1-O(ε log21/(1-ε))=1-Õ(ε). This significantly improves the previous best known result which only achieves rate 1-Õ(√ε) [11], [10], and is optimal up to a log (1/ε) factor. 1) An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log n). This significantly improves the previous best known result of [4], which only works for constant k and has redundancy O(k2log k log n); and that of [2], which has redundancy O(k2+ k log2n). Our code has optimal redundancy for k ≤ n1-α, any constant 0 <; α <; 1. This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters k, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes. In obtaining our results we introduce several new techniques. Most notably, we introduce the notion of ε-self matching hash functions and ε-synchronization hash functions. We believe our techniques can have further applications in the literature.