Explore the vast range of titles available.

Let ${\\mathcal{A}}_n$ be the set of all $n \\times n$ binary matrices in which the number of $1$'s in each row and column is at most $n/2$. We show that $|{\\mathcal{A}}_n| = 2^{n^2 - \\rho n + \\delta \\sqrt{n}} \\cdot n^{O(1)}$, for a constant $\\rho \\approx 1.42515$, and $\\delta = \\delta(n) \\approx 1.46016$ for even $n$ and $0$ otherwise. [PUBLICATION ABSTRACT]

A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-time algorithms are provided for approximating the problem of finding a feedback vertex set of G with smallest weight. When the weights of all vertices in G are equal, the performance ratio attained by these algorithms is 4-(2/n). This improves a previous algorithm which achieved an approximation factor of $O(\\sqrt{\\log n})$ for this case. For general vertex weights, the performance ratio becomes $\\min\\{2\\Delta^2, 4 \\log_2 n\\}$ where $\\Delta$ denotes the maximum degree in G. For the special case of planar graphs this ratio is reduced to 10. An interesting special case of weighted graphs where a performance ratio of 4-(2/n) is achieved is the one where a prescribed subset of the vertices, so-called blackout vertices, is not allowed to participate in any feedback vertex set. It is shown how these algorithms can improve the search performance for constraint satisfaction problems. An application in the area of Bayesian inference of graphs with blackout vertices is also presented.

Let G be a t-uniform s-regular linear hypergraph with r vertices. It is shown that the number of independent sets $\\IS(\\hgraph)$ in $\\hgraph$ satisfies \\[ \\log_2 \\IS(\\hgraph) \\le \\frac{r}{t} \\left( 1 + O \\biggl( \\frac{\\log^2(ts)}{s} \\biggr) \\right) . \\] This leads to an improvement of a previous bound by Alon obtained for t = 2 (i.e., for regular ordinary graphs). It is also shown that for the Hamming graph $\\Hamming(n,q)$ (with vertices consisting of all n-tuples over an alphabet of size q and edges connecting pairs of vertices with Hamming distance $1$), \\[ \\frac{\\log_2 \\IS(\\Hamming(n,q))}{q^n} = \\frac{1}{q} + O \\biggl(\\frac{\\log^2 (q n)}{q n} \\biggr). \\] The latter result is then applied to show that the Shannon capacity of the n-dimensional $(d,\\infty)$-runlength-limited (RLL) constraint converges to 1/(d+1) as n goes to infinity.

Techniques are presented for computing upper and lower bounds on the number of errors that can be corrected by list decoders for general block codes and, specifically, for Reed--Solomon (RS) codes. The list decoder of Guruswami and Sudan implies such a lower bound (referred to here as the GS bound) for RS codes. It is shown that this lower bound, given by means of the code's length, the minimum Hamming distance, and the maximal allowed list size, in fact applies to all block codes. Ranges of code parameters are identified where the GS bound is tight for worst-case RS codes, in which case the list decoder of Guruswami and Sudan provably corrects the largest possible number of errors. On the other hand, ranges of parameters are provided for which the GS lower bound can be strictly improved. In some cases the improvement applies to all block codes with a given minimum Hamming distance, while in others it applies only to RS codes.

The following file distribution problem is considered: Given a network of processors represented by an undirected graph $G = (V, E)$ and a file size $k$, an arbitrary file ${\\bf w}$ of $k$ bits is to be distributed among all nodes of $G$. To this end, each node is assigned a memory device such that by accessing the memory of its own and of its adjacent nodes, the node can reconstruct the contents of ${\\bf w}$. The objective is to minimize the total size of memory in the network. This paper presents a file distribution scheme which realizes this objective for $k \\gg \\log \\Delta_{G}$, where $\\Delta_{G}$ stands for the maximum degree in $G$: For this range of $k$, the total memory size required by the suggested scheme approaches an integer programming lower bound on that size. The scheme is also constructive in the sense that given $G$ and $k$, the memory size at each node in $G$, as well as the mapping of any file ${\\bf w}$ into the node memory devices, can be computed in time complexity which is polynomial in $k$ and $|V|$. Furthermore, each node can reconstruct the contents of such a file ${\\bf w}$ in $O(k^{2})$ bit operations. Finally, it is shown that the requirement of $k$ being much larger than $\\log \\Delta_{G}$ is necessary in order to have total memory size close to the integer programming lower bound.

