A subset $V \subseteq \mathbb{F}_2^n$ is a tile if $\mathbb{F}_2^n$ can be covered by disjoint translates of V. In other words, V is a tile if and only if there is a subset $A \subseteq \mathbb{F}_2^n$ such that $V+A = \mathbb{F}_2^n$ uniquely (i.e., $v + a = v' + a'$ implies that $v=v'$ and $a=a'$, where $v,v' \in V$ and $a,a' \in A$). In some problems in coding theory and hashing we are given a putative tile V and wish to know whether or not it is a tile. In this paper we give two computational criteria for certifying that V is not a tile. The first involves the impossibility of a bin-packing problem, and the second involves the infeasibility of a linear program. We apply both criteria to a list of putative tiles given by Gordon, Miller, and Ostapenko [IEEE Trans. Inform. Theory, 56 (2010), pp. 984–991] in the context of hashing to find close matches, to show that none of them are, in fact, tiles.

We study several classes of related scheduling problems including the carpool problem, its generalization to arbitrary inputs and the chairman assignment problem. We derive both lower and upper bounds for online algorithms solving these problems. We show that the greedy algorithm is optimal among online algorithms for the chairman assignment problem and the generalized carpool problem. We also consider geometric versions of these problems and show how the bounds adapt to these cases.

We consider scheduling policies in a client-server system where the server delivers data by broadcasting it to the users. In thesimplest model of the problem, there is a single server that holds n pages of unit size. Multiple requests for these pages arrive over time. At each time slot the server broadcasts exactly one page which satisfies all of the outstanding requests for this page at that time. We consider the problem of minimizing the average response time of requests, where the response time of the request is the duration since the request is placed until the time it is satisfied. For the offline version of this problem we give an algorithm with an approximation ratio of $O(\log^2(n) / \log \log(n))$. More generally, for any $\epsilon>0$, the algorithm achieves an average response time of $(2+\epsilon) \cdot \text{OPT} + O(\log n \cdot \log_{(1+\epsilon)} n)$, which is useful when the optimum value is large. This substantially improves the previously best known approximation factor of $O(\sqrt{n})$ for the problem [N. Bansal, M. Charikar, S. Khanna, and J. Naor, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, ACM, New York, SIAM, Philadelphia, 2005, pp. 215–221]. Our result is based on iteratively relaxing and rounding an auxiliary linear program derived from a natural linear programming relaxation of the problem.

We introduce and study the notions of pairwise and sourcewise preservers. Given an undirected N-vertex graph G = (V,E) and a set P of pairs of vertices, let G' = (V,H), H \subseteq E, be called a pairwise preserver of G with respect to P if for every pair {u,w} \in P, distG'(u,w) = distG(u,w). For a set S \subseteq V of sources, a pairwise preserver of G with respect to the set of all pairs P = (S \atop 2) of sources is called a sourcewise preserver of G with respect to S . We prove that for every undirected possibly weighted N-vertex graph G and every set P of P = O(N1/2) pairs of vertices of G, there exists a linear-size pairwise preserver of G with respect to P. Consequently, for every subset S \subseteq V of S = O(N1/4) sources, there exists a linear-size sourcewise preserver of G with respect to S. On the negative side we show that neither of the two exponents (1/2 and 1/4) can be improved even when the attention is restricted to unweighted graphs. Our lower bounds involve constructions of dense convexly independent sets of vectors with small Euclidean norms. We believe that the link between the areas of discrete geometry and spanners that we establish is of independent interest and might be useful in the study of other problems in the area of low-distortion embeddings.

