This paper focuses on the study of the minimum possible alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified set of erasure or error patterns, naturally represented by a hypergraph. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size of codes in this generalized setting and the combinatorial properties of the hypergraph that represents the pre-specified collection of erasure or error patterns. We also establish connections between error and erasure correcting codes in our generalized setting. Finally, we consider a variation of the problem that allows a small probability of decoding error and relate it to an approximate version of hypergraph coloring.

Group testing is one of the fundamental problems in coding theory and combinatorics in which one is to identify a subset of contaminated items from a given ground set. There has been renewed interest in group testing recently due to its applications in diagnostic virology, including pool testing for the novel coronavirus. The majority of existing works on group testing focus on the uniform setting in which any subset of size d from a ground set V of size n is potentially contaminated.In this work, we consider a generalized version of group testing with an arbitrary set-system of potentially contaminated sets. The generalized problem is characterized by a hypergraph H = (V, E), where V represents the ground set and edges e ∈ E represent potentially contaminated sets. The problem of generalized group testing is motivated by practical settings in which not all subsets of a given size d may be potentially contaminated, rather, due to social dynamics, geographical limitations, or other considerations, there exist subsets that can be readily ruled out. For example, in the context of pool testing, the edge set E may consist of families, work teams, or students in a classroom, i.e., subsets likely to be mutually contaminated. The goal in studying the generalized setting is to leverage the additional knowledge characterized by H = (V, E) to reduce the number of tests.The paper considers both adaptive and non-adaptive group testing and makes the following contributions. First, for the non-adaptive setting, we show that finding an optimal solution for the generalized version of group testing is NP-hard. For this setting, we present a solution that requires O(d log |E|) tests, where d is the maximum size of a set e ∈ E. Our solutions generalize those given for the traditional setting and are shown to be of order-optimal size O(log |E|) for hypergraphs with edges that have “large” symmetric differences. For the adaptive setting, when edges in E are of size exactly d, we present a solution of size O(log |E| + d log2d) that comes close to the lower bound of $\Omega (\log |E| + d)$

We study the relation betweenlatencyandalphabet sizein the context of Multicast Network Coding. Given a graph$G = (V, E)$representing a communication network, a subset$S \subseteq V$of sources, each of which initially holds a set of information messages, and a set$T \subseteq V$of terminals; we consider the problem in which one wishes to design a communication scheme that eventually allows all terminals to obtain all the messages held by the sources. In this study we assume that communication is performed in rounds, where in each round each network node may transmit a single (possibly encoded) information packet on any of its outgoing edges. The objective is to minimize the communication latency, i.e., number of communication rounds needed until all terminals have all the messages of the source nodes. For sufficiently large alphabet sizes (i.e., large block length, packet sizes), it is known that traditional linear multicast network coding techniques (such as random linear network coding) minimize latency. In this work we seek to study the task of minimizing latency in the setting of limited alphabet sizes (i.e., finite block length), and alternatively, the task of minimizing the alphabet size in the setting of bounded latency. We focus on the establishing the computation complexity of the problem and present several intractability results. In particular, through reductive arguments, we prove that it is NP-hard to (i) approximate (and in particular to determine) the minimum alphabet size given a latency constraint; (ii) approximate (and in particular to determine) the minimum latency of communication schemes in the setting of limited alphabet sizes.

This paper focuses on error-correcting codes that can handle a predefined set of specific error patterns. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size for this generalized setting and the combinatorial properties of a hypergraph that represents the prespecified collection of error patterns. We also show a connection between error and erasure correcting codes in this specialized setting. This allows us to establish bounds on the minimum alphabet size and show an advantage of non-linear codes over linear codes in a generalized setting. We also consider a variation of the problem which allows a small probability of decoding error and relate it to an approximate version of the hypergraph coloring problem.

A Maximum Distance Separable code over an alphabet F is defined via an encoding function C : Fk→ Fnthat allows to retrieve a message m ∈ Fkfrom the codeword C(m) even after erasing any n - k of its symbols. The minimum possible alphabet size of general (non-linear) MDS codes for given parameters n and k is unknown and forms one of the central open problems in coding theory. The paper initiates the study of the alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified subset of all possible erasure patterns, naturally represented by an n-vertex k-uniform hypergraph. We relate the minimum possible alphabet size of such codes to the strong chromatic number of the hypergraph and analyze the tightness of the obtained bounds for both the linear and non-linear settings. We further consider variations of the problem which allow a small probability of decoding error.

In this paper, we consider the edit distance with block moves, block copies and block deletions, which is shown to be NP-hard, and employ a simple left-to-right greedy sliding window algorithm that achieves a constant factor approximation ratio of 5. This is an improvement on the constant approximation of 12 presented by Ergun and Sahinalp (Ergün, F., Muthukrishnan, S., and Sahinalp, S. C. Comparing sequences with segment rearrangements. FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science), and is achieved by a proof that introduces two non-trivial kinds of substrings for different purposes, so recursive and non-recursive operations can be treated at the same time.

We consider the coded cooperative data exchange problem for general graphs, both undirected and directed. In this problem, given a graph G = (V, E) representing clients in a broadcast network, each of which initially hold a (not necessarily disjoint) set of information packets; one wishes to design a communication scheme in which eventually all clients will hold all the packets of the network. Communication is performed in rounds, where in each round a single client broadcasts a single (possibly encoded) information packet to its neighbors in G. The objective is to design a broadcast scheme that satisfies all clients with the minimum number of broadcast rounds. The coded cooperative data exchange problem has seen significant research over the last few years; mostly when the graph G is the complete broadcast graph in which each client is adjacent to all other clients in the network, but also on general topologies, both in the fractional and integral setting. In this paper, we focus on the integral setting in general topologies G, both undirected and directed. For undirected graphs, we tie the coded cooperative data exchange problem on G to variants of the dominating set problem and in such show that solving the problem exactly or even approximately within a multiplicative factor of log |V| is intractable (i.e., NP-hard). We then turn to study efficient data exchange schemes for undirected topologies yielding a number of communication rounds comparable with our intractability result. Last, we tie the coded cooperative data exchange problem for directed topologies to the directed Steiner tree problem, yielding efficient data exchange approximation schemes. Our communication schemes do not involve encoding, and in such yield bounds on the coding advantage in the setting at hand.

