| 1. |
- Apers, Simon, et al.
(författare)
-
Cut Query Algorithms with Star Contraction
- 2022
-
Ingår i: 2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). - : Institute of Electrical and Electronics Engineers (IEEE). ; , s. 507-518
-
Konferensbidrag (refereegranskat)abstract
- We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that (i) there is a bounded-error randomized algorithm that computes edge connectivity with O(n) cut queries, and (ii) there is a bounded-error quantum algorithm that computes edge connectivity with (O) over tilde(root n) cut queries. To prove these results we introduce a new technique, called star contraction, to randomly contract edges of a graph while preserving non-trivial minimum cuts. In star contraction vertices randomly contract an edge incident on a small set of randomly chosen "center" vertices. In contrast to the related 2-out contraction technique of Ghaffari, Nowicki, and Thorup [SODA'20], star contraction only contracts vertex-disjoint star subgraphs, which allows it to be efficiently implemented via cut queries. The O(n) bound from item (i) was not known even for the simpler problem of connectivity, and it improves the O(n log(3) n) upper bound by Rubinstein, Schramm, and Weinberg [ITCS'18]. The bound is tight under the reasonable conjecture that the randomized communication complexity of connectivity is Omega(n log n), an open question since the seminal work of Babai, Frankl, and Simon [FOCS'86]. The bound also excludes using edge connectivity on simple graphs to prove a superlinear randomized query lower bound for minimizing a symmetric submodular function. The quantum algorithm from item (ii) gives a nearlyquadratic separation with the randomized complexity, and addresses an open question of Lee, Santha, and Zhang [SODA'21]. The algorithm can alternatively be viewed as computing the edge connectivity of a simple graph with (O) over tilde(root n) matrix-vector multiplication queries to its adjacency matrix. Finally, we demonstrate the use of star contraction outside of the cut query setting by designing a one-pass semi-streaming algorithm for computing edge connectivity in the complete vertex arrival setting. This contrasts with the edge arrival setting where two passes are required.
|
|
| 2. |
- Blikstad, Joakim, et al.
(författare)
-
Breaking the quadratic barrier for matroid intersection
- 2021
-
Ingår i: Proceedings of the Annual ACM Symposium on Theory of Computing. - New York, NY, USA : Association for Computing Machinery (ACM). ; , s. 421-432
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 3. |
- Blikstad, Joakim, et al.
(författare)
-
Fast Algorithms via Dynamic-Oracle Matroids
- 2023
-
Ingår i: STOC 2023. - : Association for Computing Machinery (ACM). ; , s. 1229-1242
-
Konferensbidrag (refereegranskat)abstract
- We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified"algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with Õk(n+rr) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and Õk hides poly(k, log(n)). This implies the following consequences. (i) An improvement over the Õk(nr) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An Õk(|E|+|V||V|)-time algorithm for the k-disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the Õk(|V||E|) bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility. Matroid intersection. We show a matroid intersection algorithm with Õ(nr) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP'85], graphic matroid intersection [Gabow-Xu FOCS'89], simple job scheduling matroid intersection [Xu-Gabow ISAAC'94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a "unified"algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously. Lower bounds. We show simple super-linear (ω(nlogn)) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log2(3)n-o(n) bound by Harvey [SODA'08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS'19].
|
|
| 4. |
- Blikstad, Joakim, et al.
(författare)
-
Nearly Optimal Communication and Query Complexity of Bipartite Matching
- 2022
-
Ingår i: 2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). - : Institute of Electrical and Electronics Engineers (IEEE). ; , s. 1174-1185
-
Konferensbidrag (refereegranskat)abstract
- We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC'88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS'12; Dobzinski, Nisan, and Oren STOC'14; Nisan SODA'21] and tighten the lower bounds shown by Beniamini and Nisan [STOC'21] and Zhang [ICALP'04]. We also settle the communication complexity of the generalizations of BMM, such as maximum-cost bipartite b-matching and trans-shipment; and the query complexity of unique bipartite perfect matching (answering an open question by Beniamini [2022]). Our algorithms and lower bounds follow from simple applications of known techniques such as cutting planes methods and set disjointness.
|
|
| 5. |
- Chattopadhyay, Arkadev, et al.
(författare)
-
Simulation Beats Richness : New Data-Structure Lower Bounds
- 2018
-
Ingår i: STOC'18. - New York, NY, USA : ASSOC COMPUTING MACHINERY. ; , s. 1013-1020
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 6. |
- Chattopadhyay, Arkadev, et al.
(författare)
-
Simulation Theorems via Pseudo-random Properties
- 2019
-
Ingår i: Computational Complexity. - : Springer. - 1016-3328 .- 1420-8954. ; 28:4, s. 617-659
-
Tidskriftsartikel (refereegranskat)abstract
- 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).
|
|
| 7. |
- Dory, Michal, et al.
(författare)
-
Distributed weighted min-cut in nearly-optimal time
- 2021
-
Ingår i: Proceedings of the Annual ACM Symposium on Theory of Computing. - New York, NY, USA : Association for Computing Machinery (ACM). ; , s. 1144-1153
-
Konferensbidrag (refereegranskat)abstract
- 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 Õ(n0.8D0.2 + n0.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.
|
|
| 8. |
- López-Martínez, Andrés, et al.
(författare)
-
Work-optimal parallel minimum cuts for non-sparse graphs
- 2021
-
Ingår i: Annual ACM Symposium on Parallelism in Algorithms and Architectures. - New York, NY, USA : Association for Computing Machinery (ACM). ; , s. 351-361
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 9. |
- Mukhopadhyay, Sagnik, 1987-, et al.
(författare)
-
Lifting Theorems for Equality.
- 2019
-
Konferensbidrag (refereegranskat)abstract
- 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).
|
|
| 10. |
- Mukhopadhyay, Sagnik, et al.
(författare)
-
Separation Between Deterministic and Randomized Query Complexity
- 2018
-
Ingår i: SIAM journal on computing (Print). - : Siam Publications. - 0097-5397 .- 1095-7111. ; 47:4, s. 1644-1666
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