For an unweighted graph $G = (V,E)$, $G' = (V,E')$ is a subgraph if $E' \subseteq E$, and $G' = (V',E',\omega)$ is a Steiner graph if $V \subseteq V'$, and for any pair of vertices $u,w \in V$, the distance between them in $G'$ (denoted $d_{G'}(u,w)$) is at least the distance between them in G (denoted $d_G(u,w)$). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) $G'$ of a graph G is a subgraph (resp., Steiner) D-preserver of G if for every pair of vertices $u,w \in V$ with $d_G(u,w) \ge D$, $d_{G'}(u,w) = d_G(u,w)$. We show that any graph (resp., digraph) has a subgraph D-preserver with at most $O(n^2/D)$ edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains $\Omega(n^2/D)$ edges. However, we show that if one allows a directed Steiner (diSteiner) D-preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner D-preserver with $O({{n^2 \cdot \log D} \over {D \cdot \log n}})$ arcs, and that this result is tight up to a constant factor. We also study D-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least D one from another. We show that there exists a D-preserving labeling scheme with labels of size $O({{n} \over {D}} \log^2 n)$, and that labels of size $\Omega({{n} \over {D}} \log D)$ are required for any D-preserving labeling scheme.

The number of ways to factor a natural number into an ordered product of integers, each factor greater than one, is called the ordered factorization of n and is denoted H(n). We show upper and lower bounds on H(n) with explicit constructions.

We consider the task of reconstructing a curve in constant dimensional space from noisy data. We consider curves of the form C = [(x,y1,•••,yc) | yj = pj(x)], where the pj's are polynomials of low degree. Given n points in (c+1)-dimensional space, such that t of these lie on some such unknown curve C while the other n-t are chosen randomly and independently, we give an efficient algorithm to recover the curve C and the identity of the good points. The success of our algorithm depends on the relation between n, t, c and the degree of the curve C, requiring t = Ω (n deg(C)) 1/(c+1). This generalizes, in the restricted setting of random errors, the work of Sudan (J. Complexity, 1997) and of Guruswami and Sudan (IEEE Trans. Inf. Th. 1999) that considered the case c=1.

Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of the direction changes at the points. We establish the NP-hardness of both this problem and its relaxation to the cycle cover problem. We then consider the issue of designing approximation algorithms for these problems and show that both problems can be approximated to within a ratio of O(log n) in polynomial time. We also consider the problem of simultaneously approximating both the angle and the length measure for a TSP tour. In studying the resulting tradeoff, we choose to focus on the sum of the two performance ratios and provide tight bounds on the sum. Finally, we consider the extremal value of the angle measure and obtain essentially tight bounds for it. In this paper we restrict our attention to the planar setting, but all our results are easily extended to higher dimensions.

This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into several channels, each at a different optical wavelength. A connection between two nodes is assigned a specific wavelength, with the constraint that no two connections sharing a link in the network can be assigned the same wavelength. This paper considers optical networks with and without switches, and different types of routing in these networks. It presents optimal or near-optimal constructions of optical networks in these cases and algorithms for routing connections, specifically permutation routing for the networks constructed here.

For an undirected graph and an optimal cyclic list of all its vertices, the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list until it completes a full cycle. The main result of this paper is a characterization of the cyclic cover time in terms of simple and easy-to-compute graph properties. Namely, for any connected graph, the cyclic cover time is $\Theta (n^2 d_{ave} (d^{ - 1} )_{ave} $), where n is the number of vertices in the graph, $d_{ave} $ is the average degree of its vertices, and $(d^{ - 1} )_{ave} $ is the average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar characterization of minimum resistance spanning trees of graphs, improved bounds on the cover time of graphs, and a simplified proof that the maximum commute time in any connected graph is at most $4n^3 /27 + o(n^3 )$.

Paul Erdös asked how dense a sequence of integers, none of which is the sum of a consecutive subsequence, can be. In other words, let $(x_{1}, \ldots ,x_m )$ be an increasing sequence of integers in $[ 1,n ]$, such that there do not exist i, j, and k, with $0 < i < j < k \leq m$ and $x_i + x_{i + 1} + \cdots + x_j = x_k $. Erdös asked if $m > n/2 + 1$ is possible. A simple argument shows that $m > 2n/3 + O(\log n)$ is impossible. Freud recently constructed a sequence with $m = 19n/36$. This note constructs a sequence with $m = 13n/24 - O(1)$ and extends the simple upper bound to show that $m > (2/3 - \epsilon )n + (\log n)$ is impossible for $\epsilon = 1/512$.

Let Dist(f,g)=Pr/sub u/[f(u)/spl ne/g(u)] denote the relative distance between functions f,g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphisms) g, of Dist(f,g). Given a function f:G/spl rarr/H we let Err(f)=Pr/sub u,/spl upsi//[f(u)+f(/spl upsi/)/spl ne/f(u+/spl upsi/)] denote the rejection probability of the Blum-Luby-Rubinfeld (1993) linearity test. Linearity testing is the study of the relationship between Err(f) and Dist(f), and in particular lower bounds on Err(f) in terms of Dist(f). We discuss when the underlying groups are G=GF(2)/sup n/ and H=GF(2). In this case, the collection of linear functions describe a Hadamard code of block length 2/sup n/ and for an arbitrary function f mapping GF(2)/sup n/ to GF(2) the distance Dist(l) measures its distance to a Hadamard code. Err(f) is a parameter that is "easy to measure" and linearity testing studies the relationship of this parameter to the distance of f. The code and corresponding test are used in the construction of efficient probabilistically checkable proofs and thence in the derivation of hardness of approximation. Improved analyses translate into better nonapproximability results. We present a description of the relationship between Err(f) and Dist(f) which is nearly complete in all its aspects, and entirely complete in some. We present functions L,U:[0,1]/spl rarr/[0,1] such that for all x /spl isin/ [0,1] we have L(x)/spl les/Err(f)/spl les/U(x) whenever Dist(f)=x, with the upper bound being tight on the whole range, and the lower bound tight on a large part of the range and close on the rest. Part of our strengthening is obtained by showing a new connection between linearity testing and Fourier analysis.

Let Dist(f,g)=Pr/sub u/ [f(u)/spl ne/g(u)] denote the relative distance between functions f,g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphisms) g, of Dist(f,g). Given a function f:G/spl rarr/H we let Err(f)=Pr/sub u/,v[f(u)+f(v)/spl ne/f(u+v)] denote the rejection probability of the BLR (Blum-Luby-Rubinfeld) linearity test. Linearity testing is the study of the relationship between Err(f) and Dist(f), and in particular the study of lower bounds on Err(f) in terms of Dist(f). The case we are interested in is when the underlying groups are G=GF(2)/sup n/ and H=GF(2). The corresponding test is used in the construction of efficient PCPs and thence in the derivation of hardness of approximation results, and, in this context, improved analyses translate into better non-approximability results. However, while several analyses of the relation of Err(f) to Dist(f) are known, none is tight. We present a description of the relationship between Err(f) and Dist(f) which is nearly complete in all its aspects, and entirely complete (i.e. tight) in some. In particular we present functions L,U:[0,1]/spl rarr/[0,1] such that for all x/spl isin/[0,1] we have L(x)

We are given a set of points p1;...;pn and a symmetric distance matrix (dij) givingthedistancebetweenpiandpj. Wewishtoconstruct atourthatminimizesPni=1`(i),where`(i)is thelatencyofpi,denedtobethedistance traveledbeforerstvisitingpi.Thisproblem isalsoknownintheliteratureasthedeliveryman problem orthetravelingrepairmanproblem. It arises in a number ofapplicationsincluding disk-head scheduling, and turnsouttobesurprisinglydierentfromthetravelingsalesman problem in character. We give exact and approximate solutions to a number of cases, including a constant-factor approximation algorithm whenever the distance matrix satisfies the triangle inequality.

The design and analysis of randomized on-line algorithms are studied.This problem is shown to be closely related to the synthesis of random wdlks on graphs with positive real costs on their edges.A theory is developed for the synthesis of such wdlks, and it is employed to design competitive on-line algorithms.

A token located at some vertex $v $ of a connected, undirected graph G on n vertices is said to be taking a “random walk” on G if, whenever it is instructed to move, it moves with equal probability to any of the neighbors of $v $. The authors consider the following problem: Suppose that two tokens are placed on G, and at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying to keep the tokens apart as long as possible. What is the expected time M before they meet? The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing. Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound. The authors use a novel potential function argument to show that in the worst case $M = ( \frac{4}{27} + o ( 1 ) )n^3 $.

Consider an arithmetic expression of length n involving only the operations (+,*) and non-negative constants. The authors prove lower bounds on the depth of any binary computation tree over the same set of operations and constants that computes such an expression. In their main result they exhibit a family of arithmetic expressions that requires computation trees of depth at least 1.5 log/sub 2/n-O(1). The authors also consider the family of arithmetic expressions defined by alternating 5-3 trees. For this family they show a tight bound of 5/(log/sub 2/15)log/sub 2/n+O(1) on the depth of any computation tree. This is the best known tight bound for any family of arithmetic expressions.>

We study the design and analysis of randomized on-line algorithms.We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.

For n>0, d>or=0, n identical to d (mod 2), let K(n, d) denote the minimal cardinality of a family V of +or-1 vectors of dimension n, such that for any +or-1 vector w of dimension n there is a v in V such that mod v-w mod>

The following three problems concerning random graphs can be solved in (log n)O(1) expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

We present a new method for accelerating matrix multiplication asymptotically. This work builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.

Problems in circuit fan-out reduction motivate the study of constructing various types of weighted trees that are optimal with respect to maximum weighted path length. An upper bound on the maximum weighted path length and an efficient construction algorithm will be presented for trees of degree at most t, along with their implications for circuit fan-out reduction.

We present a method for determining logarithms in GF(2n). Its asymptotic running time is O( exp (cn1/3log2/3n)) for a small constant c, while, by comparison, Adleman's scheme runs in time O( exp (c'n1/2log1/2n)). The ideas give a dramatic improvement even for moderate-sized fields such as GF(2127), and make (barely) possible computations in fields of size around 2400. The method is not applicable to GF(q) for a large prime q.

