We prove several results on linear codes achieving list-recovery capacity. We show that random linear codes achieve list-recovery capacity with constant output list size (independent of the alphabet size and length). That is, over alphabets of size at least 𝓁^Ω(1/ε), random linear codes of rate R are (1-R-ε, 𝓁, (𝓁/ε)^O(𝓁/ε))-list-recoverable for all R ∈ (0,1) and 𝓁. Together with a result of Levi, Mosheiff, and Shagrithaya, this implies that randomly punctured Reed-Solomon codes also achieve list-recovery capacity. We also prove that our output list size is near-optimal among all linear codes: all (1-R-ε, 𝓁, L)-list-recoverable linear codes must have L ≥ 𝓁^{Ω(R/ε)}. Our simple upper bound combines the Zyablov-Pinsker argument with recent bounds from Kopparty, Ron-Zewi, Saraf, Wootters, and Tamo on the maximum intersection of a "list-recovery ball" and a low-dimensional subspace with large distance. Our lower bound is inspired by a recent lower bound of Chen and Zhang.

In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - with linear-sized alphabets. More precisely, we prove that, for any ε > 0 and positive integers n and k, with high probability, random Reed-Solomon codes of length n and dimension k can correct (1-ε)n-2k+1 adversarial insdel errors over alphabets of size n+2^{poly(1/ε)}k. This significantly improves upon the alphabet size demonstrated in the work of Con, Shpilka, and Tamo (IEEE TIT, 2023), who showed the existence of Reed-Solomon codes with exponential alphabet size Õ(binom(n,2k-1)²) precisely achieving the half-Singleton bound. Our methods are inspired by recent works on list-decoding Reed-Solomon codes. Brakensiek-Gopi-Makam (STOC 2023) showed that random Reed-Solomon codes are list-decodable up to capacity with exponential-sized alphabets, and Guo-Zhang (FOCS 2023) and Alrabiah-Guruswami-Li (STOC 2024) improved the alphabet-size to linear. We achieve a similar alphabet-size reduction by similarly establishing strong bounds on the probability that certain random rectangular matrices are full rank. To accomplish this in our insdel context, our proof combines the random matrix techniques from list-decoding with structural properties of Longest Common Subsequences.

Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of articles on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC’21] and [Dalirrooyfard and Wein, STOC’21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer k ≥ 2 and δ > 0, a \(2-\frac{1}{k}-\delta\) approximation for diameter in directed m -edge graphs requires \(m^{1+1/(k-1)-o(1)}\) time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this article, we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC’13], [Li’20] and [Bonnet, ICALP’21] who proved the first few cases of the curve, k =2,3, and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is conditionally optimal for undirected graphs. To obtain our result, we extract the core ideas in known reductions and introduce a unification and generalization that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rateRcodes are not list-decodable using list-sizeLbeyond an error fractionL/L+1 (1-R) (the Singleton bound being the case ofL= 1, i.e., unique decoding). We prove that in order to approach this bound for any fixedL> 1, one needs exponential alphabets. Specifically, for everyL> 1 andR∈ (0, 1), if a rateRcode can be list-of-Ldecoded up to error fractionL/L+1 (1 -R- ε), then its alphabet must have size at least exp(ΩL,R(1/ε)). This is in sharp contrast to the situation for unique decoding where certain families of rateRalgebraic-geometry (AG) codes over an alphabet of sizeO(1/ε2) are unique-decodable up to error fraction (1 -R- ε)/2. Our bounds hold even for subconstant ε ≥ 1/n, implying that any code exactly achieving theL-th generalized Singleton bound requires alphabet size 2ΩL,R(n). Previously this was only known only forL= 2 under the additional assumptions that the code is both linear and MDS. Our lower bound is tight up to constant factors in the exponent—with high probability random codes (or, as shown recently, even random linear codes) over exp(OL(1/ε))-sized alphabets, can be list-of-Ldecoded up to error fractionL/L+1 (1-R- ε).

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate R codes are not list-decodable using list-size L beyond an error fraction (the Singleton bound being the case of L = 1, i.e., unique decoding). We prove that in order to approach this bound for any fixed L > 1, one needs exponential alphabets. Specifically, for every L > 1 and R ∈ (0,1), if a rate R code can be list-of-L decoded up to error fraction , then its alphabet must have size at least exp(ΩL,R(1/ɛ)). This is in sharp contrast to the situation for unique decoding where certain families of rate R algebraic-geometry (AG) codes over an alphabet of size O(1/ɛ2) are unique-decodable up to error fraction (1 — R — ɛ)/2.