Let \\([q\\rangle\\) denote the integer set \\(\\{0,1,\\ldots,...,q-1\\}\\) and let \\(\\mathbb{B}=\\{0,1\\}\\). The problem of implementing functions \\([q\\rangle\\rightarrow\\mathbb{B}\\) on content-addressable memories (CAMs) is considered. CAMs can be classified by the input alphabet and the state alphabet of their cells; for example, in binary CAMs, those alphabets are both \\(\\mathbb{B}\\), while in a ternary CAM (TCAM), both alphabets are endowed with a \"don't care\" symbol. This work is motivated by recent proposals for using CAMs for fast inference on decision trees. In such learning models, the tree nodes carry out integer comparisons, such as testing equality (\\(x=t\\)?) or inequality (\\(x\\le t\\)?), where \\(x \\in [q\\rangle\\) is an input to the node and \\(t \\in [q\\rangle\\) is a node parameter. A CAM implementation of such comparisons includes mapping (i.e., encoding) \\(t\\) into internal states of some number \\(n\\) of cells and mapping \\(x\\) into inputs to these cells, with the goal of minimizing \\(n\\). Such mappings are presented for various comparison families, as well as for the set of all functions \\([q\\rangle\\rightarrow\\mathbb{B}\\), under several scenarios of input and state alphabets of the CAM cells. All those mappings are shown to be optimal in that they attain the smallest possible \\(n\\) for any given \\(q\\).

Error-correcting codes over the real field are studied which can locate outlying computational errors when performing approximate computing of real vector--matrix multiplication on resistive crossbars. Prior work has concentrated on locating a single outlying error and, in this work, several classes of codes are presented which can handle multiple errors. It is first shown that one of the known constructions, which is based on spherical codes, can in fact handle multiple outlying errors. A second family of codes is then presented with \\(\\zeroone\\)~parity-check matrices which are sparse and disjunct; such matrices have been used in other applications as well, especially in combinatorial group testing. In addition, a certain class of the codes that are obtained through this construction is shown to be efficiently decodable. As part of the study of sparse disjunct matrices, this work also contains improved lower and upper bounds on the maximum Hamming weight of the rows in such matrices.

A function $f:\\{ 0,1\\} ^n \\to \\{ 0,1\\} $ is called $t$-sparse if the $n$-variable polynomial representation of $f$ over $GF(2)$ contains at most $t$ monomials. Such functions are uniquely determined by their values at the so-called critical set of all binary $n$-tuples of Hamming weight $ \\geqq n - \\lfloor \\log _2 t \\rfloor - 1$. An algorithm is presented for interpolating any $t$-sparse function $f$, given the values of $f$ at the critical set. The time complexity of the proposed algorithm is proportional to $n$, $t$, and the size of the critical set. Then, the more general problem of approximating 1-sparse functions is considered, in which case the approximating function may differ from $f$ at a fraction $\\varepsilon $ of the space $\\{ 0,1\\} ^n $. It is shown that $O(({t / \\varepsilon }) \\cdot n)$ evaluation points are sufficient for the (deterministic) $\\varepsilon $-approximation of any $t$-sparse function, and that an order $(t / \\varepsilon )^{\\alpha (t,\\varepsilon )} \\cdot \\log n$ points are necessary for this purpose, where $\\alpha (t,\\varepsilon ) \\geqq 0.694$ for a large range of $t$ and $\\varepsilon $. Similar bounds hold for the $t$-term DNF case as well. Finally, a probabilistic polynomial-time algorithm is presented for the $\\varepsilon $-approximation of any $t$-sparse function.

Motivated by coding applications,two enumeration problems are considered: the number of distinct divisors of a degree-m polynomial over F = GF(q), and the number of ways a polynomial can be written as a product of two polynomials of degree at most n over F. For the two problems, bounds are obtained on the maximum number of factorizations, and a characterization is presented for polynomials attaining that maximum. Finally, expressions are presented for the average and the variance of the number of factorizations, for any given m (respectively, n).

An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters [n,k,d] and the list size L. L-MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed-Solomon (GRS) codes.