Since the advent of fast computers, much attention has been paid to practical factoring algorithms. Several of these algorithms set out to find two squares x^2, y^2 that are congruent modulo the number n we wish to factor, and are non-trivial in the sense that x is not equivalent to +/- y mod n. In 1994, this prompted Pomerance to ask the following question. Let a_1, a_2, ... be random integers, chosen independently and uniformly from a set {1, ... x}. Let N be the smallest index such that {a_1, ... , a_N} contains a subsequence, the product of whose elements is a perfect square. What can you say about this random number N? In particular, give bounds N_0 and N_1 such that P(N_0 <= N <= N_1)-> 1 as x -> infty. Pomerance also gave bounds N_0 and N_1 with log N_0 ~ log N_1. In 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds of Pomerance, bringing them within a constant of each other, and conjectured that their upper bound is sharp. In a recent paper, Paul Balister, Rob Morris and I have proved this conjecture. In the talk I shall review some related results and sketch some of the ideas used in our proof.

A hypergraph is $k$-irregular if there is no set of $k$ vertices all of which have the same degree. We asymptotically determine the probability that a random uniform hypergraph is $k$-irregular.

We prove that in a random $3$-uniform or $4$-uniform hypergraph of order $n$ the probability that some two vertices have the same degree tends to one as $n\to\infty$.

A coloring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each color; the polychromatic number is the maximum number of colors in such a coloring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric hypergraphs, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree); our goal here is to broaden the study beyond geometric settings. We obtain algorithms yielding near-tight bounds for three families of hypergraphs: bounded hyperedge size, paths in trees, and bounded Vapnik--Chervonenkis (VC)-dimension. This reveals that discrepancy theory and iterated linear program relaxation are useful for cover-decomposition. Finally, we discuss the generalization of cover-decomposition to sensor cover.

Let $B_i^{(k)}$ be the $k$-uniform hypergraph whose vertex set is of the form $S\cup T$, where $|S|=i$, $|T|=k-1$, and $S\cap T=\emptyset$, and whose edges are the $k$-subsets of $S\cup T$ that contain either $S$ or $T$. We derive upper and lower bounds for the Turán density of $B_i^{(k)}$ that are close to each other as $k\to\infty$. We also obtain asymptotically tight bounds for the Turán density of several other infinite families of hypergraphs. The constructions that imply the lower bounds are derived from elementary number theory by probabilistic arguments, and the upper bounds follow from some results of de Caen, Sidorenko, and Keevash.

The problem of designing policies for in-network function computation with minimum energy consumption subject to a latency constraint is considered. The scaling behavior of the energy consumption under the latency constraint is analyzed for random networks, where the nodes are uniformly placed in growing regions and the number of nodes goes to infinity. The special case of sum function computation and its delivery to a designated root node is considered first. A policy which achieves order-optimal average energy consumption in random networks subject to the given latency constraint is proposed. The scaling behavior of the optimal energy consumption depends on the path-loss exponent of wireless transmissions and the dimension of the Euclidean region where the nodes are placed. The policy is then extended to computation of a general class of functions which decompose according to maximal cliques of a proximity graph such as the k-nearest neighbor graph or the geometric random graph. The modified policy achieves order-optimal energy consumption albeit for a limited range of latency constraints.

Consider words over an alphabet with n letters. Fisher [Amer. Math. Monthly, 96 (1989), pp. 610–614] calculated the number of distinct words of length $\ell$ assuming certain pairs of letters commute. In this paper we are interested in a more general setting where the pairs of letters that commute at a certain position of a word depend on the initial segment of the word. In particular, we show that if for each word at each position any letter fails to commute with at most a constant number of other letters, then the number of distinct words of length $\ell$ is at most $C^{n+\ell}$ for some constant C. We use this result to obtain a lower bound on the number of diagonal flips required in the worst case to transform one n-vertex labeled triangulated planar graph into some other one. This has previously been proved in [D. D. Sleator, R. E. Tarjan, and W. P. Thurston, SIAM J. Discrete Math., 5 (1992), pp. 428–450] by different methods.