A method for determining logarithms in GF(2^{n})is presented. Its asymptotic running time isO(\exp (cn^{1/3} \log^{2/3} n))for a small constantc, while, by comparison, Adleman's scheme runs in timeO(\exp (c^{'}n^{1/2} \log^{1/2} n )). The ideas give a dramatic improvement even for moderate-sized fields such as GF(2^{127}), and make (barely) possible computations in fields of size around2^{400}. The method is not applicable to GF(q)for a large primeq.

We find the minimum distances of the binary(113, 57), and ternary(37, 19), (61, 31), (71, 36), and(73, 37)quadratic residue codes and the corresponding extended codes. These distances are15, 10, 11, 17, and17, respectively, for the nonextended codes and are increased by one for the respective extended codes. We also characterize the minimum weight codewords for the(113, 57)binary code and its extended counterpart.

One has a shift register of length n and a collection of designated subsets of {0, 1,···, n-1}. The problem is to devise a method for feeding a string of bits into the shift register in such an order that, for each designated subset S = {k1,···, kr}, if one keeps track of the bit patterns appearing at the corresponding positions k1, ···, krof the shift register, all 2r possible bit patterns will ultimately appear at those positions. A simple and efficient solution to this problem, derived from the connections between polynomials over finite fields and linear feedback shift registers, is presented. Applications of this solution to the problem of VLSI self-testing are discussed and illustrated.