Reed–Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a fundamental question in coding theory is determining if Reed–Solomon codes can optimally achieve list-decoding capacity. A recent breakthrough by Brakensiek, Gopi, and Makam, established that Reed–Solomon codes are combinatorially list-decodable all the way to capacity. However, their results hold for randomly-punctured Reed–Solomon codes over an exponentially large field size 2O(n), where n is the block length of the code. A natural question is whether Reed–Solomon codes can still achieve capacity over smaller fields. Recently, Guo and Zhang showed that Reed–Solomon codes are list-decodable to capacity with field size O(n2). We show that Reed–Solomon codes are list-decodable to capacity with linear field size O(n), which is optimal up to the constant factor. We also give evidence that the ratio between the alphabet size q and code length n cannot be bounded by an absolute constant. Our techniques also show that random linear codes are list-decodable up to (the alphabet-independent) capacity with optimal list-size O(1/ε) and near-optimal alphabet size 2O(1/ε2), where ε is the gap to capacity. As far as we are aware, list-decoding up to capacity with optimal list-size O(1/ε) was not known to be achievable with any linear code over a constant alphabet size (even non-constructively), and it was also not known to be achievable for random linear codes over any alphabet size. Our proofs are based on the ideas of Guo and Zhang, and we additionally exploit symmetries of reduced intersection matrices. With our proof, which maintains a hypergraph perspective of the list-decoding problem, we include an alternate presentation of ideas from Brakensiek, Gopi, and Makam that more directly connects the list-decoding problem to the GM-MDS theorem via a hypergraph orientation theorem.

Abstract. This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite fields in the code length, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving the list-decoding capacity. In particular, we show that for any [Formula: see text] there exist RS codes with rate [Formula: see text] that are list-decodable from radius of [Formula: see text]. We generalize this result to list-recovery, showing that there exist [Formula: see text]-list-recoverable RS codes with rate [Formula: see text]. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree packing theorem to hypergraphs and show that if this conjecture holds, then there would exist RS codes that are optimally (nonasymptotically) list-decodable.

Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time Hypothesis (SETH) yields a lower bound on the time vs. approximation trade-off that is quite close to the upper bounds. In \emph{directed} graphs, however, where only some of the upper bounds apply, much larger gaps remain. Since $d(u,v)$ may not be the same as $d(v,u)$, there are multiple ways to define the problem, the two most natural being the \emph{(one-way) diameter} ($\max_{(u,v)} d(u,v)$) and the \emph{roundtrip diameter} ($\max_{u,v} d(u,v)+d(v,u)$). In this paper we make progress on the outstanding open question for each of them. -- We design the first algorithm for diameter in sparse directed graphs to achieve $n^{1.5-\varepsilon}$ time with an approximation factor better than $2$. The new upper bound trade-off makes the directed case appear more similar to the undirected case. Notably, this is the first algorithm for diameter in sparse graphs that benefits from fast matrix multiplication. -- We design new hardness reductions separating roundtrip diameter from directed and undirected diameter. In particular, a $1.5$-approximation in subquadratic time would refute the All-Nodes $k$-Cycle hypothesis, and any $(2-\varepsilon)$-approximation would imply a breakthrough algorithm for approximate $\ell_{\infty}$-Closest-Pair. Notably, these are the first conditional lower bounds for diameter that are not based on SETH.