Deriving the critical density (which is equivalent to deriving the critical radius or power) to achieve coverage and/or connectivity for random deployments is a fundamental problem in the area of wireless networks. The probabilistic conditions normally derived, however, have limited appeal among practitioners because they areoften asymptotic, i.e., they only make high probability guarantees in the limit of large system sizes. Such conditions are not very useful in practice since deployment regions are always finite. Another major limitation of most existing work on coverage and connectivity is their focus on thick deployment regions (such as a square or a disk). There is no existing work (including traditional percolation theory) that derives critical densities for thin strips (or annuli).

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.

In this paper, various fast transmission strategies for sending information from a source s over a large distance to a target t in ad hoc wireless networks where the nodes are distributed as a Poisson process of intensity is presented. The existence of an infinite component, i.e., percolation, is not sufficient for our problem since the proportion of vertices in the infinite component may be very low. To achieve connectivity the power must increase with the number of vertices, since there is some positive chance that a vertex is isolated. Result shows that with directional transmissions, even with very low power there exist points at arbitrarily large distance that can communicate.

Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We prove an integrality gap of 2-o(1) for three families of linear relaxations for vertex cover, and our methods seem relevant to other problems as well.

The paper gives a nearly logarithmic lower bound on the randomized competitive ratio for a Metrical Task Systems model (A. Borodin et al., 1992). This implies a similar lower bound for the extensively studied K-server problem. Our proof is based on proving a Ramsey-type theorem for metric spaces. In particular, we prove that in every metric space there exists a large subspace which is approximately a "hierarchically well-separated tree" (HST) (Y. Bartal, 1996). This theorem may be of independent interest.

Given a pair of nonidentical complex objects, defining (and determining) how similar they are to each other is a nontrivial problem. In data mining applications, one frequently needs to determine the similarity between two time series. We analyze a model of timeseries similarity that allows outliers, different scaling functions, and variable sampling rates. We present several deterministic and randomized algorithms for computing this notion of similarity. The algorithms are based on nontrivial tools and methods from computational geometry. In particular, we use properties of families of well-separated geometric sets. The randomized algorithm has provably good performance and also works extremely efficiently in practice. 1 Introduction Being able to measure the similarity between objects is a crucial issue in many data retrieval and data mining applications; see [10] for a general discussion on similarity queries. Typically, the task is to define a function Sim(X;Y ), where X and Y are...

The random graph order $P_{n,p}$ is defined by taking a random graph $G_{n,p}$ on vertex set $[n]$, treating an edge $ij$ with $i\prec j$ in $[n]$ as a relation $i < j$, and taking the transitive closure. A {\it post} in a partial order is an element comparable with all others. We investigate the occurrence of posts in random graph orders, showing in particular that $P_{n,p}$ almost surely has posts if $np^{-1}e^{-\pi^2/3p}\to \infty$, but almost surely does not if this quantity tends to 0. If there are many posts, the partial order decomposes as a linear sum of smaller orders, and we use this decomposition to show that many parameters of a random graph order---for instance, the height, the logarithm of the number of linear extensions, and the number of incomparable pairs---behave as normal random variables. For instance, for the height $H_{n,p}$, we prove that, for p in an appropriate range, there are functions $\alpha_H(p) =e(1+o(1))p$ and $\beta_H(p)$ such that $(H_{n,p} - \alpha_H(p)n)/\sqrt n \beta_H(p) \tod N(0,1)$.

