The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids M1 = (V, I1) and M2 = (V, I2) on a comment ground set V of n elements, and then we have to find the largest common independent set S e I1 I2 by making independence oracle queries of the form "Is S e I1?"or "Is S e I2?"for S ? V. The goal is to minimize the number of queries. Beating the existing O(n2) bound, known as the quadratic barrier, is an open problem that captures the limits of techniques from two lines of work. The first one is the classic Cunningham's algorithm [SICOMP 1986], whose O(n2)-query implementations were shown by CLS+ [FOCS 2019] and Nguyen [2019] (more generally, these algorithms take O(nr) queries where r denotes the rank which can be as big as n). The other one is the general cutting plane method of Lee, Sidford, and Wong [FOCS 2015]. The only progress towards breaking the quadratic barrier requires either approximation algorithms or a more powerful rank oracle query [CLS+ FOCS 2019]. No exact algorithm with o(n2) independence queries was known. In this work, we break the quadratic barrier with a randomized algorithm guaranteeing O(n9/5) independence queries with high probability, and a deterministic algorithm guaranteeing O(n11/6) independence queries. Our key insight is simple and fast algorithms to solve a graph reachability problem that arose in the standard augmenting path framework [Edmonds 1968]. Combining this with previous exact and approximation algorithms leads to our results. 

Minimum-weight cut (min-cut) is a basic measure of a network’s connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC’96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]) can guarantee a solution that is (1+є)-approximation at best while the exact Õ(n^0.8D^0.2 + n^0.9)-time algorithm [Ghaffari, Nowicki, Thorup, SODA’20] works only on simple networks (no weights and no parallel edges). Throughout, n and D denote the network’s number of vertices and hop-diameter, respectively. For the weighted case, the best bound was Õ(n) [Daga, Henzinger, Nanongkai, Saranurak, STOC’19]. In this paper, we provide an exact Õ(√n + D)-time algorithm for computing min-cut on weighted networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC’20] and can be of independent interest.

We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For ≥ n^1+ϵ for any constant ϵ>0, our algorithm requires O(m łog n) work and O(łog^3 n) depth and succeeds with high probability. Its work matches the best O(m łog n) runtime for sequential algorithms [MN STOC'20; GMW SOSA'21]. This improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by a O(łog^3 n) factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC'21; GMW SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.