The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programming algorithm gives an exact algorithm in quadratic time, and this is essentially best possible under plausible fine-grained complexity assumptions, so a natural problem is to find faster approximation algorithms. When the inputs are two binary strings, there is a simple 1/2-approximation in linear time: compute the longest common all-0s or all-1s subsequence. It has been open whether a better approximation is possible even in truly subquadratic time. Rubinstein and Song showed that the answer is yes under the assumption that the two input strings have equal lengths. We settle the question, generalizing their result to unequal length strings, proving that, for any ε>0, there exists δ>0 and a (1/2+δ)-approximation algorithm for binary LCS that runs in n1+ε time. As a consequence of our result and a result of Akmal and Vassilevska-Williams, for any ε>0, there exists a (1/q+δ)-approximation for LCS over q-ary strings in n1+ε time.

We prove that there exists an absolute constant$\delta >0$such that any binary code$C\subset \{0,1\}^{N} \vphantom {_{\int }}$tolerating$(1/2-\delta)N$adversarial deletions must satisfy$|C|\le 2^{ \mathop {\mathrm {poly}} \log N}$and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating$N/2$adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants$A$and$\delta >0$such that any set$C\subset \{0,1\}^{N}$of$2^{\log ^{A} N}$binary strings must contain two strings$c$and$c'$whose longest common subsequence has length at least$(1/2+\delta)N$. As an immediate corollary, we show that$q$-ary codes tolerating a fraction$1-(1+2\delta)/q$of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.

In this paper, we present CopyCat2 (CC2), a novel model capable of: a) synthesizing speech with different speaker identities, b) generating speech with expressive and contextually appropriate prosody, and c) transferring prosody at fine-grained level between any pair of seen speakers.We do this by activating distinct parts of the network for different tasks.We train our model using a novel approach to two-stage training.In Stage I, the model learns speaker-independent word-level prosody representations from speech which it uses for many-to-many finegrained prosody transfer.In Stage II, we learn to predict these prosody representations using the contextual information available in text, thereby, enabling multi-speaker TTS with contextually appropriate prosody.We compare CC2 to two strong baselines, one in TTS with contextually appropriate prosody, and one in fine-grained prosody transfer.CC2 reduces the gap in naturalness between our baseline and copy-synthesised speech by 22.79%.In fine-grained prosody transfer evaluations, it obtains a relative improvement of 33.15% in target speaker similarity.

Batch codes are a useful notion of locality for error correcting codes, originally introduced in the context of distributed storage and cryptography. Many constructions of batch codes have been given, but few lower bound (limitation) results are known, leaving gaps between the best known constructions and best known lower bounds. Towards determining the optimal redundancy of batch codes, we prove a new lower bound on the redundancy of batch codes. Specifically, we study (primitive, multiset) linear batch codes that systematically encode n information symbols, with the requirement that any multiset of k symbol requests can be obtained in disjoint ways. We show that such batch codes need $\Omega (\sqrt {nk} )$ symbols of redundancy, improving on the previous best lower bounds of $\Omega (\sqrt n + k)$ at all k = nεwith ε ∈ (0,1). Our proof follows from analyzing the dimension of the order-O(k) tensor of the batch code’s dual code.

Given a probability distribution D over the nonnegative integers, a D-repeat channel acts on an input symbol by repeating it a number of times distributed as D. For example, the binary deletion channel (D=Bernoulli) and the Poisson repeat channel (D=Poisson) are special cases. We say a D-repeat channel is square-integrable if D has finite first and second moments. In this paper, we construct explicit codes for all square-integrable D-repeat channels with rate arbitrarily close to the capacity, that are encodable and decodable in linear and quasi-linear time, respectively. We also consider possible extensions to the repeat channel model, and illustrate how our construction can be extended to an even broader class of channels capturing insertions, deletions, and substitutions.Our work offers an alternative, simplified, and more general construction to the recent work of Rubinstein [3], who attains similar results to ours in the cases of the deletion channel and the Poisson repeat channel. It also slightly improves the runtime and decoding failure probability of the polar codes constructions of Tal et al. [1] and of Pfister and Tal [2] for the deletion channel and certain insertion/deletion/substitution channels. Our techniques follow closely the approaches of Guruswami and Li [4] and Con and Shpilka [5]; what sets apart our work is that to obtain our result, we show that a capacity-achieving code for the channels in question can be assumed to have an "approximate balance" in the frequency of zeros and ones of all sufficiently long substrings of all codewords. This allows us to attain near-capacity-achieving codes in a general setting. We consider this "approximate balance" result to be of independent interest, as it can be cast in much greater generality than just repeat channels.A full version of this paper is available at https://arxiv.org/abs/2201.12746.