A number of open questions are settled about the expected costs of two disjoint set Union and Find algorithms raised by Knuth and Schönhage [Theoret. Comput. Sci., 6 (1978), pp. 281–315]. This paper shows that the expected time of the Weighted Quick-Find (QFW) algorithm to perform $(n - 1)$ randomly chosen unions is $cn + o({n / {\log n}})$, where $c = 2.0847 \ldots $ . Through an observation of Tarjan and Van Leeuwen in [J. Assoc. Comput. Mach., 22 (1975), pp. 215–225] this implies linear time bounds to perform $O(n)$ unions and finds for a class of other union-find algorithms. It is also proved that the expected time of the Unweighted Quick-Find (QF) algorithm is ${{n^2 } / {8 + O(n(\log n)^2 )}}$. The expected costs of QFW and QF are analyzed when fewer than $(n - 1)$ unions are performed. Among other results, for QFW it is shown that the expected cost of $m = o(n)$ randomly chosen unions is $m(1 + o(1))$. If $m = {{\alpha n} / 2}$, where $\alpha \leqslant e^{ - 2} $, this cost is $m(1 + \epsilon (\alpha ) + o(1))$, where $\epsilon (\alpha ) \to 0$ as $\alpha \to 0$ and $\epsilon (e^{ - 2} ) \leqslant .026$. For QF, the expected cost of ${n / {2 - n^{{2 / 3}} }}(\log n)^{{2 / 3}} $ randomly chosen unions is $O(n\log n)$.

A new approach to the analysis of random probing hashing algorithms is presented. The probability-generating function in closed form for the asymptotic cost of insertion via random probing with secondary clustering is derived. For higher-order clustering, it is shown that all the moments of the probability distribution of the insertion cost exist and are asymptotically equal to the corresponding moments of the cost distribution under uniform hashing. The method in this paper also leads to simple derivations for the expected cost of insertion for random probing with secondary and higher-order clustering.

Given a set of n elements in some unknown order, parallel comparison algorithms to select the tth highest with probability $1- o(1)$ as $n \to \infty $ are considered, where each order is assumed to be equally likely. Such an algorithm is given using four rounds and $cn$ comparisons per round, and it is shown that no such algorithm exists using three rounds and $cn$ comparisons per round.

The discrete torus is the graph on $\mathbb{Z}_k^n = ( \mathbb{Z}/k\mathbb{Z} )^n $ in which $x = (x_i )_1^n $ is joined to $y = (y_i )_1^n $ if for some i there is $x_i = y_i \pm 1$ and $x_j = y_j $ for all $j \ne i$. For a set $A \subset \mathbb{Z}_k^n $ and a natural number t, let $A_{( t )} $ be the set of vertices of $\mathbb{Z}_k^n $ within distance t of A. The main aim of this paper is to give a best possible lower bound for $| A_{(t)} |$ in terms of $| A |$, for even values of k.

Suppose that we have a set X of n objects in some unknown total order $ < $. For G a graph on X, we ask, for each edge $xy$, “Is $x < y$?” On processing the information thus gained we may be able to deduce more comparisons. The information we have is then in the form of a partial order $P(G; <)$. Let $t(G)$ denote the maximum, over all linear orders $ <$ on X, of the number of pairs not related in $P(G; <)$; and let $t(n,p)$ denote the minimum of $t(G)$ over all graphs G with n vertices and $\lfloor {{{pn^2 } / 2}} \rfloor $ edges. We find upper and lower bounds for $t(n,p)$ throughout the range of $p = p(n)$.

How small can the diameter be made by adding a matching to an n-cycle? In this paper this question is answered by showing that the graph consisting of an n-cycle and a random matching has diameter about $\log _2 n$, which is very close to the best possible value. It is also shown that by adding a random matching to graphs with certain expanding properties such as expanders or Ramanujan graphs, the resulting graphs have near optimum diameters.

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs with n vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. Finally, it is used in an algorithm for solving the symmetric bottleneck travelling salesman problem with probability tending to 1, as n tends to ∞.

We show that the expected time of the Weighted Quickfind (QFW) disjoint set union and find algorithm to perform (n - 1) randomly chosen unions is cn + o(n/log n), where c = 2.0847 …. This implies, through an observation of Tarjan and Van Leeuwen, linear expected time bounds to perform O(n) unions and finds for a class of other union -find algorithms. We also prove that the expected time of the unweighted Quickfind (QF) algorithm is n2/8 + o(n(log n)2), and set the several related open questions of Knuth and Schönhage.