In this paper we consider the problem of local wiring in a VLSI chip. The problem is one of interconnecting two sets of terminals, one set on each side of a wiring channel, in accordance with a given interconnection pattern, and to accomplish this while minimizing some objective function. We make the further assumption that the terminals are not rigidly positioned and can be "moved" provided that this does not change the structural intent of the circuit. Several objective functions are considered-channel width, channel length, channel area, channel perimeter, number of via holes, as well as some constrained objective functions. For some of these objective functions, we are able to find polynomial time optimal algorithms while, for others, we prove NP-completeness and suggest efficient heuristics.

Ideas which have origins in Shannon's work in information theory have arisen independently in a mathematical discipline called symbolic dynamics. These ideas have been refined and developed in recent years to a point where they yield general algorithms for constructing practical coding schemes with engineering applications. In this work we prove an extension of a coding theorem of Marcus and trace a line of mathematics from abstract topological dynamics to concrete logic network diagrams.

The number of essential multiplications required to multiply matrices of size $N \times N$ and $N \times N^{0.172} $ is bounded by $CN^2 \log ^2 N$.

A model of a general mass storage system is presented and its performance analyzed. The system is composed of a square two-dimensional grid of storage cells over which a single read/write head moves freely. The head can contain at most some fixed number b of cell contents. Algorithms for realizing an arbitrary permutation of the memory contents are presented for all ranges of b, particularly the important case $b = 1$; in each case the algorithms’ performances are explicitly characterized. Open problems, especially regarding the development of good heuristics, are then discussed.