A family of error-correcting codes is list-decodable from error fraction$p$if, for every code in the family, the number of codewords in any Hamming ball of fractional radius$p$is less than some integer$L$. It is said to be list-recoverable for input list size$\ell $if for every sufficiently large subset of at least$L$codewords, there is a coordinate where the codewords take more than$\ell $values. In this work, we study the list size ofrandom linear codesfor both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below$q$is the alphabet size, and$ \varepsilon > 0$is the gap to capacity). (1) A random linear code of rate$1 - \log _{q}(\ell) - \varepsilon $requires list size$L \ge \ell ^{\Omega (1/ \varepsilon)}$for list-recovery from input list size$\ell $. (2) A random linear code of rate$1 - h_{q}(p) - \varepsilon $requires list size$L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $for list-decoding from error fraction$p$. (3) A randombinarylinear code of rate$1 - h_{2}(p) - \varepsilon $is list-decodable fromaverageerror fraction$p$with list size with$L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018).

Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer$k\geq 2$and$\delta > 0$, a$2-\frac{1}{k}-\delta$approximation for diameter in directed$m$-edge graphs requires$mn^{1+1/(k-1)-o(1)}$time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC'13], [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve,$k=2,3$and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is also optimal for undirected graphs. To obtain our result we develop new tools for fine-grained reductions that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.

This paper shows that there exist Reed-Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ε E (0,1] there exist RS codes with rate$\Omega(\frac{\varepsilon}{1\not\varepsilon(1/_{\in})+1})$that are list-decodable from radius of 1-ε. We generalize this result to list-recovery, showing that there exist$(1-\varepsilon,\ell, O(\ell/\varepsilon))$-list-recoverable RS codes with rate$\Omega\left(\frac{\varepsilon}{\sqrt{\ell}(\log(1/\varepsilon)+1)}\right)$. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree-packing theorem to hypergraphs, and show that if this conjecture holds, then there would exist RS codes that are optimally (non-asymptotically) list-decodable.11A full version of this paper is available online at https://arxiv.org/abs/2011.04453.

We prove that there exists an absolute constant 6 > 0 such any binary code$C$⊂ {0, 1}Ntolerating (1/2 - δ)$N$adversarial deletions must satisfy| C| ≤ 2polylog$N$and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating$N$/2 adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants$A$and 6 > 0 such that any set$C$⊂ {0, 1} of 2logAN binary strings must contain two strings$c$and c’ whose longest common subsequence has length at least (1/2 + δ) N. As an immediate corollary, we show that q-ary codes tolerating a fraction 1 - (1 + 2δ) /$q$of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.

We define wedge-lifted codes, a variant of lifted codes, and we study their locality properties. We show that (taking the trace of) wedge-lifted codes yields binary codes with the$t$-disjoint repair property ($t$-DRGP). When$t= N^{1/2d}$, where$N$is the block length of the code and$d\geq 2$is any integer, our codes give improved trade-offs between redundancy and locality among binary codes.

We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any ε>0, assuming the Strong Exponential Time Hypothesis (SETH), there are no near-linear time 2−ε-approximation algorithms for the Diameter of a sparse directed graph, even in unweighted graphs. This result shows that a simple near-linear time 2-approximation algorithm for Diameter is optimal under SETH, answering a question from a survey of Rubinstein and Vassilevska-Williams (SIGACT ’19) for the case of directed graphs.

For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming, to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.