We consider the coded cooperative data exchange problem for general graphs. In this problem, given a graph G = (V, E) representing clients in a broadcast network, each of which initially hold a (not necessarily disjoint) set of information packets; one wishes to design a communication scheme in which eventually all clients will hold all the packets of the network. Communication is performed in rounds, where in each round a single client broadcasts a single (possibly encoded) information packet to its neighbors in G. The objective is to design a broadcast scheme that satisfies all clients with the minimum number of broadcast rounds. The coded cooperative data exchange problem has seen significant research over the last few years; mostly when the graph G is the complete broadcast graph in which each client is adjacent to all other clients in the network, but also on general topologies, both in the fractional and integral setting. In this work we focus on the integral setting in general undirected topologies G. We tie the data exchange problem on G to certain well studied combinatorial properties of G and in such show that solving the problem exactly or even approximately within a multiplicative factor of log |V| is intractable (i.e., NP-Hard). We then turn to study efficient data exchange schemes yielding a number of communication rounds comparable to our intractability result. Our communication schemes do not involve encoding, and in such yield bounds on the coding advantage in the setting at hand.

In this paper we propose a P2P live streaming topology, prove its optimality under common constraints, and match the analytical research with results from a running commercial network. We assume two types of nodes: viewers that consume the entire media, and amplifiers which are non-viewing nodes utilized for their upstream bandwidth. We analytically derive the minimum needed server upload capacity, for any topology, under the following assumptions: the amount of amplifiers and buffer time are limited, dynamics are low, and the total bandwidth required by the viewers exceeds the total upstream bandwidth of all peers. Then, we present a two-level topology and prove that it achieves the minimum possible server upload, up to a small fraction. Finally, the assumptions and derivation are supported by performing several experiments on RayV's real-world commercial system, with varying network parameters. Namely, we show our predictions are valid while varying the viewers to amplifiers ratio, the stream bit-rate, and the country of the peers. These results not only verify the analytical static predictions, but also evaluate the dynamic costs during the `flash crowd', the initial time when peers are joining the system.

In this paper we present a P2P live streaming topology which performs near the optimum under common constraints. We assume two types of nodes: viewers that consume the entire media, and amplifiers which are non-viewing nodes utilized for their upstream bandwidth. We analytically derive the minimum needed server upload, for any topology, under the constraint of limited total peer upload. Under this constraint, we prove that a 2-level topology for the amplifiers is optimal. Then, by running experiments on RayV's real-world commercial system, we demonstrate that in such a 2-level system the server upload is indeed near the minimum.

Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets) is motivated by applications in a variety of areas ranging from biology to the study of the World Wide Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph [Formula: see text]. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter [Formula: see text] and query access to a graph [Formula: see text], outputs an estimate [Formula: see text] such that with high constant probability, [Formula: see text], where [Formula: see text] denotes the number of stars of size [Formula: see text] in the graph. The expected query complexity and running time of the algorithm are [Formula: see text]. We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in [Formula: see text] and the dependence on [Formula: see text]. Our work extends the work of Feige [SIAM J. Comput., 35 (2006), pp. 964–984] and Goldreich and Ron [Random Structures Algorithms, 32 (2008), pp. 473–493] on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-3 paths in sublinear-time.

Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph G. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter 0 < ε < 1 and query access to a graph G, outputs an estimate such that with high constant probability, , where vs(G) denotes the number of stars of size s + 1 in the graph. The expected query complexity and running time of the algorithm are . We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in n and the dependence on ε. Our work extends the work of Feige (SIAM Journal on Computing, 2006) and Goldreich and Ron (Random Structures and Algorithms, 2008) on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-3-paths in sublinear time.

When designing a mechanism there are several desirable properties tomaintain such as incentive compatibility (IC), individual rationality (IR), and budget balance (BB). It is well known [15] that it is impossible for a mechanism to maximize social welfare whilst also being IR, IC, and BB. There have been several attempts to circumvent [15] by trading welfare for BB, e.g.,in domains such as double-sided auctions [13], distributed markets [3] and supply chain problems [2, 4].

The goal of this work is to model the peering arrangements between autonomous systems (ASes). Most existing models of the AS-graph assume an undirected graph. However, peering arrangements are mostly asymmetric customer-provider arrangements, which are better modeled as directed edges. Furthermore, it is well known that the AS-graph, and in particular its clustering structure, is influenced by geography. We introduce a new model that describes the AS-graph as a directed graph, with an edge going from the customer to the provider, but also models symmetric peer-to-peer arrangements. In addition, our model takes geography into account. We are able to mathematically analyze its power-law exponent and number of leaves. Beyond the analysis, we have implemented our model as a synthetic network generator called GDNG. Experimentation with GDNG shows that the networks it produces are more realistic than those generated by other network generators, in terms of its power-law exponent, fractions of customer-provider and symmetric peering arrangements, and the size of its dense core. We believe that our model is the first to manifest realistic regional dense cores that have a clear geographic flavor. Our synthetic networks also exhibit path inflation effects that are similar to those observed in the real AS graph.