The main results of this paper have the following flavor: Given one algorithm for multiplying matrices, there exists another, better, algorithm. A consequence of these results is that $\omega $, the exponent for matrix multiplication, is a limit point, that is, it cannot be realized by any single algorithm. We also use these results to construct a new algorithm which shows that $\omega < 2.495548$.

In this paper, we examine the problem of time-slot assignment in an SS/TDMA system operating in a packet-switched environment. We seek to assign time slots in order to minimize average packet waiting time and in order to maximize transponder utilization. We show that an assignment which achieves both objectives exists and develop a branch-and-bound algorithm to find it. In addition, we suggest several heuristics which require much less computational effort and give very close to optimal results. We derive theoretical bounds on the performance of these heuristics and perform simulation trials to show that, on average, the heuristics are very much better than their bounds suggest, and are, in fact, extremely close to optimal.

The main results of this paper have the following flavor: given one algorithm for multiplying matrices, there exists another, better, algorithm. A consequence of these results is that ω, the exponent for matrix multiplication, is a limit point, that is, cannot be realized by any single algorithm. We also use these results to construct a new algorithm which shows that ω ≪ 2.495364.

In this paper we consider an SS/TDMA system withMuplink beams,Ndownlink beams, andK, 1 \leq K \leq \min (M, N)transponders. An optimal time slot assignment algorithm for anyM, N, K,and any traffic matrix is presented, where optimality means achieving the minimal possible total duration for the given traffic matrix. The number of switching matrices generated by the algorithm is bounded above byN^{2} - N + 1forK = M = NandMN + K + 1otherwise. Extensive simulation results on randomly generated matrices are carried out, showing that the average number of switching matrices generated is substantially lower than the bounds.

In this paper two recent models of basic operations in magnetic bubble memories are discussed. The accessing of an item and the generation of arbitrary permutations in these models are studied. It is shown that the two methods of accessing an item as described in this paper for the two models are optimal in terms of the number of operations. For each model, lower bounds for the number of operations needed to generate arbitrary permutations are derived for both the worst case and the average case. Consequently, the methods proposed in this paper for both models are shown to be optimal as far as the order of magnitude of the number of operations is concerned. The results obtained in this paper may be helpful for deciding upon the relative merits of these two models.

This paper deals with a combinatorial minimization problem arising from studies on multimodule memory organizations. Instead of searching for an optimum solution, a particular solution is proposed and it is demonstrated that it is close to optimum. Lower bounds for the objective functions are obtained and compared with the corresponding values of the particular solution. The maximum percentage deviation of this solution from optimum is also established.