Consider the following 2-respecting min-cut problem. Given any weighted graph G and its spanning tree T, find the minimum cut among the cuts that contain at most two edges in T. This problem is an important subroutine in Karger's celebrated randomized near-linear-time min-cut algorithm [STOC'96]. We present a new approach for this problem which can be easily implemented in many settings, leading to the following randomized min-cut algorithms for weighted graphs: (i) An O(m log(2)/log n + n log(6) n)-time sequential algorithm improving Karger's long-standing O(m log(3) n) and O(n log(6) n + m log(2) n log (n(2)/m)/log log n) bounds when the input graph is not extremely sparse or dense. Improvements over Karger's bounds were previously known only under a rather strong assumption that the input graph is simple (unweighted without parallel edges) [Henzinger, Rao, Wang, SODA'17; Ghaffari, Nowicki, Thorup, SODA'20]. For unweighted graphs (possibly with parallel edges) and using bit operations, our bound can be further improved to O(m log(1.5) n/log log n + n log(6) n). (ii) An algorithm that requires (O) over tilde (n) cut queries to compute the min-cut of a weighted graph: This answers an open problem by Rubinstein, Schramm, and Weinberg [ITCS'18], who obtained a similar bound for simple graphs. Our bound is tight up to polylogarithmic factors. (iii) A streaming algorithm that requires (O) over tilde (n) space and O(log n) passes to compute the min-cut: The only previous non-trivial exact min-cut algorithm in this setting is the 2-pass (O) over tilde (n)-space algorithm on simple graphs [Rubinstein et al., ITCS'18] (observed by Assadi, Chen, and Khanna [STOC'19]). Our approach exploits some cute structural properties so that it only needs to compute the values of (O) over tilde (n) cuts corresponding to removing (O) over tilde (n) pairs of tree edges, an operation that can be done quickly in many settings. This is in contrast to the techniques used by Karger and Lovett-Sandlund to solve 2-respecting min-cut where information about many more cuts is computed, stored in and accessed from sophisticated data-structures.

We show a deterministic simulation (or lifting) theorem for composed problems f ◦Eqn where the9 inner function (the gadget) is Equality on n bits. When f is a total function on p bits, it is easy to10 show via a rank argument that the communication complexity of f ◦Eqn is Ω(deg(f)·n). However,11 there is a surprising counter-example of a partial function f on p bits, such that any completion f012 of f has deg(f0) = Ω(p), and yet f ◦Eqn has communication complexity O(n). Nonetheless, we are13 able to show that the communication complexity of f ◦Eqn is at least D(f)·n for a complexity14 measure D(f) which is closely related to the AND-query complexity of f and is lower-bounded by15 the logarithm of the leaf complexity of f. As a corollary, we also obtain lifting theorems for the16 set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the NOR17 gadget.18 As an application, we prove a tight lower-bound for the deterministic communication complexity19 of the communication problem, where Alice and Bob are each given p-many n-bit strings, with the20 promise that either all of the strings are distinct, or all-but-one of the strings are distinct, and they21 wish to know which is the case. We show that the complexity of this problem is Θ(p·n).

We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403–435, 1999), to any gadget which satisfies a certainhitting property. We prove that inner product and gap-Hammingsatisfy this property, and as a corollary, we obtain a deterministic simulationtheorem for these gadgets, where the gadget’s input size is logarithmicin the input size of the outer function. This yields the firstdeterministic simulation theorem with a logarithmic gadget size, answeringan open question posed by Göös, Pitassi & Watson (in: Proceedingsof the 56th FOCS, 2015). Our result also implies the previous results for the indexing gadget, withbetter parameters than was previously known. Moreover, a simulationtheorem with logarithmic-sized gadget implies a quadratic separationin the deterministic communication complexity and the logarithm ofthe 1-partition number, no matter how high the 1-partition number iswith respect to the input size—something which is not achievable by previous results of Göös, Pitassi & Watson (2015).

Saks and Wigderson 27th FOGS, IEEE Computer Society, as Alamitos, CA, 1986, pp. 29-38] conjectured that R-0(f) = Omega (D(f)(0.753...)) for all Boolean functions f, here R-0 denotes the randomized complexity and D denotes 10 determinist is query CCATI p1exit;,yr. We,show t hat for the pointer function GPW(rxs) defined by Goos. Pitassi, arid Watson [in Proceedings of the 56th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077-1088] the following hold: s) s) and (b) R-1(GPW(rxs)) = Irs), cyhere R1 denotes the randomized one-sided error query complexity. These results imply that (i) R-0(GPW(s2xs)) = O(D(GPW(s2xs))2/3) t hereby refuting the; conjecture of Saks and Wigdorson, and (ii) R-1 (GPW(sxs))- O(R-0(GPW(sxs))(2/3)), thereby providing a polynomial separation between the randomized zero -error and one-sided error query complexity measures.

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a p x n matrix x over F-2 and Bob gets a vector y is an element of F-2(n). Alice and Bob need to evaluate f (x center dot y) for a Boolean function f : {0, 1}(p) -> {0, 1}. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C center dot n for Alice and C for Bob, if and only if there exists a deterministic/randomized parity decision tree of cost Theta As applications of this technique, we obtain the following results: (i) The first strong lower-bounds against randomized data-structure schemes for the Vector-Matrix-Vector product problem over F-2. Moreover, our method yields strong lower bounds even when the data-structure scheme has tiny advantage over random guessing. (ii) The first lower bounds against randomized data-structures schemes for two natural Boolean variants of Orthogonal Vector Counting. (iii) We construct an asymmetric communication problem and obtain a deterministic lower-bound for it which is provably better than any lower-bound that may be obtained by the classical Richness Method of Miltersen et al.. This seems to be the first known limitation of the Richness Method in the context of proving deterministic lower bounds.