Lifted Reed-Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we calllifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the$t$-disjoint-repair-group property than previously known constructions. As a corollary, they also give better tradeoffs for PIR codes in the same parameter regimes. More precisely, we show that, for$t\le \sqrt {N}$, lifted multiplicity codes with length$N$and redundancy$O(t^{0.585} \sqrt {N})$have the property that any symbol of a codeword can be reconstructed in$t$different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant$t < \sqrt {N}$. We also give an alternative analysis of lifted Reed-Solomon codes using dual codes, which may be of independent interest.

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate 1- H(p)- ∈ is (p, O(1/∈))-list-decodable with high probability. In this work, we show that such codes are (p, H(p)/∈ + 2)list-decodable with high probability, for any p ∈ (0, 1/2) and ∈ > 0. In addition to improving the constant in known list-size bounds, our argument-which is quite simple-works simultaneously for all values of p, while previous works obtaining L = O(1/∈) patched together different arguments to cover different parameter regimes. Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain an essentially tight lower bound of 1/∈ on the list size of uniformly random codes; this implies that random linear codes are in fact more list-decodable than uniformly random codes, in the sense that the list sizes are strictly smaller. To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear codes and (b) to prove a similar result for random linear rank-metric codes.

The coded trace reconstruction problem asks to construct a code C ⊂ {0,1}nsuch that any x ∈ C is recoverable from independent outputs (“traces”) of x from a binary deletion channel (BDC). We present binary codes of rate 1-ε that are efficiently recoverable from exp(Oq(log1/3([1/(ε)]))) (a constant independent of n) traces of a BDCq for any constant deletion probability q ∈ (0,1). We also show that, for rate 1 -ε binary codes, ~Ω(log5/2(1/ε)) traces are required. The results follow from a pair of black-box reductions that show that average-case trace reconstruction is essentially equivalent to coded trace reconstruction. We also show that there exist codes of rate 1 -ε over an Oε(1)-sized alphabet that are recoverable from O(log(1/ε)) traces, and that this is tight.

Decision Tree is a classic formulation of active learning: given n hypotheses with nonnegative weights summing to 1 and a set of tests that each partition the hypotheses, output a decision tree using the provided tests that uniquely identifies each hypothesis and has minimum (weighted) average depth. Previous works showed that the greedy algorithm achieves a O(log n) approximation ratio for this problem and it is NP-hard beat a O(log n) approximation, settling the complexity of the problem. However, for Uniform Decision Tree, i.e. Decision Tree with uniform weights, the story is more subtle. The greedy algorithm's O(log n) approximation ratio was the best known, but the largest approximation ratio known to be NP-hard is 4 – ε. We prove that the greedy algorithm gives a approximation for Uniform Decision Tree, where COPT is the cost of the optimal tree and show this is best possible for the greedy algorithm. As a corollary, we resolve a conjecture of Kosaraju, Przytycka, and Borgstrom [20]. Our results also hold for instances of DecisioN Tree whose weights are not too far from uniform. Leveraging this result, for all α ϵ (0, 1), we exhibit a approximation algorithm to Uniform Decision Tree running in subexponential time . As a corollary, achieving any super-constant approximation ratio on Uniform Decision Tree is not NP-hard, assuming the Exponential Time Hypothesis. This work therefore adds approximating Uniform Decision Tree to a small list of natural problems that have subexponential time algorithms but no known polynomial time algorithms. Like the analysis of the greedy algorithm, our analysis of the subexponential time algorithm gives similar approximation guarantees even for slightly nonuniform weights. A key technical contribution of our work is showing a connection between greedy algorithms for Uniform Decision Tree and for Min Sum Set Cover.

