More Like this

1. On the rank of a random binary matrix

   https://doi.org/10.1137/1.9781611975482.58  

   Cooper, Colin; Frieze, Alan; Pegden, Wesley (January 2019, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the rank of a random n × m matrix An, m; k with entries from GF(2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all (nk) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix An, m; k forms the vertex-edge incidence matrix of a k-uniform random hypergraph H. The rank of An, m; k can be expressed as follows. Let |C2| be the number of vertices of the 2-core of H, and | E (C2)| the number of edges. Let m* be the value of m for which |C2| = |E(C2)|. Then w.h.p. for m < m* the rank of An, m; k is asymptotic to m, and for m ≥ m* the rank is asymptotic to m – |E(C2)| + |C2|. In addition, assign i.i.d. U[0, 1] weights Xi, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X(S) = ∑j∊S Xj. Define a basis as a set of n – 1 (k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1.202. 

   more » « less
2. Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem

   Ahmed, R.; Efrat, A.; Kobourov, S.; Krieger, S.; Spence, R. (January 2019, ArXiv.org)

   Given a graph G = (V, E) and a subset T ⊆ V of terminals, a Steiner tree of G is a tree that spans T. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of G. Vertex-weighted problems have applications in network design and routing, where there are different costs for installing or maintaining facilities at different vertices. We study a natural generalization of the VST problem motivated by multi-level graph construction, the vertex-weighted grade-of-service Steiner tree problem (V-GSST), which can be stated as follows: given a graph G and terminals T, where each terminal v ∈ T requires a facility of a minimum grade of service R(v) ∈ {1, 2, . . . `}, compute a Steiner tree G0 by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in G 0 with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on `, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a (2 ln |T|)-approximation, where T is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service. Finally, we show that this problem is a special case of the directed Steiner tree problem and provide an integer linear programming (ILP) formulation for the V-GSST problem. 

   more » « less
3. Parallel Algorithms through Approximation: b-Edge cover

   https://doi.org/10.1109/IPDPS.2018.00013  

   Khan, Arif; Pothen, Alex; Ferdous, SM (January 2018, 2018 IEEE International Parallel and Distributed Processing Symposium)

   We describe a paradigm for designing parallel algorithms via approximation, and illustrate it on the b-edgecover problem. A b-edgecover of minimum weight in a graph is a subset $$C$$ of its edges such that at least a specified number $b(v)$ of edges in $$C$$ is incident on each vertex $$v$$, and the sum of the edge weights in $$C$$ is minimum. The Greedy algorithm and a variant, the LSE algorithm, provide $3/2$-approximation guarantees in the worst-case for this problem, but these algorithms have limited parallelism. Hence we design two new $$2$$-approximation algorithms with greater concurrency. The MCE algorithm reduces the computation of a b-edgecover to that of finding a b'-matching, by exploiting the relationship between these subgraphs in an approximation context. The LSE-NW is derived from the LSEalgorithm using static edge weights rather than dynamically computing effective edge weights. This relaxation gives LSE a worse approximation guarantee but makes it more amenable to parallelization. We prove that both the MCE and LSE-NW algorithms compute the same b-edgecover with at most twice the weight of the minimum weight edge cover. In practice, the $$2$$-approximation and $3/2$-approximation algorithms compute edge covers of weight within $$10\%$$ the optimal. We implement three of the approximation algorithms, MCE, LSE, and LSE-NW on shared memory multi-core machines, including an Intel Xeon and an IBM Power8 machine with 8 TB memory. The MCE algorithm is the fastest of these by an order of magnitude or more. It computes an edge cover in a graph with billions of edges in $20$ seconds using two hundred threads on the IBM Power8. We also show that the parallel depth and work can be bounded for the Suitor and b-Suitor algorithms when edge weights are random. 

   more » « less
4. Decoding Reed–Muller Codes Using Minimum-Weight Parity Checks

   Santi, Elia; Haeger, Christian; Pfister, Henry D. (January 2018, IEEE International Symposium on Information Theory)

   Reed–Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly- symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs. 

   more » « less
5. Point-hyperplane Incidence Geometry and the Log-rank Conjecture

   https://doi.org/10.1145/3543684  

   Singer, Noah; Sudan, Madhu (June 2022, ACM Transactions on Computation Theory)

   We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in ℝ d that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., 2 –polylog( d ) ) fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the point-hyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank- d matrix containing at most O (1) distinct entries in each column contains a submatrix of fractional size 2 –polylog( d ) , in which each column is constant. We prove that our conjecture is equivalent to the log-rank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel k -partitions to bounds for parallel ( k -1)-partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density Ω (ε 2 d / d ) in any d -dimensional configuration with incidence density ε, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upper-bound construction of Apfelbaum and Sharir [ 2 ], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is Ω (1/√ d ). Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density Ω (1) and complete bipartite subgraph density 2 -Ω (√ d ) , and pose several questions for this special case in the alternative language of extremal set combinatorics. Our framework and results may help shed light on the difficulty of improving Lovett’s Õ(√ rank( f )) bound [ 20 ] for the log-rank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel 3-partitioned configurations which beat our generic bounds for unstructured configurations. 

   more » « less