Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCommunication Lower Bounds for Nested Bilinear Algorithms
153
0
0.0
(
0
)
Added by
Caleb Ju
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We develop lower bounds on communication in the memory hierarchy or between processors for nested bilinear algorithms, such as Strassens algorithm for matrix multiplication. We build on a previous framework that establishes communication lower bounds by use of the rank expansion, or the minimum rank of any fixed size subset of columns of a matrix, for each of the three matrices encoding the bilinear algorithm. This framework provides lower bounds for any way of computing a bilinear algorithm, which encompasses a larger space of algorithms than by fixing a particular dependency graph. Nested bilinear algorithms include fast recursive algorithms for convolution, matrix multiplication, and contraction of tensors with symmetry. Two bilinear algorithms can be nested by taking Kronecker products between their encoding matrices. Our main result is a lower bound on the rank expansion of a matrix constructed by a Kronecker product derived from lower bounds on the rank expansion of the Kronecker products operands. To prove this bound, we map a subset of columns from a submatrix to a 2D grid, collapse them into a dense grid, expand the grid, and use the size of the expanded grid to bound the number of linearly independent columns of the submatrix. We apply the rank expansion lower bounds to obtain novel communication lower bounds for nested Toom-Cook convolution, Strassens algorithm, and fast algorithms for partially symmetric contractions.
rate research
Read More
Randomized algorithms provide solutions to two ubiquitous problems: (1) the distributed calculation of a principal component analysis or singular value decomposition of a highly rectangular matrix, and (2) the distributed calculation of a low-rank approximation (in the form of a singular value decomposition) to an arbitrary matrix. Carefully honed algorithms yield results that are uniformly superior to those of the stock, deterministic implementations in Spark (the popular platform for distributed computation); in particular, whereas the stock software will without warning return left singular vectors that are far from numerically orthonormal, a significantly burnished randomized implementation generates left singular vectors that are numerically orthonormal to nearly the machine precision.
The prior independent framework for algorithm design considers how well an algorithm that does not know the distribution of its inputs approximates the expected performance of the optimal algorithm for this distribution. This paper gives a method that is agnostic to problem setting for proving lower bounds on the prior independent approximation factor of any algorithm. The method constructs a correlated distribution over inputs that can be generated both as a distribution over i.i.d. good-for-algorithms distributions and as a distribution over i.i.d. bad-for-algorithms distributions. Prior independent algorithms are upper-bounded by the optimal algorithm for the latter distribution even when the true distribution is the former. Thus, the ratio of the expected performances of the Bayesian optimal algorithms for these two decompositions is a lower bound on the prior independent approximation ratio. The techniques of the paper connect prior independent algorithm design, Yaos Minimax Principle, and information design. We apply this framework to give new lower bounds on several canonical prior independent mechanism design problems.
Given a graph $G = (V,E)$, an $(alpha, beta)$-ruling set is a subset $S subseteq V$ such that the distance between any two vertices in $S$ is at least $alpha$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $beta$. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a $(2, beta)$-ruling set in the LOCAL model, we show the following, where $n$ denotes the number of vertices, $Delta$ the maximum degree, and $c$ is some universal constant independent of $n$ and $Delta$. $bullet$ Any deterministic algorithm requires $Omegaleft(min left{ frac{log Delta}{beta log log Delta} , log_Delta n right} right)$ rounds, for all $beta le c cdot minleft{ sqrt{frac{log Delta}{log log Delta}} , log_Delta n right}$. By optimizing $Delta$, this implies a deterministic lower bound of $Omegaleft(sqrt{frac{log n}{beta log log n}}right)$ for all $beta le c sqrt[3]{frac{log n}{log log n}}$. $bullet$ Any randomized algorithm requires $Omegaleft(min left{ frac{log Delta}{beta log log Delta} , log_Delta log n right} right)$ rounds, for all $beta le c cdot minleft{ sqrt{frac{log Delta}{log log Delta}} , log_Delta log n right}$. By optimizing $Delta$, this implies a randomized lower bound of $Omegaleft(sqrt{frac{log log n}{beta log log log n}}right)$ for all $beta le c sqrt[3]{frac{log log n}{log log log n}}$. For $beta > 1$, this improves on the previously best lower bound of $Omega(log^* n)$ rounds that follows from the 30-year-old bounds of Linial [FOCS87] and Naor [J.Disc.Math.91]. For $beta = 1$, i.e., for the problem of computing a maximal independent set, our results improve on the previously best lower bound of $Omega(log^* n)$ on trees, as our bounds already hold on trees.
In this paper, we study lower bounds for randomized solutions to the maximal independent set (MIS) and connected dominating set (CDS) problems in the dual graph model of radio networks---a generalization of the standard graph-based model that now includes unreliable links controlled by an adversary. We begin by proving that a natural geographic constraint on the network topology is required to solve these problems efficiently (i.e., in time polylogarthmic in the network size). We then prove the importance of the assumption that nodes are provided advance knowledge of their reliable neighbors (i.e, neighbors connected by reliable links). Combined, these results answer an open question by proving that the efficient MIS and CDS algorithms from [Censor-Hillel, PODC 2011] are optimal with respect to their dual graph model assumptions. They also provide insight into what properties of an unreliable network enable efficient local computation.
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs. Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed. Finally, it is shown that graph constructions for CONGEST lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