We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining p0(adv), the zero-rate threshold of adversarial deletions, defined to be the supremum of all p for which there exists a code family with rate bounded away from 0 capable of correcting a fraction p of adversarial deletions. A recent construction of deletion-correcting codes shows that p0(adv)≥ √2 - 1, and the trivial upper bound, p0(adv)≤ 1/2, is the best known. Perhaps surprisingly, we do not know whether or not p0(adv)= 1/2. In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of pn deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction p0(obliv)equals 1. For online 0 deletions, where the channel decides whether to delete bit xibased only on knowledge of bits x1x2. . . xi, define the deterministic zerorate threshold for online deletions p0(on,d)to be the supremum of p for which there exist deterministic codes against an online channel causing pn deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove p0(adv)= 1/2 if and only if p0(on,d)= 1/2.

Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we call lifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the $t$-disjoint-repair-group property than previously known constructions. More precisely, we show that lifted multiplicity codes with length $N$ and redundancy $O(t^{0.585} \sqrt{N})$ have the property that any symbol of a codeword can be reconstructed in $t$ different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant $t < \sqrt{N}$. We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest.

In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a directed graph. For directed graphs on $n$ vertices, all preferred extensions can be enumerated in $O^*(3^{n/3})$ time and there are directed graphs with $Ω(3^{n/3})$ preferred extensions. We give faster enumeration algorithms for directed graphs with at most $0.8004\cdot n$ vertices occurring in $2$-cycles. In particular, for oriented graphs (digraphs with no 2-cycles) one of our algorithms runs in time $O(1.2321^n)$, and we show that there are oriented graphs with $Ω(3^{n/6}) > Ω(1.2009^n)$ preferred extensions. A combination of three algorithms leads to the fastest enumeration times for various proportions of the number of vertices in $2$-cycles. The most innovative one is a new 2-stage sampling algorithm, combined with a new parameterized enumeration algorithm, analyzed with a combination of the recent monotone local search technique (STOC 2016) and an extension thereof (ICALP 2017).

In the random deletion channel, each bit is deleted independently with probability p. For the random deletion channel, the existence of codes of rate (1 - p)/9, and thus bounded away from 0 for any p0(1- p) for an absolute constant c0> 0.

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate 1 - H(p) - epsilon is (p,O(1/epsilon))-list-decodable with high probability. In this work, we show that such codes are (p, H(p)/epsilon + 2)-list-decodable with high probability, for any p in (0, 1/2) and epsilon > 0. In addition to improving the constant in known list-size bounds, our argument - which is quite simple - works simultaneously for all values of p, while previous works obtaining L = O(1/epsilon) patched together different arguments to cover different parameter regimes. Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear binary codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain a tight lower bound of 1/epsilon on the list size of uniformly random binary codes; this implies that random linear binary codes are in fact more list-decodable than uniformly random binary codes, in the sense that the list sizes are strictly smaller. To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear binary codes and (b) to prove a similar result for random linear rank-metric codes.

We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining p0(adv), the zero-rate threshold of adversarial deletions, defined to be the supremum of all p for which there exists a code family with rate bounded away from 0 capable of correcting a fraction p of adversarial deletions. A recent construction of deletion-correcting codes [3] shows that , and the trivial upper bound, p0(adv) ≤ ½, is the best known. Perhaps surprisingly, we do not know whether or not p0(adv) = 1/2. In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of pn deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction p < 1 of oblivious deletions, establishing that the associated zero-rate threshold p0(obliv) equals 1. For online deletions, where the channel decides whether to delete bit xi based only on knowledge of bits x1x2 … xi, define the deterministic zero-rate threshold for online deletions p0(on, d) to be the supremum of p for which there exist deterministic codes against an online channel causing pn deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove p0(adv) = ½ if and only if p0(adv) = ½.

In the random deletion channel, each bit is deleted independently with probability p. For the random deletion channel, the existence of codes of rate (1-p)/9, and thus bounded away from 0 for any p < 1, has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate c_0 (1-p) for an absolute constant c_0 > 0.

This work constructs codes that are efficiently decodable from a constant fraction of worst-case insertion and deletion errors in three parameter settings: (i) Binary codes with rate approaching 1; (ii) Codes with constant rate for error fraction approaching 1 over fixed alphabet size; and (iii) Constant rate codes over an alphabet of size k for error fraction approaching (k - 1)/(k + 1). When errors are constrained to deletions alone, efficiently decodable codes in each of these regimes were constructed recently. We complete the picture by constructing similar codes that are efficiently decodable in the insertion/deletion regime.