Tight Bounds for Maximum Weight Matroid Independent Set and Matching in the Zero Communication Model
Authors: Ilan Doron-Arad
Venue: NeurIPS 2025 poster ()
Keywords: matroids; matching; distributed algorithms; parallel algorithms; lower bounds
Primary area: theory
TL;DR: The paper introduce the zero communication model of computation, describes tight bounds for matroids and matchings in this model, and shows how they yield faster parameterized deterministic parallel algorithms to these problems.

Abstract: Recent years have revealed an unprecedented demand for AI-based technology, leading to a common setting where immense data is distributed across multiple locations. This creates a communication bottleneck among the storage facilities, often aiming to jointly solve tasks of small solution size $k$ from input of astronomically large size $n$. Motivated by federated and distributed machine learning applications, we study two fundamental optimization problems, maximum weight matroid independent set (MW-IS) and maximum weight matching (MWM), in a zero communication computational model. In this model, the data is dispersed between $m$ servers. Without any communication, each server has to send a message to a central server, which is required to compute an optimal solution for the original (large) instance. The goal is to minimize the size of the maximum message sent. For this natural restrictive model, we obtain deterministic algorithms that use $k$-data per server for MW-IS and $O(k^2)$-data per server for MWM, where $k$ is the solution size. We complement these results with tight lower bounds -- ruling out any asymptotic improvement even if randomization is allowed. Our algorithms are simple and run in nearly linear time. Interestingly, we show how our zero communication algorithms yield deterministic parallel algorithms with running times $O\left(\sqrt{k} \cdot \log n\right)$ and $O\left(k^4 \cdot \log n\right)$ for MW-IS and MWM, respectively.

Tight Bounds for Maximum Weight Matroid Independent Set and Matching in the Zero Communication Model
llan Doron-Arad
Department of Computer Science
Technion
ilan a. d.g.ad10mm....mmmmmmmmmmm......m com
Abstract
Recent years have revealed an unprecedented demand for Al-based technology, leading to a common setting where immense data is distributed across multiple locations. This creates a communication bottleneck among the storage facilities, often aiming to jointly solve tasks of small solution size k from input astro- nomically large size Motivated by federated and distributed machine learning applications, we study two fundamental optimization problems, maximum weight matroid independent set (MW-IS) and maximum weight matching (MWM), in zero communication computational model. this model, the data dispersed between servers. Without any communication, each server has send message a central coordinator which is required to compute an optimal solution for the original (large) instance. The goal is to minimize the size of the maximum message sent. For this natural restrictive model, we obtain deterministic algorithms that use (kk)-data per server for MW-IS and O -dta per server for MWM, where k: is the solution size (given to each server). We complement these results with tight lower bounds ruling out any asymptotic improvement even if randomization allowed. Our algorithms are simple and run in nearly linear time. Interestingly, we show how our zero communication algorithms yield deterministic parallel al- gorithms with rumning times O (Vk logn) and O (K+ log n) for MW-IS and MWM, respectively.
1 Introduction
Recent years have revealed an unprecedented demand for Al-based technology. Consequently. data and computing resources are often distributed across multiple locations [6]
59 42 either due to
difficulties of storing immense data in a single location [17 or privacy and security concerns [4]]. Furthermore, communication among the storage facilities is often bottleneck prohibited.
This data storage shift has a significant effect the relevant algorithmic model of computation. Classic sequential algorithms, where the entire data is given to a single processor, are no longer applicable to the most urgent algorithmic challenges we face today. response, the algorithmic community focuses on the core fundamental problems on new computational models. This include distributed algorithms
parallel computing (54]. online algorithms 2 dynamic and streaming algorithms 49 and many more computational models.
Motivated by federated and distributed machine learning applications (5
42 this work focuses
on an ultra-restrictiv model of computation, which allows zero communication between different parties (aka, servers) holding parts of large data. Each server sends without any communication subset of its data to central coordinator who is obligated to find an optimal solution for the original
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

instance. The goal is to minimize the amount of data sent. We often consider problems where the solution size k is significantly smaller than the overall imput size n. This model is a one-round message-passing model described more formally below.
1.1 The Zero Communication Model
Before the definition of the model, we define the class of problems appropriate for the model. We consider the general class of weighted subset selection problems such as weighted matroid optimization and maximum weight matching. In general subset selection problem P parameterized by solution size, an instance is described as I = (E, w. k), where E is a set of elements, w: E - R is weight function, and & IN is cardinality constraint (upper bound) on the solution size; henceforth refer to k as the solution size with a slight abuse of notation. Moreover, there exists a set F C 2 of feasible solutions, which are usually not given explicitly in the input but must be inferred computationally. The goal is generally to find S E F such that |S| I l and Eees we() is optimized either maximized or minimized. For the following definitions, fix some subset selection problem P and an instance 1 = (E, w. k) of P.
In this model, the set E' is partitioned E,...., E., between servers for some E IN and each server also receives the parameter k. In feasible selection of the given instance, each i E {1,.... m) selects E S E, without any communication with any other server j f1..... m {i); then, server i sends {(e, w(e))} beg (that is, an explicit encoding of the selected elements and their weights) to a central coordinator, such that Use(1.....) Fg must contain an optimal solution for 7: there is
S S (I..(.....m)))) E2 such that S is an optimal solution for the instance. The goal is to find a feasible selection of 7 that minimizes the maximum message size per server: maxig(I.....m) |P-l For some d E IV, we refer to an algorithm in this model as d-data algorithm if each server transmits at most d element-weight pairs to the coordinator: Z ma..g(L.....m) [X
An algorithm is a randomized (respectively, deterministic) d-data algorithm if it uses d-data and yields a feasible selection with probability at least 2 (probability 1 and does not use any form of randomness). The only form of randomness considered in the paper is on the feasibility (Monte Carlo) and does not consider random algorithms with random bound on the running time (Las Vegas). We emphasize that despite the name, the zero communication model allows one-directional communication between server and the coordinator, but prohibits communication between any two servers.
The above paragraph assumes explicit data model, where each element and its weight are explicitly communicated. However, this model can be easily generalized such that each server i sends some encoded message from which the coordinator can decode {(e, (o(c))}EEE))
JeE Due to Shannon's 's source coding theorem [58] it holds that Ω (log (FI) bits required to be sent for uniquely distinguishing between all pairs of solutions in F, which implies that for exponential size solution set J the explicit data encoding cannot be asymptotically improved under unique encoding. Moreover, the elements may have large metadata (e.g., large weights) and their encoding size may fluctuate dramatically. Therefore, we focus simple explicit encoding of {(c, w(e))) bee; for the messages and use the well-defined number of elements sent rather than the size of the message.
As an example, consider the maximum weight matching (MWM) problem in the zero communication model. Consider a graph G = (V, E) and a weight function on the edges w E -> IR. The edge set E is partitioned between m servers Ei.... Em. Each server E {1, {1...., mm] sends subset of the given edges and their weights {(e, (<e)))ee Fy to the coordinator, such that ULe EV contains a maximum weight matching of G with respect to w. Some of our results are tight bounds for the number of edges required to be sent from each server in this model.
Motivation Al and ML applications use more than ever before data distributed across multiple locations such as data centers [60], hospitals [35], or edge devices [45]. Task assignment problems (or, matching) naturally appear in such distributed setting: Each vertex represents an agent and the algorithm aims to select an optimal assignment of agents to tasks, where the servers hold only partial information on subset of the agents. For example, in medical settings, patient data may be partitioned across hospitals due to privacy or logistical constraints [56] (35. Similar scenarios occur
An alternative objective is to minimize the total communication, resulting with similar model.

---

in recommendation systems and federated learning, where we aim to solve combinatorial problems efficiently despite limited communication.
Another motivation for studying this model is its ability to derive parallel algorithms in a standard demonstrate in this paper. Furthermore, the zero communication model
computational model, allows to distinguish between the difficulty of problems in common distributed setting. Knowing which problems exhibit this property can have practical implications and enable robust algorithms that do not have to process large data on single processor. Finally, the model generalizes well-studied problems in the literature, such as dieectrctionn communication, making it a natural extension of prior work (see Section 1.3
1.2 Our Results
Despite the plethora of research works on maximum weight matching and matroid independent set in various models, some fundamental questions are still present. This paper studies the elementary question of how much data from multiple servers needs to be delivered to solve a fundamental problem optimally with zero communication between the servers. This is particularly interesting when the solution size k small the optimal solution does not require most data in the input. Our main results are tight bounds for these problems in the zero communication model and their direct implications to parallel algorithms, giving bounds that depend on the solution size We begin with formal definitions of the considered problems.
Maximum Weight Matroid Independent Set (MW-IS) Consider finite ground E and let I S 2F be non-empty set of subsets of E called the independent sets of E. The set system M (E, I) is a matroid if (i) for all A E I and B C A it holds that B I: (ii) for any A, B I where |A| > [B] there is E A \ B such that B U [e] E I. In the MW-IS problem, given a matroid (F. and a weight function w E - on the elements, the goal is to find a maximum weight independent set: S E I such that Eees w(e) is maximized. Additionally, this problem can be considered in a parametric setting, where the input also consists of a bound i E IN and the chosen IS has to be of cardinality bounded by k. We refer to this problem k-MW-IS, As this variant is more general (using matroid truncation), our results are described for k-MWIIS and hold also for MW-IS.
Maximum Weight Matching (MWM) Let G (V, E) be graph, and let w E - IR be weight function on the edges. The goal is to find matching M (a set of pairwise disjoint edges) that maximizes EeEm w(e). Similarly to MW-IS, a variant of this problem is k-MWM, where the input also consists of a bound & E IV on the cardinality of the maximum matching that can be selected.
Throughout the paper, k denotes the size of an optimal solution for a given problem (in most cases, either MW-IS or MWM) and = EE denotes the input size. Let Ô denote big-O, Ω notations, respectively, suppressing logarithmic factors in n. Our main algorithmic results in the zero communication model are given below. These algorithms are deterministic and run in nearly linear time. addition, these results hold even if the inputs to some of the servers overlap. Interestingly, our algorithm for MW-IS does not require the servers to know the parameter k; on the other hand, this parameter necessary for our MWM algorithm (i.e., the result holds for k-MWM).
Theorem 1.1. There is deterministic k-data algorithm for k-(MW-IS) and MW-IS. Moreover, for each server E [m]] the running time of server is Ö(v [Bi]) parallel time, or Ö((E.)) non- parallel time.
In similar setting, we give result for MWM well.
Theorem 1.2. There is deterministic O (k2) -data algorithm for k-MWM. Moreover, for each server i E [m] the running time of server is Ö(E.)
We complement the above algorithms with tight lower bounds. These lower bounds rule out any qualitative improvement of our algorithms, even if randomization allowed.
Theorem 1.3. There is no randomized o(k) -dta algorithm for k-MW-IS.
We note that Theorem 1.3 holds for every m, k, E IN {0) such that n. c. A and m = k. where n the number of elements, m the number of servers, & is the solution size, and is an additional integer parameter. In particular, the above result holds for arbitrarily large with
3

---

respect to k, m, and uses only two distinct weights. Moreover, for deterministic algorithms. the bound rules out - number of communication rounds with the coordinator and not necessarily one round of one-way communication.
2 -daa algorithms and is effectively tight. Finally, the result also applies to any
Similarly to MW-IS, We give a tight lower bound for k-MWM.
Theorem 1.4. For every l E N, there is no randomized o ) algorithm for k-MWM.
The above lower bound use weighted instances. We give an additional easy lower bound for unweighted MWM instances, or, maximum cardinality matching (MCM) instances.
Theorem 1.5. For every even 2 there no deterministic
(b))) - algorithm for I-MCM.
The above algorithmic results in the zero communication model follow from the structural properties of the given problem. Interestingly, these algorithms lead simple deterministic parallel algorithms for MW-IS and MWM, significantly strengthening the running time guarantee for small solution size we assume that the weights are poly-logarithmic in the size of the ground set: w(e) (nlylog(n) for every E E. Dropping this practical assumption would change the guarantee of our algorithms to linearly depend on the maximum representation size in bits of any of the weights. We start with MW-IS, and give sub-linear parallel running time in the rank of the matroid (effectively equivalent to the parameter using matroid truncation).
k. As in various previous works on the subject (e.g.. (37 48 50 28))
Theorem 1.6. There is a deterministic parallel Ö(Vk) time algorithm for k-MW-IS.
The above algorithm works for general matroids, unlike parallel efficient (RNC algorithms, see Section I.3) that can be applied only to linear matroids [37 48 [50..
Theorem 1.7, There is a deterministic parallel Ô (k-)) time algorithm for k-MWM.
We note that the above statement holds for general graphs, and the running time bound may be improved for special cases of the problems, such bipartite graphs. Using the above result as black-box, we obtain a parallel algorithm for MWM (without a cardinality constraint).
Theorem 1.8. There is a deterministic parallel Ô (K*) time algorithm for MWM.
A summary of our main results is given in Table 1
Problem
Zero Communication
Parallel Time
Algorithm
Lower Bound
Algorithm
k-Max Weight Matroid IS
k
22kk)
Ö(Vk)
k-Max Weight Matching
O (12)
Ω (K2)
Ô (R:)
Table 1: Our main results. In the table, l denotes the solution size. The zero communication algorithms are deterministic and the lower bounds also rule out randomized algorithms.
1.3 Related Work
There has been extensive work matching and matroid optimization in similar models to those studied in this paper. However, the majority of these works focus on approximation algorithms. the one-round communication complexity model 29 336,, the input is partitioned between two players Alice and Bob. Alice sends a single message to Bob, and Bob outputs an answer using his input and the message received from Alice. Maximum matching in this model was first studied by Goel, Kapralov, and Khanna [29), who designed an algorithm that achieves a aaapproximation in bipartite graphs using only (n) communication and proved that any better than 3 -approximation algorithms would require at least n ++0% io communication complexity. This holds even on bipartite graphs (see also 4)) Later, Lee and Singla [47 obtained g-approximation algorithm for general graphs.
Assadi and Bernstein 3 obtained a 2/ 2/3-approximation for maximum matching in the one-round communication complexity; they also obtained approximation algorithms for stochastic matching

---

II 6 5
(finding maximum matching in random graph) and fault-toerrance 13 8 12 matching
ppreserving an approximation guarantee even if any sufficiently small subset of edges is removed from the graph), where all of their results use the edge-degree constrained sub-graph (EDCS) matching construction originating
[T]] The EDCS matching construction has been generalized to matroid
intersection by Huang et al. [32 achieving roughly the same approximation ratio of ( e) in the
one-round communication complexity model.
each server (or player) receives a part of the input and communication possible between all pairs of servers. After some communication between the servers, the mutual goal is to send message to coordinator that computes some function of the imput while minimizing the total communication complexity. For simultaneous protocols (the messages are sent simultaneously to the coordinator) Assadi et al. 7 obtained tight randomized a-approximation for maximum matching for a S Vm with total communication of O(n m a²) and a deterministic protocol with total communication of O m - a), where n is the number of vertices and m is the number of servers. For non-simultancous setting, there is tight è (a² m - n) information-bil a-approximation for maximum matching [33]. We are not aware of any results for matroid optimization in this model.
In the Message- Model 16
33 53
As mentioned above, there many works bounded or oneedirectional communication, some of them can be seen as special cases or variants of the zero communication model. In addition, the idea of providing
dataset, known coreset, is prevalent in machine learning literature (e.g., [46 31 22 23 52). Under these lenses, our model can intuitively be viewed as distributed (communication free) construction of non-approximate variant of coreset. However, to the best of our knowledge, the zero communication model as defined above is introduced in this work.
In a distinct line of research, maximum matching is well-studied in parallel algorithms. The main class of parallel algorithms considered is Nick's Class (NC) polylog(n) parallel time using poly(n) number of processors with unrestricted communication between them, where n denotes the input size. There are randomized NC (RNC) algorithms for maximum cardinality matching and matroid intersection on linear matroids by Lovász work [43] by reducing these problems to deciding if a
determinant of a symbolic matrix is equal zero, which can be solved in NC time [13 91. A
few years later, RNC algorithms were obtained for finding actual solutions 337 48 50 There are
also pseudo-deterministi NC algorithms (27 28); however, whether there exist deterministic NC
algorithms for maximum matching (or matroid intersection) remains one of the long-standing and important questions in theoretical computer science.
1.4 Discussion
In this work, we provide tight bounds of (l)) and θ (1:2) on the data required per server to solve k-MW-IS and k-MWM, respectively, in the zero communication model. In addition, we give deterministic Ô (vk) and Ô (A*)) time parallel algorithms for MW-IS and k-MWM, respectively. Some implications and limitations of our work, and some open questions are listed below.
Matroid Intersection This work focuses on zero communication algorithms for MW-IS and MWM. interesting question that can the subject of follow-up research is what is the minimum fkk for which there is f(k)-data algorithm for matroid intersection, where k is the rank of one of the given matroids. An f -da- algorithm for matroid intersection can be obtained for an exponential function f relatively easily. It would be intriguing solve this for polynomial function f. or show a lower bound ruling this out.
Parallel Algorithms In this work, obtain deterministic parallel algorithms for MW-IS and MWM of running time guarantee ò (VF and Ô (k:4), respectively. For k < n, these algorithms are faster than the classic RNC (i.e., randomized parallel) algorithms for the problems
48 50)
Moreover, our schemes handle general matroids rather than the special case of linear matroids as in previous works. However, for Ω (n²) for some constant e our parallel algorithms are no longer in NC. The most important open question here is whether a deterministic NC algorithm for MWM or MW-IS (on linear matroids) exists, even for the unweighted versions of the problems. As this question remains open for several decades, we believe that our bounds, parameterized by k. pave
5

---

research path towards faster deterministic parallel algorithms for maximum matching (and matroids) with stronger parametric bounds on the solution size k.
Approximation Algorithms All of our results apply to exact optimal versions of the considered problems. That is, unlike the majority of the previous work in similar models of low or no commu- nication [29] 36 16
553 34 77], this paper does not consider approximation algorithms. While there are results for zero communication on both matroids [32 and matching [3), most works focus on two servers (i.e., Alice sends data to Bob), allow some communication. It would be very interesting to extend the state-of-the-ar approximations for a general number m of servers with zero communication. It would also be nice to obtain stronger lower bounds for such settings.
33
Parameterized (fixed- parameter tractable (FPT)) Algorithms Our bounds are parameterized by k the solution size of the given problem. One may wonder, at least superficially, whether the fact that matching and matroids have such catta-prramttriizee attributes in the zero communication model
implies some connection to fixed- peeemparreeter tractable (FPT) algorithms (20) Stated alternatively,
can be thought that the fact that (ppoly(A) (1)) d-data algorithms exist for MW-IS and MWM can be attributed to the fact that these problems are efficiently solvable. However, as we show in Appendix [F] there are well-known problems that are (1) efficiently solvable and (2) have a small solution size k < yet do not have a d-data zero communication algorithm for d = o(n).
MWM vs. k-MWM Our zero communication algorithm focus on the cardinality constrained version of MWM, namely, k-MWM. We note that without this restriction, there is only an -aata algorithm for MWM (consider a single server whose sub- -abbggrah is a star graph of 12(m) edges, which cannot determine which subset of edges send, as any of these edges might belong the optimal solution depending on the input to the other servers). However, the cardinality constraint has also practical justification.
For example, bipartite graphs with one side of the bipartition significantly larger than the other appear in various applications. Consider server with k processing slots and given set of >> k tasks, each task can be scheduled on a subset of the slot, determined by compatibility issues such as memory communication bandwidth, bipartite graph with & vertices on one side and n >> & vertices on the other side, where the goal of the server is to compute an MWM (the weight being the price a task is willing pay to be scheduled on a corresponding processor). Another example is allocating ads to (a few) advertisement slots. Another variant of this problem is the well-studied partial optimal transport (2 14). We note that our parallel MWM and M-MWM algorithms use a sequential k-MWM algorithm as a black box. A feasible research direction is strengthen our parallel bounds using faster black-box k-MWM algorithm for special cases of the problem, such as bipartite graphs. More details are given in the appendix.
other performance
security reasons. This induces
Noisy/faulty Server Inputs This paper studies the zero communication model, in which the input to the servers is assumed to intact. However, this model can be generalized to tackle noisy or faulty server inputs. The noise can be either on (1) the actual element whether it is given to the server or not, (2) the fcasibility the server may not know exactly which subsets of clements are feasible, and (3) the weights can be noisy. This of course, only makes the problem more difficult, thus our lower bounds hold; it remains open if the algorithms given in the paper can be generalized to tackle any of these scenarios. While the answer depends the exact formulation of the noise model, our bounds are unlikely to hold as is. It remains an interesting question for follow-up research to rigorously define variation of our model on faulty servers and give tight bounds for the discussed problems (and more) in such a model.
Matroid Structure and Membership Oracles In zero communication algorithms, each server must be able to compute independence on subsets of elements it received. Without this assumption, it would be impossible to design a cero-communiaation algorithm that does not simply send all elements. Most matroids considered in the literature, and those with the strongest applications, are linear matroids (e.g., graphic matroids), which can be compactly defined and allow efficient independence testing with relatively small memory. However, there are also non-linear matroids, which may require exponential memory (in the number of elements of the ground set) to distinguish correctly between independent sets and non-independent sets. These matroids appear less in practical

---

settings and will require that each server have larger memory. To make independence testing more abstract, we assume that independence is computed via a membership oracle (see Section 2
Organization In Section 2 we give some preliminary definitions and notations. In Sections 3 and we give our zero communication algorithms for MW-IS and MWM, respectively. Then, Section describes the implications of the above algorithms for parallel computation. Due to space constraints, We give our lower bounds for zero communication algorithms and some of the remaining proofs in the appendix.
2 Preliminaries
Let IN [1.2....} be the of natural numbers excluding zero. For any l E IN let [k] fl...., . } for short. In addition, for any set X, function f X - IR, and finite S C X let f(S) Eees fee. With slight abuse of notation, we occasionally use the same notation for function f and for restriction of J' to subset of its domain.
Basic Notations
Graph and Matching Notations Fix a graph G = -V, for the remaining of this section. In general, all edges in this paper are undirected and with slight abuse of notation, we use (u, v) to denote the undirected edge fu, v4 between vertices u, v E V. We also assume that there are no parallel edges throughout this paper. Let [(e) = {u V (u, v) E E} be the set of neighbors of V holds that v an VJI < 1. Furthermore, M is perfect matching every vertex appears exactly once as an endpoint of an edge in M. When the graph is clear from the context, we use V(S) U(w.eess {u, r) as the vertex set of end-points of subset of edges S C E the graph G. Given C V define the induced graph G[S] = (S, E[S]) of G and S, where E[S] = {(u, v) E E u, E 5). Finally, we use the standard notation G (A, B, E) for bipartite graph, where A, B are sets of vertices and E CA
some V. A matching G subset of edges M C E such that for all endpoint of at most one edge in M; that is, ((u, v) E M
Matroids Let .M- = (E, be a matroid. All matroids in this paper are assumed to be general matroids whose set of elements is given in the input and for any $ C E, determining whether S I can be done in one query to a membership oracle that is assumed to take O(1) time and memory. We note that this is the standard formalism of representing general matroids for algorithmic purposes (see, e.g., [57 51 for more details).
A basis of matroid is an inclusion-wise maximal independent set of the matroid. The following matroid operations remain matroids (see, c.g., [57)).
Matroid Restriction:
For any F C E define InF = {A E I MEIIAAA ACF) and M (F,InF) as the F-restriction of M.
Contraction: For any F E I define I/F {A C E F AUF E I} and define M/F = (E') F/IFP) as the F-contraction of M.
Truncation: For any E N define Igg = (A E
|A| S 4 and (E,Isa) as
g-truncation of M.
3 A Zero Communication Algorithm for MW-IS
In this section, we obtain a zero communication deterministic k-data algorithm for MW-IS. The following is standard structural lemma used to derive our result.
Lemma 3.1. Let M = (E, I) be a matroid of rank k and let w E IR be a weight function. Let E IN, let EI...., Em be a partition of E, and let Bı,..., Bm be maximum weight bases of the Em, respectively. Then, there is a maximum weight basis B of M such matroids M MI......, that B Use B,
We give brief overview of the proof below. We consider a basis B" with the largest intersection with the elements in Ute[m B, there is some E B" Ute|m) B, we can show using some insights on generalized exchange properties of matroids that there is some element e' E Uie(m] B; with larger or equal weight w.r.t. that can be added to 8" instead of implying contradiction to the fact that
7

---

B" has a maximal intersection with Use(m) B;. This generic line of proof has also been used in other matroid and ceatching-relatede problems in approximation algorithms, including the author's prior work in a different setting [8] 19]. The full proof given in the appendix.
We use the following result of (38 for obtaining our main result.
Theorem 3.2. [38] There is deterministic parallel (Vvn) algorithm for finding maximum weight basis of a matroid with n. elements.
Thus, we obtain the following results. As our algorithm is based on simply computing a basis for each server, the parameter & can be omitted from the input (that is, the following result holds for MW-IS in addition to k-(MW-IS)).
Theorem 1.1. There is deterministic k-data algorithm for k- k-(M-IIS) and MW-IS, Moreover, for each server E [m] the running time of server is O E.l) parallel time, or Ö((E,) non- parallel time.
Proof. Let 7 = (F,, w. k) be an instance of MW-IS whose elements are distributed into servers by Fj,...; : Emm The proof follows by computing for each server maximum weight basis B, for the matroid restricted to the set of elements E; given server i and truncated with the value k. These bases can be either computed using the standard greedy algorithm in time Ö((E:) (for more details on the greedy algorithm sec, c.g., (57l), using a parallel deterministic ((V [ time algorithm of Karp et al. (38. Since the optimum of size k. by Lemma 3.T follows that there is an optimal solution for (i.e., maximum weight basis of the original matroid truncated by k) in Uselma B;- Thus, the above algorithm optimally solves the original instance and sends most k elements from each server. The proof follows.
4 A Zero Communication Algorithm for Maximum Weight Matching
In this section, we give zero communication algorithm for k-MWM. Our approach is based on the following auxiliary structures we call strong sets.
Definition 4.1. Let G = (V, E) be a graph, let w + R be a weight function, and let is E N be parameter. A set of edges S C E is called a strong set of E, w, and k if for every (u, v) E E at least one of the following holds.
1. S.
2. There is a matching M C S G of cardinality 2 + 1 such that for every f E M it holds that w(f)= 2 w(e).
3. There is {u. v and there are 2 k + 1 distinct edges (z, vz)...., . that for all E [2 k + 1] holds that w ((x, vc)) 2 w ((,,
U2 (I,22411) e S such
The following algorithm finds strong set efficiently.
function Lemma 4.2. There is an algorithm STRONG-SER that given a graph G = (V, E), a functionn E RR and a parameter k E IN returns in time (IE) log |E) a strong set of E, w, k of cardinality at most 10- k22 ++++1
For the entire proof of the theorem, fix graph G (V, E), weight function w E - RR, and parameter & IV and define the following algorithm STRONG- SERTTG-SETTRE on the above input. Let = V and [E] (with slight abuse of notation, recall that m is also used in this paper to denote the number of servers; however, this is not considered in the current algorithm and its proof). For a subset of edges 5 F and E V let
N(S,)) = H(xx y) E 8 == ory = =
be the number of neighbors of v in S. The algorithm iterates the edges in a non increasing order of weights, and adds to the constructed strong set the current edge (u,, v;) if both NSS are bounded by 2 k. The algorithm is formally defined as follows.
"We note that if the maximum weight W = max.ge [w[e]] is large w.r.t. [E], then the running time also depends w. as the running time follows from sorting an array of size |E".
8

---

1. Let e1,...,,m fm be the edges in E sorted in a non increasing order w.r.t. w
2. Initialize t-P y
3. For i = 1,.... m do:
(a) Let C2 (u4, Us)
(b) If (S, uz) 2 and ((S, vs) S 2 then: S SU {ei}
(c) If [S] 2 10 10- 622
then: return S
4. return S
Intuition We give below some Intuition on Algorithm STRONG-SET (a formal proof is given in the appendix). For the following, consider execution of the algorithm on set of edges E with weight function w, such that the algorithm returns a subset S of edges. Consider some arbitrary edge
v) E E, and let give the intuition why necessarily at least one property from (I), (2), or (3)
of Definition 4.1 holds for e. We consider several cases here. First, clearly if E S, then property (1)
trivially holds for Second, assume that (1) does not hold for and we shall show why (2) or (3)
must hold. Since e is not added to S, by Step (b) of the algorithm we can consider two sub-cases to conclude.
N(S, u) > k or N(S,v) > 2 k. From this case, (3) casily holds since has at least 2 k + neighbors of some E {u, v}, where all of these neighbors are with weight at least (e) by the sorted order of the edges.
The complementary case, where NSS, u) S k and N v) S 2- k. Since e of S, then the algorithm terminated by the stopping condition of Step (c) and consequently |S| > 10 k22 By Step (b) of the algorithm, for each edge e; = (u, 02) holds that N(S, u;) S k + and (S, u;) < 2- k + 1. Therefore, the edges in S induce graph with over 10 k22 edges that has a maximum degree of 2 k 1. By a result of Han (30], in this induced graph there exists a matching of size of over 2. k.
The following structural lemma for distributed MWM using strong sets, showing the power of strong sets for zero communication algorithms.
Lemma 4.3. Let G = (V, E) be a graph, let w E IR be a weight function, and let k E IN be parameter. Additionally, let E IN, and let E1...., Em be partition of E. For all i [m] let S: be a strong set of Es, w. k. Then, there is k-maximum weight matching M of G such that M C Uieemm].. St.
Intuition We give below some intuition for the above result and a formal proof is given in the appendix. In the above lemma, we are given a strong set S: for each server and need to prove that the union of S,'s contains k-MWM. Consider k-MWM denoted by M with the maximum size of intersection with the union of S,'s. If M is contained in this union - the central server can directly compute M Otherwise, there is edge E M* that belongs to F&ę for some server such that &f S, By Definition 4.1 and as o S,, one of the following holds:
1. There is matching M contained in St of cardinality 2 k + 1 such that every edge in M has weight at least w(e). Thus, as M is sufficiently large and since M and M* are matchings, there is e in M such that A1' _M" U (e') a matching (each endpoint of M can appear at most once as an endpoint of M and [M > 2- IM* Note that w (M') 2 w (M*)
2. There is an endpoint x of and there are . A + distinct edges adjacent to æ: (z, vi)...,, (I, U2 12)),,, each of weight at least w(e). Since |M* < k it has at most 2 k endpoints; therefore, one of the above 2 ++ edges e' = (x, 02) satisfies that v, is not endpoint of M Thus, since (c') 2 w(e) it holds that M' M \ {e) fe') is matching satisfying w (M') 2 w (M*).
The above two cases yield contradiction that M is k-MWM of maximum intersection with the union of S,'s.
We can now give the main theorem of this section.
Theorem 1.2. There is a deterministic O (k:)) -dat algorithm for k-MWM. Moreover, for each server i E [m]] the running time of server is Ö(EE.).

---

Proof. Let I = (V, E, w, k) be an instance of MWM, where the edges are distributed into m servers by Ei,..., Em The proof follows by computing for each server a strong set of E,, w, k S, using Algorithm STRONG-SET. By Lemma 4.3 there is optimal solution for 7 (i.e., k-MWM) in Uieim| S. Thus, the above algorithm optimally solves the original instance and by Lemma 4.2 the algorithm sends at most (10 k2 + edges from each server using zero communication. The running time guarantee of each server follows from Lemma 4.2
Parallel Algorithms
In this section, show that zero communication schemes lead to fast parallel algorithms. The results follow from the next theorem, whose proof is given in the appendix. Recall that for our parallel algorithms that the weights are assumed to be poly-logarithmic in the input size n.
Theorem 5.1. Let P be subset selection problem that has a zero communication f(k)-data algorithm A in time (()(( for each server i E [[m]], for some monotonic polynomial functions f. where & is the solution size. Then, there is an Ö (g (f())) time parallel algorithm that given an instance of P returns subset of the elements of size (I)))) that contain optimal solution. The algorithm is deterministic if A is deterministic.
We give below the pseudocode of the algorithm described in Theorem 5.] and the full proof given in the appendix. Let I = (E, w, k) denote an instance of subset selection problem P. where E is of elements,
weight function, and & is the solution size. Define the following algorithm on instance / based on the existence of a zero communication algorithm A for P. Let EE
1. Let j + 0, E + E, & n
2. While n: > 1:
4:f(A)
(a) Let my =
4-f(K)
(b) Partition E into servers El...., Ei....,,,, Ei where E/ S 4- f(k) for all e [my]
(c) Execute A on the instance I, (E k)
iE(my)
(d) Let K2 C Fij be the elements brought from server to the central coordinator Vi [my]
(e) Update ES+1 < Use(mg) K/,
FS+1
j+j+1
3. Return E
Intuitively, at each iteration of the algorithm, each server applies a filtering of the elements it receives: Each server gets roughly 4 ((k) elements and returns only f(k) elements (in parallel to the other servers). Thus, in Ollgg n) such rounds, we obtain an O(((k) size instance. We note that the number servers my used in each iteration decreases exponentially.
By Theorem 5.1 we have the following results for MW-IS and MWM.
Theorem 1.6. There is a deterministic parallel Ö O(vk) time algorithm for k-MW-IS.
Proof. By Theorem 1.1 there a deterministic zero communication k-data algorithm for maximum weight independent set of matroid in deterministic parallel time of Ö /EEl) for each server i. Assuming membership oracle for the given matroid, sending each element to the central coordinator takes Ô(1) bits each element-weight pair in the ground set can be encoded in O(log n) bits assuming pseudo-polynomial weights. Thus, sending k elements from each server can done using (k) bits. Hence, by Theorem 5.1 there is a deterministic parallel Ö(Vk) algorithm that computes subset elements size O(k) containing an optimal solution; on this subset, we can apply Lemma 3.2 to get an overall (vV)) parallel time deterministic algorithm for MW-IS.
LI
The proofs of Theorem 1.7 and Theorem 1.8 are given in the appendix.
10

---

References
[1] Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 52(1):1-30, 2005.
[2] Susanne Albers. Online algorithms: survey. Mathematical Programming, 97:3-26, 2003.
[3] Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. arXiv preprint arXiv: 18/ 1.02009, 2018.
[4] Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Proceedings of the Twenty-Eight Anmual ACM-SIAM Symposium on Discrete SIAM, 2017.
Algorithms, pages
[5] Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem: Beating half' with non-adaptive algorithm. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 99-116, 2017.
[6] Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem with (very) few queries. ACM Transactions on Economics and Computation (TEAC), 7(3):1-19, 2019.
[7] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultancous communication model. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1345-1364. SIAM, 2016.
[8] Surender Baswana, Keerti Choudhary. and Liam Roditty. Fault-tolerant subgraph for single- source reachability: General and optimal. SIAM Journal on Computing, 47(1):80-95, 2018.
[9] Stuart Berkowitz. On computing the determinant in small parallel time using small number of processors. Information processing letters, 18(3):147-150, 1984.
[10] Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part 42, pages 167-179. Springer, 2015.
[11] Avrim Blum, John Dickerson, Nika Haghtalab, Ariel D Procaccia, Tuomas Sandholm, and Ankit Sharma. Ignorance is almost bliss: Near-optimal stochastic matching with few queries. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 325-342, 2015.
[12] Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. Optimal vertex fault tolerant spanners (for fixed stretch). In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposhum on Discrete Algorithmss, pages 1884-1900. SIAM, 2018.
[13] Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving distances in very faulty graphs. In loannis Chatzigiannakis. Piotr Indyk. Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming. ICALP 2017, July 10-14, 2017, Warsaw, Poland.
[14] Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. ACM Transactions on Graphics (TOG), 38 38(4): 2019.
[15] Allan Borodin, Joachim von zur Gathem, and John Hoperoft. Fast parallel matrix and ged computations. In 23rd annual symposium on foundations of computer science (sfes 1982), pages 65-71. IEEE, 1982.
[16] Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. tight bound for set disjointness in the message-passing model. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 668-677. IEEE, 2013.
[17] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions Computer Systems (TOCS), 26(2): 2008.
11

---

[18] Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An eptas for budgeted matching and budgeted matroid intersection via representative sets. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 49-1. Schloss Dagstuhl-Leiiniiz- Zentrum für Informatik, 2023.
[19] Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An eptas for budgeted matroid independent set. In Symposium on Simplicity in Algorithms (SOSA), pages 69-83. SIAM, 2023.
[20] Rod G Downey and Michael R Fellows. Fixed-paramete tractability and completeness i: Basic results. SIAM Journal on computing, 24(4):873 1995.
[21] Jack Edmonds, Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 19(12-113):555
1965.
[22] Dan Feldman. Core-sets: Updated survey. In Sampling techniques for supervised or unsuper- vised tasks, pages 23 Springer, 2019.
[23] Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 361-370, 2009.
[24] Alessio Figalli. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):5335565 560, 2010.
[25] Harold N Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pages 434 443,443, 1990.
[26] Harold N Gabow and Robert E Tarjan. Faster scaling algorithms for general graph matching problems. Journal of the ACM (JACM), 38 853, 1991.
[27] Eran Gat and Shafi Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. In Electronic Colloquium on Computational Complexity (ECCC), volume 18, pages 1-3, 2011.
(28) Sumanta Ghosh and Rohit Gurjar. Matroid intersection: A pseudo-deterministe parallel reduc- tion from search to weighted-decision. In Approximation, Randomization, and Combinatorial Optimization. Algorithmss and Techniques (APPROX/RANDOM 202 pages 41-1. Schloss Degsuull-ecibniz-Zeenuuu für Informatik, 2021.
[29] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the twenty-third annual ACM- SIAM symposium on Discrete Algorithms, pages 468-485. SIAM, 2012.
[30] Yijie Han. Matching for graphs of bounded degree. In International Workshop on Frontiers in Algorithmics, pages 171-173. Springer, 2008
[31] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering, In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 291-300, 2004.
[32] Chien-Chung Huang and François Sellier. Robust sparsification for matroid intersection with applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
SIAM, 2024.
[33] Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. Communication complexity of approximate matching distributed graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), pages 460-473. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2015.
[34] Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. Communication complexity of approximate maximum matching in the message-passing model. Distributed Computing, 33(6):515-533 2020.
12

---

[35] Arthur Jochems, Timo M Deist, Johan Van Soest, Michael Eble, Paul Bulens, Philippe Coucke, Wim Dries, Philippe Lambin, and Andre Dekker. Distributed learning: developing a predictive model based on data from multiple hospitals without data leaving the hospital-a real life proof of concept. Radiotherapy and Oncology, 121(3)459 467, 2016.
[36] Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the !wenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1679-1697. SIAM, 2013.
[37] Richard M Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is random nc. In Proceedings of the seventeenth annual ACM symposium Theory of computing, pages 22-32, 1985.
[38] Richard M Karp, Eli Upfal, and Avi Wigderson. The complexity of parallel search. Journal of Computer and System Sciences, 36(2):225-22) 253,, 1988.
[39] Harold W Kuhn. Variants of the hungarian method for assignment problems. Naval research logistics quarterly, 344)2253-258, 1956.
[40] Li Li, Yuxi Fan, Mike Tse, and Kuo-Yi Lin. A review of applications in federated learning. Computers Industrial Engineering, 149:44 2020.
[41] Yibin Li, Keke Gai, Longfei Qiu, Meikang Qiu, and Hui Zhao. Intelligent cryptography approach for secure distributed big data storage in cloud computing. Information Sciences, 387:103-115, 2017.
[42] Liu, Jizhou Huang, Yang Zhou, Xuhong Li, Shilei Ji, Haoyi Xiong, and Dejing Dou. From distributed machine learning to federated learning: A survey. Knowledge and Information Systems, 64(4):885 917, 2022.
[43] László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79, pages 565 065-574,17 1979.
[44] Nancy A Lynch. Distributed algorithms. Elsevier, 1996.
[45] Massimo Merenda, Carlo Porcaro, and Demetrio Iero. Edge machine learning for ai-enabled iot devices: A review. Sensors, 20(9):2533, 2020.
[46] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-cfficient training of machine learning models. In International Conference Machine Learming, pages 6950-6960. PMLR, 2020.
[47] Batih-Arrival Model. Maximum matching in the online. In Integer Programming and Com- binatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, volume 10328, page 355. Springer, 2017.
[48] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the nineteenth annual ACM symposium Theory of computing, pages 345-354, 1987.
[49]
Shanmugavelayuthan Muthukrishnan et al. Data streams: Algorithms and applications. Foun- dations and Trends@ Theoretical Computer Science, 1(2):117-236, 2005.
[50] Hariharan Narayanan, Huzur Saran, and Vijay V Vazirani. Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge- disjoint spanning trees. SIAM Journal on Computing, 23(2):387-397, 1994.
[51] James G Oxley. Matroid theory, volume Oxford University Press, USA, 2006.
[52] Jeff Phillips. Coresets and sketches. arXiv preprint arXiv: urXiv: 1601.00077. 2016.
[53] Jeff M Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand hand multiparty communication complexity, made easy. SIAM Journal on Computing, 45(1):174-196, 2016.
[54] Michael Quinn. Parallel computing theory and practice. McGraw-Hill, Inc., 1994.
13

---

[55] Piotr Sankowski. Maximum weight bipartite matching in matrix multiplication time. Theoretical Computer Science, 410(44):4480 4488, 2009.
[56] Monica Scannapieco, Ilya Figotin, Elisa Bertino, and Ahmed K Elmagarmid. Privacy preserving schema and data matching. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 653 66-66,477 2007.
[57] Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
[58] Claude E Shannon. mathematical theory of communication. The Bell system technical journal, 27(3):379-423, 1948.
[59] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan Rellermeyer. A survey on distributed machine learning. Acm computing surveys (csur), 53(2):1-33, 2020.
[60] Lizhe Wang. Jie Tao, Rajiv Ranjan, Holger Marten, Achim Streit, Jingying Chen, and Dan Chen. G-hadoop: Mapreduce across distributed data centers for data-intensive computing, Future Generation Computer Systems, 29(3):739-750, 2013.
[61] Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims are correct as proven in the paper body and appendices.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of the work are given the discussion (see Section 1.4)
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
For every claim and non-trivial logical step formal proof is given.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer:[NA
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuii wwwiicccguie///eeeeeeeeis CoodeSubeiiieeee ssi wswinnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
17

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: ttttps://neutt hwtp:://eeuuuueeeeeee http:/pp..c//ubllcchhcsssstiaaad
Answer: [Yes]
Justification: reviewed the NeurlPS Code Ethics and truly believe this paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Applications of our algorithms given in the introduction and can be considered as (positive and negative) societal impacts and some limitations of the paper are also considered in the discussion. However, this paper discusses theoretical algorithms and does not have a direct broad societal impact out of the academic community.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
21

---

A Zero communication Algorithm for MW-IS
In this section, we give the proof of Lemma 3.1
be matroid of rank k. and let w F. -> IR be weight function. Let Lemma 3.1. Let M = (E, Fm be a partition of E,, and let Bi..... Bm be maximum weight bases of the m E NN, let Fi...., Fm matroids Mn Ei, E Mn Em, respectively. Then, there is a maximum weight basis B of M such that B C UiE(m) B,
Proof. Let B be the set of all maximum weight bases of .M. Note that B o 0 since every matroid has at least one basis. For every E B, define p( B) = (Ure(m) Bi) to be the proximity of B. Let
B" arg max {P(B) B B)
be a maximum weight basis of .M with maximum proximity and choose B" arbitrarily if there is more than one maximum weight basis of maximum proximity. Since B o 0. it holds that B is well-defined. Assume towards a contradiction that (B*) < [3] thus, there is e E B Vieejm) B. Let i E [m]] be the unique index such that E ES and let X {c' B, w (e') 2 w(e)). We use the following strong basis exchange property of general matroids; for more details see, e.g., (57 51].
Claim A.1. Let A, B be two bases of matroid T (F. Then, for every AA B there is b E B \ A such that (A \ {a]) [b) E J and (B (b)) [a] E J.
The next claim follows from repeated application of the exchange property of matroids. We give a proof for completeness.
Claim A.2. Let B be basis and let A be an independent set of a matroid T = (F,J). Then, there is S C B \ A such that S is a basis T.
Proof. We prove the claim by induction on L = [B] - |A]. For the base case, L = O, that is, A is basis of T and the proof follows for S = 0. Assume that for all independent sets A' J with AA' > |A| there is S' C B \ A' such that A' U S" is a basis of T. Now, for the step of the induction thus [B] > [.]]. Since A B E J. by the exchange property of T there is e E B \ A such that A U {e) E J. Let A' = AU {e]; as |A' > |A], by the assumption of the
assume that [B| |A]
induction there S' C B \ A' such that A' U
basis of T. Let S S' U {c). Note that S B \ A and that A U S is basis of T, which gives the statement of the claim.
cycle of matroid T JF.J) is C F such that C & I and for all C' C holds that C' J. We use the following fundamental result on cycles in matroids. The reader is referred to, e.g., 57 51 for more details.
Claim A.3. T = (F.J) be matroid, let A E J, and let f E EFV. CFAA A such that AU $ J. Then, there is exactly one cycle C C AUU()) ofT.
The following is a core claim in the analysis.
Claim A.4. X I
Proof. Assume towards a contradiction that XU E I and consider two cases. First, if B, Uee e I. Since & B, and B, [e) C E, this is immediately contradiction since B, is basis of MnE, E, and cannot be extended. Second, assume that B, U (e) & Z; by the assumption, X X (e) E I. By Claim A.3 there is exactly one cycle C B,Ufe) and since (U(e) E I conclude that there exists some element e" E B, \ (X U {e)) that belong to the unique cycle C. Let B' = (B, U {e}) \ fe"). Then, since e" belongs the unique cycle C, it follows that B I. Since e" B, X it holds that w(e) > w (e") implying that
(B() = (B") + w (e) w (e") w (B.).
\ B₁) it follows that B' is basis of MM E, (any independent set of cardinality equals to the cardinality of some basis is also basis (57 with weight strictly larger than the weight of B.. This is contradiction since B, is maximum weight basis of M n E.. We conclude that X U {e) $ I.
Since |B|| = B&l (recall that E E,
22

---

Using the above claims, we can complete the proof of the lemma. Since B, is basis of M n E, it also follows that B, Σ; thus, as C B;, using the hereditary property it follows that E I. Then, as B is basis of M. by Claim there is S C B X such that X U.S is basis of M.
Claim A.5. EE 1" 1
Proof. Recall that & Usefm] B, and in particular e & X. In addition, assume towards contradic- tion that e E S: thus, X XU [c] S U.S. Since X U a basis of M it holds that X KUS E I; using the hereditary property it follows that U {e) I in contradiction Claim A.4 Overall, conclude that & X KUS and the claim follows.
By Claim A.5 it holds that e E B" (X (XUX) U.. Therefore, by Claim A.1 there is e E (X) B* such that (B* U (e'))) fe} E I. Let = (B* U {('))) {e}. Since S _ B and E (X U US) B it follows that e' X. Therefore, (e') 2 w(e) implying that
w (B*) (e') w(e) w (B*).
Since B = |B*| we conclude that is also a maximum weight basis of M, i.e. B E B. Since
& Ure(m] By and e' E X, where X S B, it follows that (B) p (B*). This is contradiction
the maximality of B" with respect to p and the proof follows.
B Zero communication Algorithm for MWM
In this section, give the remaining proofs from Section 4 STRONG-SET algorithm.
We start with the analysis of the
B.1 Analysis of Algorithm Strong-See
Lemma 4.2. There is an algorithm STRONG-SET that given a graph G (V, E), weight function w: E + RR and a parameter k E IN returns in time O (|E) log [E) a strong set of E, w, k of cardinality most 10- k2
Proof. We give the running time and correctness analysis of Algorithm STRONG-SET below.
Claim B.1. The running time of STRONG-SET is O(m m)..
Proof. Sorting the edges takes (m log m) time. addition, the algorithm makes one pass over the sorted edges and in each iteration additional operations. Clearly, we can compute N(S, v) for every u E V in time O(1) per iteration. We initialize N(S, v) = 0) for every E V; Let E [m]. If the edge
[m]] calculates N(S, u:), N[S, v;) and performs O(1)
(u;, v:) is added to S, we update N(S, u.) < NSS, m4) + 1, (S, v,) + N N(S, v.) + 1, and otherwise, we not need to
update any neighbor set. Thus, each iteration takes O(1) time and overall the running time of the algorithm is O(m log m) + ((m) = O(m log m))
We prove the following invariant of the algorithm.
Claim B.2. For every V it holds that (S, 2 k + 1 at any iteration.
Proof. The algorithm starts with S = 0 and consequently N(S, v) = 0 for every v E V in the first iteration. For some i [m], assume that (SS, v) < 2 + for every v e V before iteration of the algorithm: we show that the above property still holds after iteration i. Consider the following cases. Note that if the algorithm terminated before iteration there is nothing to prove. Thus, assume that the
algorithm did reach iteration i. First, assume that (SS, u,) < 2 1 and N(S, vx) < 2 k; therefore, after iteration it holds that (SS, u;) 2 le (SS, v1) S le and for every x E V (u, v.)
'we note that if the maximum weight W = max.g [w[e)] is large w.r.t. [E], then the running time also depends w. as the running time follows from sorting array of size |E
23

---

it holds that [(S, 2) does not change in iteration i. Second, assume that u(S,u) > 2 k or (S, 14) > 2- Thus, in this case, e, not added S, and S remains the same before and after iteration i. It follows that (SS, v) I 2 k + for every E V in both cases.
We also use the following result of Han
30
Claim B.3. In every graph with M edges and maximum degree A there is a matching of size 6.A43'
4-M
We can now complete the proof, by showing that S, the set returned by the algorithm, is strong set. By Definition 4.1 let e' (u, v) E and consider the following cases. First, if e' S, then e' satisfies the first property of Definition 4. and there is nothing to prove. Then, for the following assume that e' & S. Therefore, one of the following holds.
Let é E [m] such that e; = e' (there exactly one such iteration). Since e, & S, then in iteration of the algorithm one of the following holds.
The algorithm returns S before iteration Then, |S| 2 10. In addition, by Claim B.2 the maximum degree in the induced graph G[V(S) is at most 2 22kk-- + 1. Thus, by Claim B there is a matching in of cardinality at least
4. 5. (2. 11++3
4- 4- 122 +
40 12 4
40 40
40 k
2
2 k.
1
10 1 + 18
18
Since the size of a maximum matching in C(V(S) is always an integer, the above implies that there is a matching M in G[V of cardinality at least 1- Note that w(e) 2 w(e;) for every e S due to the non increasing order of weights of edges inserted S. Therefore, there is matching M S S such that w(e) 2 w(e;) for every e E M, which satisfies the second property of Definition 4.1
The algorithm reaches iteration i. Then, since e, & S. we conclude that N(,, u.) 2 2- (S, v/) 2 2 k + during iteration i. Therefore, there is {ug, &. such that N (S,,)) 2) 2 2 + Note that w(e) 2 w(e;) for every e E S due to the non increasing order of weights of the edges inserted S. Thus, there are 2 k + distinet edges (z, f.)...... (x. (21+++) E such that w((2, 8)) 2 w(ee) for every y E ( (21)+1) This satisfies the third property of Definition 4.1
To conclude the proof, we show a second trivial invariant on the size of S.
Claim B.4. |S| < 10 22 + 1 at the end of the algorithm.
Proof. The algorithm starts where S = 0 and consequently |S] = < 10 1:2 + 1. For some i E [m], assume that before iteration it holds that [S| 10 12 +1: show that either (i) the above property
either holds after iteration or (ii) the algorithm terminates and |S| = 10 k2 + 1. Consider the following cases. Note that, if the algorithm terminated before iteration i assuming |S] 10 k.2 + before the iteration, there is nothing to prove. Thus, assume that the algorithm did not terminate before iteration In iteration consider the following cases. First, e, & S; then, the size of S did not change and the claim follows. Second e; E S; then, |S] increased by 1; therefore, either (i) S still which terminates the algorithm. In both satisfies that |S| < 10 h2 + 1, (ii) |S| 10 k22
cases, the proof follows.
The above implies the proof of the lemma.
B.2 Structural Lemma for matching
Lemma 4.3. Let G = (V. E) a graph, w + be weight function, and k E IN be parameter. Additionally, let m E IN, and let E1,..., Em be partition of E. For all i E [m] let S; be a strong set of FA, w. Then, there is k-maximum weight matching M of such that
M C Uiemm) St.
24

---

Proof. Let M be the set of all k-MWMs of G and w. Note that M * 0 since every graph has at least one matching: the empty set in particular a k-matching with weight 0. For every M M define p(M) M n (Uretm) St to be the proximity of M. Let
M arg max (p(B) B E MM
be a k-MWM with maximum proximity. Assume towards a contradiction that p (M*) < |M*]; thus, there is E M Use|m S. Let i [m]] be the unique index such that E Fgg and let (u, v) for U, V. We use the following claims.
Claim B.5. For every matchings A, B of G such that |A] > 2- |B| there is a E A B such that B U {a} a matching of G.
Proof. Since B is matching of G it holds that [V( S 2- |B] < [A]. Thus, since each E ((A) appears at most once as an endpoint of an edge A, there is (z, A such that x, y $ (BB). Thus, B U {I, y)} is matching of G.
The next claim leads directly to the proof of the lemma.
Claim B.6. There is ex St such that (M* ( is matching of and (e") 2 woe))
Proof. Since S; is strong set of E,, k and e E E2 Si, one of the following holds by Definition 4.1
1. There a matching M S S; of G of cardinality 2 k+ such that for all M it holds
that w(f) 2 wee). Observe that [M] 2 2 k 1 and |M < k; thus, [M] > 2- [M*] and note that both M, M are matchings. Then, by Claim B.5 there is e E M such that (M*) {e}) U {e"} is a matching of G; by the definition of M, it holds that w (e") 2 w(e). Hence, e" implies the statement of the claim in this case.
2. There is x E {u, v} and there are 2
distinct edges (æ, U.)...... (x, (2.++1) E S, such
that for all E [2 ++ +++1 it holds that w ((x, v;)) 2 w ((u, Since IM I l it holds that IV (M*)) S 2 k;; therefore, as each v' E {VI,.... 122841) J can appear as an endpoint of an edge in M at most once, there is j E [2 k + 1] such that vj of V (M*). Thus, (M* (e)) U {(xr, v,)} is a matching of G such that ((r, my)) 2 w(ee). Hence, the proof follows with e* U3).
The above two cases give the statement of the claim.
By Claim B.6 let M (M* {et) {e"}, where ex St such that there is e* E S; satisfying that M is matching of and w (e*) 2 w(e). Thus, M a matching of G such that
w M = w (M*) + w(e") w(e) 2 w (M*).
Hence, M E M. Since ex E Ule|m) Ss and Use(m) S; it follows that (M > p (M in contradiction to the maximality of p (M*).
C Lower Bound for MW-IS
In the following sections, we give the proofs of our lower bounds. These bounds are information- theoretic bounds the number of elements required to be sent from each server in order to solve the given problem optimally.
Theorem 1.3. There is no randomized o(k)a algorithm for k-MW-IS.
Proof. Let any n, m, k E NV \ {0} such that n c k m and k. As before, will be the number of elements, m the number servers, the solution size, and c is an additional parameter.
For any i E [m]) create the i-th server, set of elements E, [f]. .......... [[]
[c]} and let
E Ule(m EG note that EE Morcover, define E [e] [mm) l E [c]} for all [m]
25

---

and j E [k]. For every i.j E [k] and & E [c] define the weight of ej(e] as w (e)]e) = 1 + 2.12 let
W (cf(e) for simplicity. We use the next trivial claim.
Claim C.1. For all f2 [k) such that jn < ja the following holds.
-k-W, J < k. Wa
k- W > (k: - 1) Wa
Proof. Clearly, W = + i
< 1 +
12 2
Wjz: thus, k- W < k. 22- In addition,
2*
j1
k
2 (k. 1) + j2
k W = k + k-
2 k = (k - 1>+1> (k- - 1) +
2 k2
2 k
2 -.6 /
j2
= (k: - 1) + (k - 1) 2. k- (k: 1) 2 (k: - 1) Wz
The third inequality holds because j2 E [k).
Note that the above defines family of MW-IS instances with a ground set E and weight function
w: E + IR that differ by distinct selections of the set of independent sets I S 2 (assuming fixed
n. m, and k). For any X S [k] define
Ix= {s C E
Ss |SFPI= skyj E X and |sn |sn S [A] 1X
(I)
Since E Ex is partition of E, it follows that Ix) is a partition matroid, which is well known to be a matroid (see, e.g.. (T)). For any X S [k]. let 4x be the MW-IS instance defined by the matroid (E, Ix), partition E,,..., E. into servers, and the weight function w E R.
We prove the theorem below. For the sake of brevity, we provide unified proof of the lower bound for both deterministic and randomized algorithms. The necessary small modifications in the proof required for randomized algorithms will appear in parentheses.
Assume towards a contradiction that there is a (randomized) d-data algorithm A for MW-IS for S 2 (for < " For every j E [k]. let S, = (S S E |S|| = k). By ① and Claim C.1 for every j [k] holds that S, is the set of all maximum weight (with respect to w) bases of (E. for all non-empty sets X _ [k] such that j = arg max j"; that is, Sy is the set of optimal solutions of all such instances 4x
Consider the MW-IS instance P(1). Let Q 2 be all sets queried (with probability at least }) by the membership oracle of the central coordinator during the execution of Algorithm A on instance @ ((I). and let E' C E be the (random) collection of elements brought to the central coordinator in this execution. Let
B = Uj E [k] @ + +0}
be all indices on which Algorithm A queried on instance ((1) at least one set in Sy (with probability at least 2). Since A is d-data algorithm for d < k - 2 (for d < k-2), ), it follows that EE| S m d (for all realizations). Recall that E E....., E* are disjoint; thus, there can be at most d indices j E [k] such that Q SS, * 0 (with probability at least 1). In other words. [3] I d < k 2 (for randomized algorithms: [B] < 2 d < k - 2 since for each j E B the expected number of clements taken to the coordinator from E is at least and the overall number of elements is bounded by m d on all realizations). Thus, there is j E [k] \ such that jr & B. Observe that the output of the central coordinator in the execution of Algorithm A on (1) is determined by the set of elements E' and the results of the queries (and the random bits of the algorithm). By [ and Claim C.I] it follows that A returns set in S (with probability at least 4). On the other hand, for the instance (1..)) the set of elements in the central coordinator is also E" and the result of each query except for subsets in Sy. is the same for the membership oracles of I(1} and I(1.5=p. Therefore, since A does not query sets in Sj- also on instance & " (with probability at least 5.) Algorithm A has to return on this instance the same output it returns on instance D (with probability at least 2), which is in Sj. Since S Sy. = 0, it follows that A does not return an optimal solution for instance T (1,1") (with probability least 1 ). in contradiction to the definition of A.
26

---

D Lower Bounds for MWM
We give below our two lower bounds for MWM. We start with the lower bound for unweighted instances.
D.1 Lower Bound for Unweighted Instances
We remark that with factor of 2 the following result can be adapted for randomized algorithms.
Theorem 1.5. For every even k 2 there is no deterministic [==1) data algorithm for k-MCM.
Proof. Let k E IN such that k > 2 and let V = [k] x {1} and U [k] x {2) be disjoint sets of vertices. Let a [k] + [k] be a bijection. Define the bipartite graph G, = U, E.) where
Eg {(v, 1), (u, 2)) E X v u [u))
Let P! ...... P!.....
P be partition of E, into servers such that for all v E [m] it holds that
P = {((x, 1), (y.2)) 2)) E Es x == ==
For every bijection [b]] + k|] define
M, = {((v, 1), (u, 2)) E E x UUU
(2)
We show that M, is maximum (cardinality) matching in Go.
Claim D.1. For every bijection a : [A:] - [k] it holds that Mg is a matching in Go of cardinality k.
Proof. We first show that Mr C E. For every ((v, 1), (u, 2)) V U such that (u), in
particular holds that S (u). This implies that ((v, 1), (u, 2)) E E which consequently means that M, C Fg. It remains to show that M, is matching in Go of cardinality k. Since is bijection, for each v E [k]] there is exactly one u E [k] such that e = (u), and for each u E [k] there exactly one [k: such that (u). Therefore, for each [k] and u such that v (u). the vertices (v, 1), (u, 2) appear exactly once as endpoints in Ma. Thus, Ma is a matching in G. of cardinality k
Claim D.2. Let [K] + [k] be bijection and let F be matching in Go such that [F] 2 k. Then, holds that F MM.
Proof. Consider two cases. First, [F| > k. Then, by the pigeonhole principle there is E V that appears as an endpoint of at least two edges in F, implying that F is not a matching. Contradiction Second, F = k and every (v. 1) V appears exactly one endpoint of an edge in F. Since is a bijection, the inverse function σ [k] - [k] is well-defined. We prove that for each v E [k], by backward induction on v, that it holds that ((v, 1), (a-1(w) 2)) F; since |F| k. it directly follows that F = M,. For the base case, assume that v = k. Then, as ((v, 1), (u. 2)) E F for some [k] (recall that |F| k). by the definition of E, it must hold that e S (u); moreover, (u) E [k] since the range of is also [k:. which implies that 2 (u)). Hence, v o(u) implying (w), and the base case follows. For the step of the induction, assume, for some v E [k].
(o that for every o' E [k] \ [v] it holds that ((v, (a (v), 2)) E F. Let ((v, 1), (v, 2)) E F for some
[k] (again, recall that [F| = i hence there such u). By the definition of Eg holds that < (u). Also, by the assumption of the induction, for every e' E [k] such that v' > v it holds that ((v, 1), (a 21), E F; thus. (u) [K] fo' [k] o' m} [e]. Therefore, v 2 (u)
implying a (u) as required. We conclude that F = M..
Assume towards a contradiction that there is a ( -data algorithm A for unweighted MWM with zero communication. For every bijection o [k] + [k] and v E [m]) let Fy C P" be the set of edges brought by A to the central coordinator from server on input Go; moreover, let F' = Uve(m) Ey be the overall of edges brought to the central coordinator.
Let do [k] +
[k] be the identity function, where (i) = for all i [k].
Claim D.3. There are v" E V and u" [k] such that ((v", 1), (u", 2)) Eoo E.o.
27

---

Proof. Since A ( ) algorithm, observe that Eodo S m
(b 1)
ki-k
Moreover,
k2 + h:
E.o [[((, (u, E x U o o((u)] = Σ (k
2
vE[R]
DE
The second equality holds since op [k] + [k] is a bijection; thus, for each v [k] there are (ke - u +u 1) entries [kc] such that S oo (u). By the above
k + k
k2
k
F
2
2
This gives the statement the claim.
Let o² E V and u" E [k] such that ((v", 1), (u", 2))
E Eog
E% promised by Claim D.3 Let
o² [k] + [k] be the bijection defined for all i E [k] as
u i V' i u
o (i)
otherwise
Clearly, o² is a one-to-one mapping (a bijection). By the definition of P Par recall that ((v",1), 1), (u", 2)) pyt and ((v", 1), (1",, E P..
Claim D.4. Ey Eg
Proof. Since A a zero communication algorithm, Ey", Ex depend only on the algorithm A, and the edge sets of the servers P P respectively. Observe that
p ((.,))) Eg x== =² [((r",1), EV xU v" {o (((,",1),(u,2)) e x 10"00= so((w)
[1(2,1),(x.2)) Ec, +==a = =v)"
Po
The third equality holds since /² (u") v², o =0²) vz
and for every & E [k] {u" vz)
holds that a² a((x)= co(x); thus, for every u E [k]] it holds that o* < <²(uu) (u) if and only if ut S So((u)
Since ((v", 1), (w" ; 2)) E Ero \ E. by Claim D.I and Claim D.2 the only maximum cardinality matching in GG- does not belong 2 and also 2 by Claim D.4 This contradiction that A is an unweighted MWM algorithm with zero communication that in particular finds maximum matching G...
D.2 Lower Bound for Weighted Instances
Theorem 1.4. For every k E IN, there is no randomized o (k²) algorithm for k-MWM.
Proof. Let E IN be the number of servers and let & E IN be the solution size parameter. Assume towards contradiction that there is T - -data algorithm A that solves MWM with zero communication. For every s E [m]. let B, = (U, E,, be complete bipartite graph with vertices on each bipartition; namely, let U {ui..... ) V, {uf {ui...., v be disjoint sets of vertices of cardinality & and let E, U x V, Let W E IR be the weight of all edges in E,. Fix some s [m] and assume that server received E, (with weight W for each edge) as an input, as part of D-MWM problem (note that the input to the remaining servers can be defined in various ways resulting in different instances). Since A is an algorithm for MWM with zero communication. it sends a random subset of edges E C E, to the central coordinator, where E depends only on F., W, and the random bits of the algorithm; that is, it is independent of the input the remaining servers.
Aaa
28

---

2' Claim D.5. For every E [m] and e E Eg it holds that Pr (e E E*) 2
Proof. Fix some E [m]. Assume towards a contradiction that there is e = (u,, vz) E Es such that
(e F²) < 2. Define bipartite graphs B1 = (U w, X, F1), B2 = (V,) Y. Fiz), where X = {z1...., I4 Y {11..... Uk U. V. are disjoint sets of vertices, E1 = {[ug, xx) E [kd [t]. and finally Eg = { ye) l E lh] \ {i}} Let V. U UUV U U and & U, Let the weight of each edge in Ei U Eg 2 W. Let G. = (V., E,) be an MWM instance I, with the distribution E., Ej U Eg into two servers, and an empty set is given as input for the remaining m 2 servers. Let M,- Ei U Eg U {uu,, v.)). Observe that each E V. appears as endpoint of exactly one edge in M,; hence, M, is a perfect matching in G. Moreover, E1 U Eg S Mg. and E, U E are the edges of strictly the highest weight in Eg; therefore, M, is the unique maximum weight matching in G2, Hence, as (u,, uf) & E with probability at least and e = (u, B2) M, the central coordinator cannot return an optimal solution for instance with probability at least 1 We reach contradiction that is required to solve every MWM instance optimally with probability at least 2-
Let G = (V, E) be the graph where V U U V and = UsE[m) Eg. Consider the MWM
instance with the graph G = (V, E) and partition Fi,...., F. into the m servers, where the weight of each edge E is W. Call this MWM instance J. By Claim [D.5] follows that for every 8 E [m] and every 6 E E, it holds that Pr (e E E*) 2 Therefore, overall the expected number of edges m.k= 2 Note that the cardinality
sent to the coordinator on instance J using algorithm A is at least
of maximum matching in G' is at most l since every edge in E. is connected to vertex in U and
in contradiction that A is assumed to be |0|= = k. Thus, it follows that A is 2. &²
k² - -ata
algorithm.
E Parallel Algorithms
We start with some definitions before giving the proof of Theorem 5.1 problem we are given a set of elements E, a weight function w E + I and there is a set C 2 of feasible solutions, which is not necessarily given; the goal find I of maximum/minimum w(S). Clearly, maximum weight matching and matroid independent set of maximum weight are natural subset selection problems. As before, k is used to denote the solution size. Assuming the solution size is given in the input, we denote by I = (E, w. k) an instance of a subset selection problem.
Recall that in subset selection
Theorem 5.1. Let P be subset selection problem that has a zero communication fkk algorithm A in time (g((EE))) for each server E [mi], for some monotonic polynomial functions f.g. where ls is the solution size. Then, there is an Ô (g (f())) time parallel algorithm that given an instance P returns a subset of the elements of size (f(()) that contain an optimal solution. The algorithm is deterministic if A is deterministic.
Proof. Let P be a subset selection problem and let A be a zero communication {lk)-data algorithm in time Ô (g (l)) for each server i, for some monotonic polynomial functions f.g. where k is the solution size, Assume without the loss generality that (k)..g( 2 and k 2 Let (E, w, k) denote an instance of P. where E is a set of elements, w is weight function, and k is the solution size. Define the following algorithm B on instance
Let n E..
1. Let + 0, E
E,
2. While n: > 1: IJ/[K]
(a) Let my- 4.
(b) Partition E into servers E..... Ey where E S 4. f(k) for all i E [my]
(c) Execute A on the instance 1₁ = { (E%, k)
iE(m,]
29

---

(d) Let Ke S Ey be the elements brought from server to the central coordinator Vi [m,]
(e) Update E < UiE(m, 1,, - EE++1 t j+1
3. Return E
Claim E.1. The running time of B instance is Ö(g(f(K)))
Proof. We show two things. First, the number of iterations of the while loop is bounded by Olog r)); that is, the value of j at the end of the algorithm satisfies j = O(logn) Second, each iterations in parallel time of (f)( Fix some iteration j of the while loop such that n, > 4. Observe that | < fk) since A is an -dk) algorithm; thus,
|++1
K
LE /E[m;]
kj
AE xE(m)]
<s(k)
my
-S(K)
4 f(:)
<f())
4 f(k)
<k(k)
n2
n2
4 f(k)
"ij
+
4
4
2
Thus, every iteration j of the while loop besides the iteration (only in the last iteration may hold that n, I 4 < 4- (k))), the number of elements decrease by at least half. We conclude that the number of iterations is therefore bounded by O(log n). Moreover, in each iteration we can partition the elements into m, consecutive segments, each containing 4 f(k) elements besides perhaps the last segment which may contain a smaller number elements. Therefore, by the definition of the running time of each iterations takes
max Ō (g (EEE)
Ö(g(4- f()))) = Ö(g(f(k))
KE[my!
The equalities above rely on f.g being monotonic polynomial. Thus, overall the running time is bounded by (k)()
Claim E.2. Algorithm B returns an optimal solution for I.
Proof. We prove an invariant of the algorithm, that is preserved in all iterations. The invariant is that for every iteration of the while loop of the algorithm, there is optimal solution S of / such that S C Jj- Before the first iteration, holds that E F. and the invariant is trivially satisfied. Assume that the invariant holds before iteration j: thus, there SCC E.. Then, in iteration j we apply A on Iy: since A is a zero communication algorithm for P follows that there is an optimal solution C Ei+1 for Iy. Since there is an optimal solution for that is a subset of E we conclude that an optimal solution for I, is also an optimal solution for Thus, there solution that is subset of the elements brought to the central coordinator. This implies that A returns a subset of elements containing an optimal solution for this last iteration and consequently returns a subset of elements containing an optimal solution for as required.
optimal solution S of such that
C Fi+1 that an optimal solution for T. Overall, it follows that there is an optimal
The proof of the theorem follows from Claim and Claim E.2 since at the end of the algorithm holds that E Okf(k)).
D
30

---

We give below the proofs for our parallel algorithms for k-MWM and MWM. We will use the following algorithm for k-MWM.
Lemma E.3.
25 There is a deterministic algorithm that solves k-MWM in time Ô (k: ((V) + [E])
The algorithm used for the above lemma by Gabow 25 is a variation of the celebrated algorithm of Edmonds [2]] for MWM (a generalization of the Hungarian algorithm (3]]. Specifically, this algorithm is made of at most [E] searches - finding an augmenting path in the graph. Each path augments by one the cardinality of the current matching, and is of maximum weight among all matchings the current cardinality. Thus, after searches, the algorithm solves k-MWM. As Gabow 25 constructs an implementation of a single search of this algorithm in time Ô (V) + |F]), overall & searches give the running time given in the above lemma. We note that the running time of the lemma may be improved using an adaptation of faster algorithms for special cases of MWM (e.g.. smaller weights [26] bipartite graphs (55] 391). However, this requires an adaptation of such an algorithm to k-MWM instead of MWM, which is not always applicable.
Theorem 1.7. There a deterministic parallel Ô (k2) time algorithm for k-MWM.
Proof. By Theorem 1.2 there deterministic zero communication O (k?)- algorithm for maximum weight matching in deterministic parallel time of Ô ([E:)) for each server i. As each edge and its weight can be encoded in Ó(1) bits, each server sends Ô (I:2) bits overall. Thus, by Theorem 5.1 (using the above, i.c., fk) O (k²) and 9 (|Egl) Ô (IE,))), there is a parallel deterministic Ô (k)) algorithm that returns a subset S of Ô (A²) edges containing an optimal solution. Let G' -V', F' S) be the induced graph these edges. Note that E'| |S| Ô (k2); therefore, | < EE| = Ô (I²2). Then, using Lemma E.3 we can solve this residual k-MWM instance in deterministic time Ô (k (IV') + EE))) = Ô (k- (k² k²)) = Ô (k$).
We complete this section with our algorithm for MWM, which uses the above algorithm. Theorem 1.8. There is a deterministic parallel Ô (K+) time algorithm for MWM.
Proof. In this proof, we use the algorithm given in Theorem 1.7 to solve MWM (rather than k- MWM); that is, without the cardinality bound. The approach uses the above algorithm, denote it by A, as a black box, using increasing values of k. Specifically, we run the following algorithm B based on algorithm A (defined in Theorem 1.7p for k-MWM. Assume without the loss of generality that the graph contains at least one edge with strictly positive weight (otherwise the problem is trivial).
1. Initialize k
2. Update h: 1:
3. Execute on the input graph with parameter k;; let ui be the total weight of the solution
4. If Wg S (1+3).....) Wyy
(a) return the highest weight solution found over all iterations q = L,...,k
5. else: Go to Step 2
Let k* opt the minimum cardinality of an optimal solution for the given instance and such an optimal solution, respectively. By the minimality of opt, all edges in opt have strictly pos- iiive weight. Then, during the execution of B, note that for every < k* it holds that wk (14//)((4//)...o0
Wy since there is edge in opt with strictly positive weight that can be added to the solution of iteration k//3 (for every two matchings A, B, where |A] < 2 B there is an edge B that can be added to preserving the matching property, as each vertex an endpoint of at most one edge in matching). Thus, the condition in Step 4 fails for every h < k consequently, during the execution B, we execute A with cardinality 1² in particular, which guarantees that returns an MWM.
31

---

It remains to bound the running time. Each iteration in the execution of algorithm A with cardinality
k takes O (k2) deterministic parallel time using Theorem 1.7 Hence, to conclude, we show that the number of iterations of executing A is O (k*); thus, as in all of these iterations it holds that k O (k*) the proof follows. Let K' be the value of k the end of the algorithm, and it follows that WW S. m [e/3]..... Wy by the stopping condition of the algorithm. Note that for every k
such that [k/3] 2 k" it holds that we I
Wy since opt is a MWM (and A returns
a k -MWM in iteration k", which has a weight equals to the optimal weight), Thus, = O (k*) as required.
F Lower Bound for Shortest Paths
In this section, we show that there is no algorithm that solves the unweighted shortest path problem even for paths of constant length without bringing the entire set of edges to the central coordinator. Intuitively, this differentiates the parameterized zero communication algorithms from FPT algorithms, using the same parameters, since shortest path can be solved in polynomial time and in particular has an FPT algorithm parameterized by the solution size.
Theorem F.1. There is no d-data algorithm for distributed shortest path any = o(EE,), even for paths of length (1), where E, is the set of edges of server i.
Proof. Assume towards a contradiction that there is a zero communication d-data algorithm A for d < [E), where E, is the set of edges of server i. Consider the following instance. Let E IN be a sufficiently large integer and let U = {uI,.... Un V {UI,..., Unh. W = (Wi,..., Wnn be disjoint sets of vertices. Let Euv {(u,, 8;) [e) and Evw S {(V,, We)eee be sets of edges between U, V and V, W, respectively. Let V = U U V U W U {s,t} where s,t UUVU W and let Let = Fuv U Evw U ((s) x U) U ([W) x {t]). Consider a collection of shortest path instances 2 servers (and central coordinator), where the edges are distributed between the server by Euv U ({s) x U) in server and Evw U (W x {(}} in server 2. Note that this is a collection of instances since we did not describe Evw explicitly and only require Evw S {(0), [x))ee(n)) Since d o(Evvv) l) and Euy = 2()) and as is sufficiently large. there is (u,, 22) Euv not brought to the central coordinator from Server in an execution of AA on the instance G (V, E). Since A is one-round algorithm, (u,, 0/) is independent of the set of edges in Server 2, in particular on Fyw. Now, consider the case where Fv {(u,, u:)}- Then, in this case the only path in G between the source to the target is (s, uz), (1;, 0;), (v,; wh)) (w;, t). However, since (44, is not brought to the central coordinator by A the algorithm returns that there is no path between and t, in contradiction the fact that A is an algorithm that requires solve all shortest path instances optimally. We conclude that such an algorithm A does not exist.
32


Reviews:
[{"review_id": "eEKJVeGQsh", "reviewer": "Reviewer_wKn3", "summary": "This paper considers the cardinality-constrained version of the maximum-weight independent set problem of matroids and the maximum-weight graph matching problem under the \"zero communication\" model. In this model, the elements and their weights of the ground set (or the edge set for the matching problem) are partitioned and stored over a multiple number of servers. Every element is in exactly one server. Each server processes its data, and sends a small message to the coordinator, which must use these messages to produce the final output.\n\nFor the maximum-weight independent set problem, the answer is intuitive: each server finds the solution for the matroid restricted to the elements the server has, and sends this solution to the coordinator. Since the problem is cardinality-constrained, each server will send at most $k$ items to the coordinator. The coordinator then finds the solution for the matroid restricted to, this time, the union of the solutions received from the servers. Its correctness is shown using an exchange argument on bases.\n\nFor the maximum-weight matching problem, the message is larger than before: each server sends $O(k^2)$ edges to the coordinator. The intuition is that a server needs to send to the coordinator only those edges that are valuable enough to be one of the k edges chosen in the final solution. As such, an edge is \"useful\" only if every cardinality-$(2k+1)$ matching contains the edge and it is one of the $(2k+1)$ most valuable edges incident with each endpoint. The number of these useful edges is $O(k^2)$, as can be easily seen from an argument that a high-degree graph with many edges must have a large matching.\n\nBased on these two zero-communication results, the paper also gives a parallel algorithm. The algorithm partitions the ground/edge set into small pieces to achieve $\\mathrm{poly}(k)\\cdot \\log(n)$ running time. The paper also presents lower bound results that complement the main results. Finally in the appendix, it also shows that the shortest path problem cannot be solved without sending the entire set of edges to the coordinator.", "questions": "- Although the paper states on Page 3 that the version with the cardinality constraint is more general, using the reduction may blow up the size of the message. It seems that messages with size $O(r)$ is sufficient for the independent set problem, where $r$ denotes the rank of the matroid, but what can we do for the matching problem?\n\n- The model assumes that the matroid structure is known by all servers (at least when restricted to its elements) and the coordinator. How practical is this assumption?\n\nLet me write a few minor comments here too:\n\n- The abstract does not make it clear that k is given as input.\n\n- Line 55, (probability 1): even if an algorithm succeeds with probability 1, it may still be randomized. \n\n- \"pseudo-polynomial\" sounds somewhat misleading. How about saying \"polylogarithmic in the size of the ground set\"?", "limitations": "Yes. While the paper clearly states assumptions it makes for its theoretical results, I discussed some additional concerns above (see Questions).", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strength\n\n- The zero communication model is an interesting model and the paper proposes to consider fundamental problems of combinatorial optimization under this model.\n\n- Presentation is simple and clear.\n\n### Weakness\n\n- (See questions.) The algorithm requires a cardinality constraint to keep the messages small. This seems somewhat artificial.\n\n- As was shown by the paper itself, the model is too restrictive to solve even simple problems like the shortest path problem. It would be nice to see some more arguments why the zero communication model should be studied (e.g. as a means to obtain good parallel algorithms).\n\n- A suggestion: the analysis of the two algorithms, especially the one for the independent set problem, uses techniques that are quite standard. Can we omit some of these arguments from the first nine pages and instead bring some of the matrials in the appendix?", "was_revised": true, "final_justification": "Most of my questions have been satisfactorily answered. Authors also discussed weaknesses I raised, and including these discussions in the paper would greatly improve it.\n\nHowever, for Question 1, we don't seem to have a good answer, according to our discussion during the rebuttal period. I believe that requiring the cardinality constraint as part of input is somewhat artificial, especially considering that it turned out to be not easy to eliminate the assumption for MWM. As such, I find that my concern regarding Weakness 1 hasn't been resolved, and I'd maintain my original rating.", "rebuttal": "We thank the reviewer for their helpful comments and suggestions. We answer their questions below. \n\n- The algorithm requires a cardinality constraint to keep the messages small. This seems somewhat artificial.\n\nAnswer: We distinguish between two settings: (1) where k is provided, and (2) where it is not. Even though our paper is formalized according to (1), we explain below the implications for case (2). \n\n(k can be arbitrary in the zero-comm model): As explained on Page 3 of the paper, in the zero communication model, the fact that each server receives the cardinality constraint is a more general setting and can be assumed without the loss of generality:  We can always set k >= |E|, and the parameter does not affect the algorithm. Yet, all of the results still hold; for example, we would still get an r-data algorithm for MW-IS where r is the rank of the matroid. For MWM with no parameter given, our results are Theta(OPT^2)-data algorithm and a matching lower bound, where OPT is the size of a maximum matching, which gives a tight bound up to a constant. If OPT is sufficiently small, this result shows we can avoid sending all edges to the coordinator. However, if OPT = Omega(n), then we may be forced to send the entire set of edges (in this case, the trivial algorithm of sending all edges matches the lower bound).\n\n(We can avoid sending k in the parallel algorithm): One additional important note that will be highlighted in the paper is that our parallel algorithm works even if the parameter k is not given, so we can tackle arbitrary MWM instances. This can be simply done by running our algorithm with increasing parameters k = 0,1,..., iteratively as long as we return a feasible solution of size sufficiently large (constant factor from k). This augments the running time only by a factor of O(k) and shows that our algorithm works for general MWM instances, rather than only the considered version where a specific parameter is given. We do note that when k = Omega(n), this algorithm is no longer better than the sequential algorithm applied in the last step (any deterministic parallel algorithm can also be used here instead). We will add a more formal version of this discussion to the full version of the paper.     \n\n(k-MWM is a generalization of MWM): The parameter k allows us to tackle the more general problem with the cardinality constraint, which we find interesting, i.e., to apply the algorithm on matroid/graphs with a large optimum size, but we want to restrict ourselves only to a smaller-sized solution. There is a practical motivation for that in, for example,  unbalanced bipartite graphs, which can represent in practice scheduling (many) tasks to k processors, or allocating ads to (a few) advertisement slots, and many more practical examples of unbalanced assignment problems. \n\n\n- As was shown by the paper itself, the model is too restrictive to solve even simple problems like the shortest path problem. It would be nice to see some more arguments why the zero communication model should be studied (e.g., as a mean to obtain good parallel algorithms).\n\t\nAnswer: We believe the zero-communication model is worth studying for several key reasons. First, indeed, as mentioned by the reviewer, we showed its close connection to parallel algorithms. Second, it allows a clean setting to distinguish between the difficulty of problems in a common distributed setting.  We can think of problems that fit well in this model as “communication-efficient” – that can be distributed with small/no communication overhead. Knowing which problems exhibit this property can have practical implications and enable robust algorithms that do not have to process large data on a single processor.\nThus, “easy” problems like shortest paths in a classic computational model that are hard in this model show the usefulness of the model in distinguishing problems according to a restrictive model of communication complexity. \nFinally, the model generalizes well-studied problems in the literature, such as one-direction communication, making it a natural extension of prior work (as discussed in the introduction).\n\n\n\n\n\n- A suggestion: the analysis of the two algorithms, especially the one for the independent set problem, uses techniques that are quite standard. Can we omit some of these arguments from the first nine pages and instead bring some of the matrials in the appendix?\n\nAnswer: We thank the reviewer for this suggestion, and these parts can be moved to the appendix. We will make this change.  \n\n- The model assumes that the matroid structure is known by all servers (at least when restricted to its elements) and the coordinator. How practical is this assumption?\n\nAnswer: For zero communication algorithms, it suffices that each server can compute independence only on the subsets of elements that the server received. Without this assumption, it would be impossible to design a zero-communication algorithm that does not send all elements. \nMost matroids considered in the literature and those with the strongest applications are linear matroids, which can be compactly defined and allow for computing independence, and representing a subset of elements in such matroids requires relatively small memory. \nFor example, consider the important family of graphic matroids, where the elements are edges of a graph and independent sets are acyclic subsets of edges. By taking a subset S of edges to a server i, we only need the server to know the contraction of the given graph to the set of edges S, which is of the same order as the number of edges in S (e.g., if the edges given to a server are only {1,2}, {2,3}, {1,3},  then even if there are n>>3 vertices and m>>3 edges overall in the graph, we can represent this matroid by 3 vertices and 3 edges and verify independence using a cycle detection algorithm on this subgraph only).\n However, there are also non-linear matroids (e.g., the Vamos matroid); a non-linear matroid may require exponential memory (in the number of elements of the ground set) to distinguish correctly between independent sets and non-independent sets. These matroids appear less in practical settings and will require that each server have larger memory. \nThe abstract does not make it clear that k is given as input. \nWe guarantee to add that to the abstract. \n\n\n- Line 55, (probability 1): even if an algorithm succeeds with probability 1, it may still be randomized. \n\nAnswer: We thank the reviewer for this distinction. This will be rewritten. \n\n\n- \"pseudo-polynomial\" sounds somewhat misleading. How about saying \"polylogarithmic in the size of the ground set\"? \n\nAnswer: Thank you for the suggestion. We will make this change as well."}, {"review_id": "6hK65754XD", "reviewer": "Reviewer_urr5", "summary": "The authors consider a low-round distributed algorithm for matroid independent set and maximum weighted matching. Their model of computation is called \"zero-communication\": the input is distributed across machines, the machines report a small message to a central server, and the central server can extract a solution from these small messages. Each message is bounded by size k, where k is the size of the solution. This is very similar to 2-round parallel algorithms, though the second step is more restricted in that it requires a single centralized computation.\n\nThese problems are highly interesting, and have been studied in related models of computation (e.g., 2-player 1-round communication, message passing, etc.), but not this model exactly. It could be said that this model is a tad niche, but these problems are also highly fundamental that improvements in more standard models are exceedingly rare. Also of note is that these algorithms are perfect algorithms, not approximations.\n\nTheir first result is a k-cardinality maximum weight matroid independent set. It is quite simple: find a solution on each machine, send the solution to a central machine, and then the central machine finds the best solution on what it's given. The interesting aspect of this work is the analysis, which carefully examines the properties of independent sets and cycles in matroids to show that this yields a perfect solution. The final algorithm uses O(sqrt(|E|)) deterministic parallel time where |E| is the size of the edge set on a machine by leveraging existing algorithms on their individual machines. The messages passed contain only k elements each.\n\nThe next result uses a similar method for maximum weight matching, though it is insufficient to simply solve the problem on each machine and pass them to a central machine. Instead, they extract what are called \"strong sets\" of size at most 10k^2 + 1 to pass along to the central machine, and the machine can extract the solution from this. Now the messages are slightly larger, but this is also a more difficult problem to solve. The parallel runtime is O(|E|).\n\nThey also show how to adapt these to parallel algorithms - both generally for any subset selection problem and specifically for the two studied problems.", "questions": "1. Theorem 1.1 says that the running time of each i can be computed in ... time. Do you mean that the runtime IS this value? Seems weird to be measuring the runtime of a computation of the runtime.\n\n2. Is Theorem 1.3 supposed to be for all k in N?\n\n3. In the proof of Claim 3.5, you only need to cite Claim 3.4 the first time. The second time you use it, you get B_i' is independent because you took B_i \\cup {e} and removed an element e'' in its only cycle, therefore leaving an independent set. Therefore you're not really using it a second time as implied by how you wrote it. This is correct, right?\n\n4. In the proof of Claim 3.5, once you have B_i' is an independent set, why is it a basis? Is it true that any independent set of a matroid with the same cardinality as a basis must be a basis (due to the second property of matroids), and that means B_i' is a basis?\n\n5. Has this zero-communication model been studied before, or are you introducing it? I think it's well-motivated either way, but I don't know if \"zero-communication\" is a misleading term term, since there is certainly communication, even if it's only from machines to a central server. It's extremely similar to a 2-round parallel algorithm, but instead you have the second round is a single centralized computation instead of more parallel computation. Do you think there's a more appropriate name for this?\n\n6. Your explanation at the beginning of section 4 is a bit lacking. MWM is not a matroid problem, so you can't necessarily transfer the results from section 3. However, the process you describe does sound like a zero communication algorithm. I'm assuming the issue is, if you distribute the graph across machines and find the k-MWM on each machine, you can't then derive an MWM from the set of solutions on across machines. Is this correct? Or otherwise, why is what you've described not a zero communication algorithm?\n\n7. Can you add some intuition of why the strong set helps you determine the maximum weight matching?\n\n8. Can you describe at a high level what the algorithm for 5.1 looks like?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper studies very interesting problems and is generally clear though quite dense at times. The model used is a bit niche (and possibly not studied before), but these are extremely fundamental problems, so progress in more standard models is more difficult. For that reason, I think this work is interesting and important.\n\nMy overall rating comes mostly from gaps in my understanding or explanations in the paper itself. If the authors clear these up, I am happy to increase my score.", "was_revised": true, "final_justification": "I have updated the score to be an accept due to the authors' clarifications. I think it is a technically complicated work in an interesting and practical area of study that deserves acceptance.", "rebuttal": "We thank the reviewer for their helpful comments and suggestions. We answer their questions below.\n\n\n1. Theorem 1.1 says that the running time of each i can be computed in ... time. Do you mean that the runtime IS this value? Seems weird to be measuring the runtime of a computation of the runtime.\n\nAnswer: We thank the reviewer for spotting this typo. Indeed, the text should be rewritten as: “...the running time is…”\n\n2. Is Theorem 1.3 supposed to be for all k in N?\n\nAnswer: In the proof of Theorem 1.3 we use: Let any n,m,k,c be natural numbers such that n = c * k * m and m = k. Thus, the theorem holds for any n,m,k as long as m = k and n = c * k * m, i.e., k is equal to the number of servers and n can be arbitrarily large w.r.t. k. We will clarify this exact formulation of Theorem 1.3 in the paper body. \n\n\n3. In the proof of Claim 3.5, you only need to cite Claim 3.4 the first time. The second time you use it, you get B_i' is independent because you took B_i \\cup {e} and removed an element e'' in its only cycle, therefore leaving an independent set. Therefore, you're not really using it a second time as implied by how you wrote it. This is correct, right?\n\nAnswer: Yes, this is correct: Since we remove an element from the unique cycle, the remaining elements do not induce more cycles, and we can conclude the next line. We will remove the second reference to Claim 3.4 and add some more details. \n\n4. In the proof of Claim 3.5, once you have B_i' is an independent set, why is it a basis? Is it true that any independent set of a matroid with the same cardinality as a basis must be a basis (due to the second property of matroids), and that means B_i' is a basis?\n\nAnswer: Yes, all bases of a matroid have the same cardinality, and all independent sets with cardinality r (r being the rank of the matroid – the cardinality of a basis) are bases. This indeed stems from the exchange property: Assume that there are two bases X, Y of a matroid such that |X| < |Y|; then, by the exchange property there is y \\in Y \\setminus X such that X \\cup {y} is an independent set in contradiction that X is a basis (an inclusion-wise maximal independent set). Moreover, if one of the independent sets with cardinality r is not a basis, it follows that there exists an independent set with cardinality > r, which means there cannot be any basis of cardinality r using the previous argument.\n\n\n5. Has this zero-communication model been studied before, or are you introducing it? I think it's well-motivated either way, but I don't know if \"zero-communication\" is a misleading term, since there is certainly communication, even if it's only from machines to a central server. It's extremely similar to a 2-round parallel algorithm, but instead you have the second round is a single centralized computation instead of more parallel computation. Do you think there's a more appropriate name for this?\n\nAnswer: There are many works on bounded or one-directional communication; some of them can be seen as special cases or variants of the zero communication model. However, to the best of our knowledge, the model in its exact form is introduced in this work. We understand the reviewer's concern regarding the model’s name. The reason for choosing this name is that there is no communication between the servers, and they are only able to send messages to the coordinator without receiving any further information. Alternatives we can suggest are:\n- The “in-star” communication model, where the in-star refers to the communication graph with edges only directed from the servers to the coordinator. \n- One-round communication – where we will need to emphasize that the communication is done only from the servers to the coordinator. \n\n\n6. Your explanation at the beginning of section 4 is a bit lacking. MWM is not a matroid problem, so you can't necessarily transfer the results from section 3. However, the process you describe does sound like a zero-communication algorithm. I'm assuming the issue is, if you distribute the graph across machines and find the k-MWM on each machine, you can't then derive an MWM from the set of solutions on across machines. Is this correct? Or otherwise, why is what you've described not a zero communication algorithm?\n\nAnswer: We agree that the first sentences in Section 4 may be slightly misleading, and we will consider removing or clarifying them better. They intended to provide some intuition for why we need a more complicated algorithm for MWM, unlike MW-IS; the analogue of a basis in the context of MWM can be seen as a maximal/maximum weight matching, even though there are crucial differences. Indeed, the suggested algorithm in the first paragraph of Section 4 does describe an algorithm without any communication between the servers, nor backward communication from the coordinator to one of the servers. However, for this to be a successful zero-communication algorithm, the central server must have an optimal solution for the entire instance. \n\nIt is quite easy to see why this does not hold using the algorithm selecting a single k-MWM in each server: assume that each server i has two edges (u_i,v_i) and (v_i,w_i); thus, there are two matchings in the input of server i:  The first being the singleton matching {(u_i,v_i)} and the second is {(v_i,w_i)}. Intuitively, server i does not know which of the two matchings would be necessary for the central server. If it sends only one of the matchings, it implies that the central server would not be able to create an MWM. \n\nFor example, assume that there are two servers, assume that u_1 = u_2, and assume that all other vertices (i.e., u_1,v_1, w_1, v_2, w_2) are distinct. If Server 1 sends the matching (u_1, v_1) and server 2 sends the matching (v_2,w_2), then the central server cannot construct a matching of size two, even though the union of edges in the two servers contains a size two matching, e.g.,  {(u_1,v_1), (w_2,v_2)}. A zero communication algorithm must be able to obtain an optimal solution in the central server. Thus, sending a single maximal/maximum matching from each server is insufficient for having a zero communication algorithm. \n\n\n7. Can you add some intuition of why the strong set helps you determine the maximum weight matching?\n\nAnswer: We agree with the reviewer that more intuition for strong sets is required. We will add a variation of the following intuition to Section 4. \nIntuition for strong-sets (or, intuition for how to use strong sets to prove Lemma 4.3): In Lemma 4.3, we are given a strong set S_i for each server i and need to prove that the union of S_i’s contains a maximum weight matching (MWM). In the proof of Lemma 4.3, we consider an MWM denoted by M^ that has the maximum size of intersection with the union of S_i’s. If M^ is contained in the union of S_i’s - we are done as the central server can compute M^. Otherwise, there is some element e in M^ and in E_i, for some server i, that does not belong to S_i. Here, we use the fact that S_i is a strong set to find some e^ in S_i such that M’ = M^ \\setminus {e} \\cup {e^} is an MWM. Specifically, recall the definition of a strong set S_i and the edge e, which guarantees one of the following (Definition 4.1):\n- e is in S_i - we already know this is not the case by the definition of e.\n- There is a matching M contained in S_i of (a sufficiently large) cardinality 2k+1 such that every edge in M has higher or equal weight to the weight of e. Thus, as M is sufficiently large and since M and M^ are matchings, there is e^ in M such that M’ = M^ \\cup {e^} is a matching (more specifically, since M^ and M are matchings, each endpoint of M^ can appear at most once as an endpoint of M, and since |M| > 2 |M^| there is an edge in M that can be added to M^ resulting in a matching).  Finally, the weight of M’ can only be higher or equal to the weight of M^ since e^ in M.\n- There is an endpoint x of e and there are 2k+1 distinct edges adjacent to x: (x, v1), . . . ,(x, v_{2 k+1}), each of weight at least the weight of e. Then, in this case, we can use one of these edges as e^ to define M’ = M^* \\setminus {e} \\cup {e^}  analogous to the above case. In more detail, since |M^| \\leq k it has at most 2k endpoints. Therefore, as there are 2k+1 edges as mentioned above, one of these edges e^=(x,v_j) satisfies that v_j is not an endpoint of M^; thus, if we remove e from M^ and add e^, it would induce a matching M’ = M^ \\setminus {e} \\cup {e^} (as the endpoint x replaces its matched endpoint to a new endpoint not in M^), that will have higher or equal weight to the weight of M^.      \nThe above two cases yield a contradiction that M^ is an MWM of maximum intersection with the union of S_i’s. \n\n8. Can you describe at a high level what the algorithm for 5.1 looks like?\n\nAnswer: At a high level, the algorithm for 5.1 can be described as follows (see page 26, line 1067 of the full submission including the appendix for the pseudocode):\n- While the number of given elements is larger than 4*f(k):\n- We partition the elements (in parallel) evenly and arbitrarily into roughly |E^j| / 4*f(k) servers, where $E^j$ is the current set of elements (initialized as E, the given set of elements). \n- Execute the black-box zero-communication algorithm A on the instance induced from the above partition (using the initial given parameter k). \n- Update E^{j+1}, the elements for the next iteration, as the union of elements brought by Algorithm A in the above step to the central server. \n\nThe intuition is that at each iteration, each server applies filtering of the elements it receives: Each server gets roughly  4*f(k) elements and returns only f(k) elements (in parallel to the other servers). Thus, in O(log n) such rounds, we obtain an O(f(k)) size instance, which can then efficiently be solved using some black-box algorithm."}, {"review_id": "Aca5WC71Xy", "reviewer": "Reviewer_SpuD", "summary": "This paper addresses two related problems : Maximum-Weight Matroid Independent Set (MW-IS) and Maximum Weight Matching (MWM) under a 0 communication model, the original problem is partitioned among smaller servers and each server must send a message to a central server such that the union of all messages sent \"contains\" the optimal solution for the overall problem.  The goal is to minimize the size of the largest message sent. \n\nMore specifically, this paper investigates a specialized form of the above problem, parameterized by $k$, which is the \"solution size\". For example, in the case of MWM, this paper is interested in computing the \"k-MWM\", that is, the maximum-cost matching of cardinality $k$. Parameterizing based on this $k$, the authors give simple algorithms for finding $k$-MW-IS and $k$-MWM with maximum message sizes of $k$ and $k^2$ respectively. They also provide lower bounds that show these results are optimal.\n\nAs a direct implication, the authors also obtain bounds for parallel versions of $O(\\sqrt{k}\\log{n})$ for $k$-MW-IS and $O(k^4\\log{n})$ $k$-MWM.", "questions": "I have highlighted several concerns in my discussion above, but, to streamline the response, please specifically address the following, referring to my discussion above for more details:\n(1) Please provide practical justification for why one should expect $k$ to be small for MWM, noting that, when $k \\geq \\sqrt{n}$, your algorithm effectively has no benefit for MWM under either model.\n(2) Please provide clarification regarding your parallel MWM algorithm, in light of my discussion above. In partciular:\n- Why are there $k^2$ total edges on the central server? (How do you account for the total message size from all servers?).\n- What sequential algorithm are you using?\n- Can the Hungarian algorithm (or any other faster sequential algorithm, or even another parallel algorithm) yield better results here?", "limitations": "Nothing to note here.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths : The paper is generally well written, especially with regards to notation definitions, aside from a few things highlighted below. (There is one major concern in the parallel section for MWM that needs addressing). \n\nThe inclusion of lower bounds strengthens the theoretical contribution of this paper, especially because it is not clear whether this exact parameterization (based on $k$) has been investigated before under this model.\n\nWeaknesses : \nDue to being less familiar with the literature on MW-IS, my feedback here is mainly related to $k$-MWM. \n\n- Your algorithm only makes sense when k is very small. However, why should we expect k to be small? I.e., for what practical applications would k ever be small? \n- You mention several applications of, for example, MWM, in a generic sense, and I agree MWM is a very important problem, and solving MWM in a zero communication model is an interesting problem. However, you are solving k-MWM, which is a totally different (probably much easier to solve) problem. As a result, you have to properly motivate *that* specific problem, which I see no discussion of; you only motivate MWM in a somewhat vague / general sense. This is both a practical concern and a theoretical concern, since I don’t think any prior work on the k-MWM variant was cited, and the value of a purely theoretical result is in some sense rooted in its comparison to prior theoretical work.  \nIn particular:\n(1)\tWhat are some examples of practical scenarios (for a NeurIPS audience) that motivate the *k*-MWM variant you propose?\n(2)\tWhy should someone expect that this k-MWM variant is a difficult problem to begin with?\n(3)\tHas the *k*-MWM problem been proposed and studied *outside* of your zero communication scenario? If so, then that would provide a good motivation for the problem to begin with. If not, then why solve it for the zero-communication setting if it’s not interesting in general?\nI would like to elaborate by saying that I am aware of the importance of the “partial p-Wasserstein” distance problem, related also to the “partial optimal transport” problem, which are generalizations of (the minimization variant of) your k-MWM problem, and have applications to a machine learning audience. Optimal cardinality-k matchings are important. My concern is that, for these applications, I don’t think k << n. I would normally expect k to be more like Theta(n), or, at least Omega(\\sqrt{n}) in most practical cases. \nI appreciate the theoretical nature of this work, but I also think that the problem needs stronger practical motivation that relates to a machine learning audience, specifically for motivating that “very small k”.\n\nI think that the literature review is somewhat lacking. The nature of the citations in the related work section seems somewhat disconnected from the nature of this work. The cited related work mentions several results for various communication models, and mainly gives approximation results. However, so far as I can tell, not a single citation in this document addresses the *k*-MWM problem, which is computationally very different from the MWM problem. This absence of prior work cited makes it difficult to assess the theoretical contribution of this work relative to prior work. If nothing else, the Hungarian algorithm is missing, which can compute an optimal cardinality $k$ matching in $O((m + n\\log{n}) * k)$ time.\n\nFinally, I don’t find the parallel result for MWM to be particularly surprising, and I don’t think it is at all tight – this appears as more of a direct by-product of your (optimal) 0-communication model, without any attempt at optimizing it for the parallel setting. I believe that prior (old) work for MWM is much stronger for the parallel setting. For example, see:\n\nOrlin, J. B., & Stein, C. (1993). Parallel algorithms for the assignment and minimum-cost flow problems. Operations research letters, 14(4), 181-186.\n\nThis also cites some work even prior to that. In this line of work, some bounds are given with parallel running times for the perfect matching problem that have running times of polylogarithmic in $n$ (with perhaps some dependency on the largest edge cost as well). Of course, this is a slightly different problem, since it computes a perfect matching, but in my experience, finding perfect matchings is usually more difficult that finding cardinality $k$ matchings for most combinatorial algorithms.\n\nIt is also not clear how your parallel bound for MWM works exactly, as stated. It seems as if you are assuming that the central server ends up with $k^2$ edges, but there are multiple servers sending a message of size $k^2$, right? So shouldn’t the central server end up with a solution much larger than $k^2$, due to accounting for the potentially very large number of servers? Regardless, the way you achieve your parallel bound is collecting a set of edges on the central server and running a (mysteriously unspecified) sequential algorithm. Why run a sequential algorithm instead of some existing parallel algorithm, such as:\n\nGabow, H., & Tarjan, R. (1988, January). Almost-optimum speed-ups of algorithms for bipartite matching and related problems. In Proceedings of the twentieth annual ACM symposium on Theory of computing (pp. 514-527).\nIn general, it seems to me like this parallel section for MWM is not thoroughly treated, and this section is perhaps the weakest part of the paper.\n\nCorrections / Improvements : \n55 : There are multiple types of randomization. One option is that randomization affects the accuracy, and another is that it affects the efficiency (Monte Carlo or Las Vegas). My point being, it’s possible to have an algorithm that is guaranteed optimal with probability 1, but that terminates within the desired time bound, with, say, probability 1/2. Most would still consider that “randomized”, but it is outside of the definition you’ve specified. This is not a major concern, but please add clarification to your model description to clarify the differences between these probability models, and also double check your proofs (especially the lower bounds) to ensure that they continue to apply under the more general notion of “randomized algorithms” if needed. If you are able to use a more general definition of probability, you should do so. Otherwise, you should clearly emphasize the limitation.\n\nIntroduction : Whenever you mention that the edges sent to the coordinator *contain* the optimal solution, be a bit more formal: i.e., say that there exists an optimal solution such that it’s a subset of the provided edges. The reason for this recommendation is that, as written, the reader might wrongly assume that the optimal consists of the optimal rather than being a superset of it. There is nothing incorrect here; simply a matter of readability.\n\n108 : “running time of server i can be computed in “. I don’t think you mean “computing the *running time*”. Reword this.\n\n180 : “In this work, we *showed* tight bounds”  : Due to the placement, this wording seems odd, more like it would be a conclusion. Same again on next line. Showed -> show.\nIntroduction : It is mentioned in multiple places (line 84 and 86) that k is the “solution size”, which seems to imply the “size of the optimal solution”. However, you really mean that k is a “constraint on the set of feasible solutions”. I.e., in your official problem statements, you are considering the maximum weight solution restricted to subsets of size k. I think some parts of the introduction need to be reworded to clarify this distinction, as I found it confusing. (It was correct and complete, but rewording these occurrences will help readability).\n\nLines 377 – 378 : Question about your k^4 bound: Where do you get k^4? Which sequential algorithm are you applying? Are you trying to apply the Hungarian algorithm, and assuming it runs in O(m^2) time? There should be a trivial improvement to this: The Hungarian algorithm takes only $O((m + n\\log{n})*k)$ running time when computing an optimal cardinality k matching. (Just run the first k iterations of it, using Dijkstra’s algorithm as a Hungarian search). So, your running time should simply be roughly ~O(k^3) I think if there are indeed only $k^2$ many edges. I know this to be true for the minimization problem where all costs are non-negative, but it seems like some small modifications to the edge costs can make the two problems equivalent (maximization for all matchings of size at most k). Please double check on this.\n\nRegardless, you have to state what sequential algorithm you are using. Make it explicit!", "was_revised": true, "final_justification": "In the rebuttal discussion, my the authors sufficiently addressed most of my concerns. Some of these require relatively minor edits to the paper, which should be easily doable for a final camera ready version. I have increased my rating accordingly.\n\nAuthors, please address the following in the updated version:\n- Include a more thorough context and discussion of $k$-MWM, both from a theoretical standpoint as well as a practical one. \n- Update the discussion of the $k$-MWM parallel algorithm to include the improved bound, as well as some short additional justification for this bound.", "rebuttal": "We thank the reviewer for their helpful comments and suggestions. We start by answering their direct questions that appear at the end of the review, and then comment on the additional questions that came up in the review text.\n\n(1) Please provide practical justification for why one should expect k to be small for MWM\n\nAnswer: We agree with the reviewer that the paper does not include a sufficient reference to applications for the regime where k << n. We will add a subsection devoted to that to the paper (including the closely related partial optimal transport problem mentioned by the reviewer).\nThe most prominent applications of the maximum matching problems are in bipartite graphs, where we have two sides representing sellers and buyers, tasks and machines, drivers and riders, and many more. A common setting where k is small occurs when the two sides are unbalanced. \n\nFor example, consider a server with k processing slots and a given set of n>>k tasks, each task can be scheduled on some of the processors but potentially not all of them due to compatibility issues such as memory communication bandwidth, or other performance or security reasons. This induces a bipartite graph with k vertices on one side and n>>k vertices on the other side, and the goal of the server is to compute a maximum weight matching (the weight being the price a task is willing to pay to be scheduled on a corresponding processor).\n\n\nAs a second example, consider the problem of ad allocation in internet browsers. In this setting, when a user searches a string, the browser fills the first k places with ads, where there are n>>k ads that are willing to pay for a slot on this search. Each link between an ad x and slot y creates an edge (x,y) with weight being the bid of x, usually multiplied by a click-rate. The goal of the browser is to allocate ads to the slot, maximizing the total price paid – an MWM instance where k is naturally significantly smaller than n. \n\nFurthermore, the study of parameterized complexity, in particular on the solution size, goes beyond practical applications and is a core research field in theoretical computer science. We believe that understanding the parameterized complexity (in various models) of fundamental problems is an important task. \n\n\n\n\n(2) Please provide clarification regarding your parallel MWM algorithm, in light of my discussion above. In particular:\nWhy are there k^2 total edges on the central server? (How do you account for the total message size from all servers?).\n\n\nAnswer: At a high level, our parallel algorithm for MWM can be described as follows:\n- While the number of edges is larger than ck^2 for some constant c (a specific value of c can be smaller than, e.g., 30, which follows from our construction in Section 4):\n- We partition the edges (in parallel) evenly and arbitrarily into roughly |E^j| / c k^2 servers, where E^j is the current set of edges (initialized as E, the given set of edges). \n- Execute our O(k^2)-zero-communication algorithm A on the instance induced from the above partition (using the initial given parameter k). The constant c is sufficiently large so our algorithm is less than a (c/2) k^2-data algorithm. \n- Update E^{j+1}, the elements for the next iteration, as the union of elements brought by Algorithm A in the above step to the central server. \n- When the number of remaining edges becomes at most c k^2, we solve this instance using a sequential algorithm (see the comments below on the selection of this algorithm)\n\n\nThe intuition is that at each iteration, each server applies filtering of the edges it receives: The server gets roughly ck^2 edges and returns only at most half, i.e., (c/2) k^2 edges (in parallel to the other servers). Thus, in O(log n) such rounds, we remain with an instance with only m’ = O(k^2) edges and therefore only n’ = O(k^2) vertices as well. Note that this is a parallel algorithm and not an algorithm in the zero-communication model, allowing us to exploit in each round a zero-communication algorithm with different number of servers: In the first round, the number of servers is roughly |E| / ck^2; in the second round it is |E| / (c/2) k^2, etc., until after O(log n) such round we remain with O(k^2) edges that can be solved efficiently enough using a standard MWM algorithm (see below).  \n\n\n\n- What sequential algorithm are you using?\n\nAnswer: As there is an O(mnpolylog(n)) time algorithm for MWM, we solve the last sequential step of our parallel algorithm in time O(m’ n’) = O(k^4polylog(n)) using the following classic result: \n\nGalil, Z., Micali, S., and Gabow, H. N. 1986. An O(EV log V) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15, 1, 120–130.\n\nThis will be added explicitly in the paper; we completely agree with the reviewer on stating this algorithm explicitly. \n\n- Can the Hungarian algorithm (or any other faster sequential algorithm, or even another parallel algorithm) yield better results here?\n\nAnswer:  As the reviewer rightfully mentioned, there are faster algorithms for special cases of MWM, such as on bipartite graphs or unweighted graphs. Such an algorithm can indeed improve the running time bound for the corresponding special case of the problem, as choosing which sequential algorithm to apply can be done independently of the other components of the algorithm.\nRegarding the Hungarian algorithm, we are aware that it works solely for bipartite graphs and indeed would probably improve the bound to O(k^3 polylog(n)) for bipartite graphs only. This bound is also possible for unweighted graphs due to \n\nS. Micali and V. Vazirani, “An O( \\sqrt(|V|) · |E|) algorithm for finding maximum matching in general graphs,” in Proc. 21st IEEE Symposium on Foundations of Computer Science (FOCS), 1980, pp. 17–27.\n \n\n\n\n\n\n - Has the k-MWM problem been proposed and studied outside of your zero communication scenario?\n\nAnswer: Yes, the problem and its variants have been studied in various computational models. We agree with the reviewer that this should be added to our paper, and we will do so in the full version of the paper. The following are examples of papers studying matching with small maximum matching size on a standard computational model:\n\nLahn N, Raghvendra S, Ye J. A faster maximum cardinality matching algorithm with applications in machine learning. Advances in Neural Information Processing Systems. 2021 Dec 6;34:16885-98.\n\nN. Lahn and S. Raghvendra, A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings, Journal of Computational Geometry, 11 (2021). Special Issue of Selected Papers from SoCG 2019.\n\nAlso, there is abundant research on sparsifying graphs in the context of matching. Specifically, given a graph, a sparsifier is a graph with a smaller number of edges/vertices that preserves the maximum matching size. See the reference below as an example. This topic is mostly relevant when k is relatively small, and is given as additional proof for the necessity of studying this setting of MWM.\n\n Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. Symposium on Simplicity in Algorithms (SOSA), 2019.\n\n\n\n\n\n- “…As a result, you have to properly motivate that specific problem, which I see no discussion of; you only motivate MWM in a somewhat vague / general sense…”\n\n Answer: We agree with the reviewer on further motivating the study of k-MWM rather than MWM. While we do agree with the reviewer on adding applications of MWM with small k, we believe the formulation of k-MWM rather than MWM is natural and is in fact a generalization of the problem by allowing the flexibility of choosing a large value of k. Namely,\n\n(k can be arbitrary in the zero-comm model): As explained on Page 3 of the paper, in the zero communication model, the fact that each server receives the cardinality constraint is a more general setting and can be assumed without the loss of generality: We can always set k >= |E|, and the parameter does not affect the algorithm. Yet, all of the results still hold. \n\n(We can avoid sending k in the parallel algorithm): One additional important note that will be highlighted in the paper is that our parallel algorithm works even if the parameter k is not given, so we can tackle arbitrary MWM instances. This can be simply done by running our algorithm with increasing parameters k = 0,1,..., iteratively as long as we return a feasible solution of size sufficiently large (constant factor from k). This augments the running time only by a factor of O(k) and shows that our algorithm works for general MWM instances, rather than only the considered version where a specific parameter is given. We do note that when k = Omega(n), this algorithm is no longer better than the sequential algorithm applied in the last step (any deterministic parallel algorithm can also be used here instead). We will add a more formal version of this discussion to the full version of the paper.\n\n\n- Finally, I don’t find the parallel result for MWM to be particularly surprising, and I don’t think it is at all tight \n\nAnswer: Our parallel algorithms for MWM is indeed given as a reduction from a black-box zero-communication algorithm and is not overly involved. The running time for MWM is poly(k)*polylog(n); indeed, the exact poly(k) factor may not be tight, though improving it would likely lead to a faster algorithm for general MWM. This algorithm is foremost interesting because it is completely deterministic, unlike existing polylog(n) parallel algorithms (mentioned by the reviewer). We note that removing the poly(k) factor for a deterministic parallel algorithm would solve a central open question of over four decades.\n\nWe will also faithfully change the paper according to the other comments of the reviewer."}, {"review_id": "pwThBRsMFN", "reviewer": "Reviewer_5oXm", "summary": "This paper is interested in the problem of selecting a maximum weight feasible set (independent set in a matroid, matching, etc) using $m$ servers which may only communicate through a central coordinator. The motivation is that perhaps the dataset is huge and needs to be partitioned onto $m$ servers -- what should the servers send the central coordinator to guarantee that the central coordinator can output the right answer? How much data do the servers have to send? How much computation do they individually have to do? The paper gives upper and lower bounds to these questions.", "questions": "Can your results with matroids extend to matroid intersection in any way? That might imply some (bipartite) matching results. I would be interested in knowing that. \n\nYou should cite coresets in your paper. You're basically creating coresets. This is a rich body of work, which may have implications about some of your questions / results. \n\nWhat's the difference between $d$-data and the definition of bandwidth?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Weaknesses: \n\nSection 3's proof is a little easy. But there's sort of a subculture within theory to de-value papers just because the proofs seem easy, so I don't think that's good grounds to reject a paper. Still, you devote almost two pages of valuable space to a proof that really just needs a few paragraphs. I'm much more interested in the proofs of Section 4's results (which are not in the main body, but the appendix). Section 4 proofs should be taking the pages you've devoted to Section 3. For example, I would really like to understand more intuition in Definition 4.1. I see how properties (1) and (3) follow from the algorithm in lines 331 - 337. Can you say a few lines about why property (2) holds (this should be in the main body, not appendices)? Also, include a paragraph as to why the union of strong sets must contain a maximum weight matching. \n\nMy main worry is that Section 4's results seem the most interesting to me, but not enough details of that proof have been added to the main body to convince me the result is true. I think this is critical in a theory focused paper (even though there's only 9 pages the reviewers will be reading). _Note: if you can write more about why your more non-trivial results are true and how you went about proving it, I would be more likely to bump my assessment to a 5_. \n\nThis is a nice theoretical result, and I'm not super sure what it's doing here in NeurIPS over some other theory conference. The application is quite nice. There's no evidence / results about empirical performance though, which I usually like to see in a theory focused paper in a venue like this. \n\nStrengths: \n\nThis is a great model. The proofs I read are clean and correct. The writing is wonderful and pleasant to read. If NeurIPS is interested in accepting more theory like papers, this is a pretty good candidate. Nice job!", "was_revised": true, "final_justification": "The original positive review I gave for this paper stands. The main thing I would definitely want from this paper if accepted is something to address this paragraph from my review: \n\n\"My main worry is that Section 4's results seem the most interesting to me, but not enough details of that proof have been added to the main body to convince me the result is true. I think this is critical in a theory focused paper (even though there's only 9 pages the reviewers will be reading). _Note: if you can write more about why your more non-trivial results are true and how you went about proving it, I would be more likely to bump my assessment to a 5_. \"\n\nIt's not so hard hitting I would make it a strong accept (I would want really interesting proofs and/or experiments for that).", "rebuttal": "We thank the reviewer for their helpful comments and suggestions. We answer their questions below.\n\n\n\n\n- ….For example, I would really like to understand more intuition in Definition 4.1. I see how properties (1) and (3) follow from the algorithm in lines 331 - 337. Can you say a few lines about why property (2) holds (this should be in the main body, not appendices)? \n\n\nAnswer: Intuition on Algorithm Strong-Set (for a formal proof read Appendix A):\nFor the following, consider an execution of the algorithm on a set of edges E with weight function w. The algorithm returns a subset S of edges, and for this subset to be a strong set, consider some edge e = (u,v) in E and let us give the intuition why necessarily at least one property from (1), (2), or (3) holds for e. We consider several cases here.\n     \n -  First, clearly if e is in S, then property (1) holds for e = (u,v). \n- Second, assume that (1) does not hold for e and we shall show why (2) or (3) must hold. Since e is not added to S, by Step (b) of the algorithm we can consider two sub-cases to conclude this intuitive proof: \n\nI. N(S,u) > 2k or N(S,v) > 2k, where recall that N(S,u) and N(S,v) are the number of neighbors of u and v in S respectively. From this case, (3) easily holds since we have taken to S at least 2k+1 neighbors of x in {u,v} and all of these neighbors are with a higher or equal weight due to the order the edges are iterated.\n\n\nII.  The complementary case, where N(S,u) \\leq 2 k and N(S,v) \\leq 2*k. Since the algorithm did not take the edge e to S, the reason has to be since it terminated by the stopping condition of Step (c), i.e., we get that |S| > 10 k^2.  Note that by Step (b) of the algorithm, we do not take edges that increase the degree of any vertex over 2 k+1. That is, for each edge e_i = (u_i, v_i) we have N(S,u_i) \\leq 2 k + 1 and N(S,v_i) \\leq 2 k + 1. Therefore, the edges in S induce a graph with (sufficiently many) over 10 k^2 edges that has a maximum degree of 2 k+1. By a result of Han (reference [20] in our paper, or Claim A.3 to be precise), since there are relatively many edges and the maximum degree is fairly small, there exist a matching in this induced graph of a size of over 2k.\n\n\n\n\n\n\n- Also, include a paragraph as to why the union of strong sets must contain a maximum weight matching.\n\nAnswer: We agree with the reviewer that more intuition for strong sets is required. We will add a variation of the following intuition to Section 4. \n\n\n Intuition for strong-sets (or, intuition for how to use strong sets to prove Lemma 4.3): In Lemma 4.3, we are given a strong set S_i for each server i and need to prove that the union of S_i’s contains a maximum weight matching (MWM). In the proof of Lemma 4.3, we consider an MWM denoted by M^ that has the maximum size of intersection with the union of S_i’s. \n\nIf M^ is contained in the union of S_i’s - we are done as the central server can compute M^. Otherwise, there is some element e in M^ and in E_i, for some server i, that does not belong to S_i. Here, we use the fact that S_i is a strong set to find some e^ in S_i such that M’ = M^ \\setminus {e} \\cup {e^} is an MWM. Specifically, recall the definition of a strong set S_i and the edge e, which guarantees one of the following (Definition 4.1):\n\ne is in S_i - we already know this is not the case by the definition of e.\n\nThere is a matching M contained in S_i of (a sufficiently large) cardinality 2k+1 such that every edge in M has higher or equal weight to the weight of e. Thus, as M is sufficiently large and since M and M^ are matchings, there is e^ in M such that M’ = M^ \\cup {e^} is a matching (more specifically, since M^ and M are matchings, each endpoint of M^ can appear at most once as an endpoint of M, and since |M| > 2 |M^| there is an edge in M that can be added to M^ resulting in a matching). Finally, the weight of M’ can only be higher or equal to the weight of M^ since e^ in M.\n\nThere is an endpoint x of e and there are 2k+1 distinct edges adjacent to x: (x, v1), . . . ,(x, v_{2 k+1}), each of weight at least the weight of e. Then, in this case, we can use one of these edges as e^ to define M’ = M^* \\setminus {e} \\cup {e^} analogous to the above case. In more detail, since |M^| \\leq k it has at most 2k endpoints. Therefore, as there are 2k+1 edges as mentioned above, one of these edges e^=(x,v_j) satisfies that v_j is not an endpoint of M^; thus, if we remove e from M^ and add e^, it would induce a matching M’ = M^ \\setminus {e} \\cup {e^} (as the endpoint x replaces its matched endpoint to a new endpoint not in M^), that will have higher or equal weight to the weight of M^.\nThe above cases yield a contradiction that M^ is an MWM of maximum intersection with the union of S_i’s.\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n- My main worry is that Section 4's results seem the most interesting to me, but not enough details of that proof have been added to the main body to convince me the result is true. I think this is critical in a theory focused paper (even though there's only 9 pages the reviewers will be reading). Note: if you can write more about why your more non-trivial results are true and how you went about proving it, I would be more likely to bump my assessment to a 5.\n\nAnswer: We agree with the reviewer on the need to add more intuition to section 4. We will add a slightly shorter description of the above proof ideas of Lemma 4.2 and Lemma 4.3 to the first 9 pages of the paper. \n\n- …There's no evidence/results about empirical performance though, which I usually like to see in a theory-focused paper in a venue like this.\n\nAnswer: We believe the contribution of this paper is foremost theoretical. However, if the reviewer think the paper would benefit from empirical experiments, we would be happy to consider adding such experiments to the full version of the paper. \n\n\n\n\nQuestions of the reviewer:\n\n- Can your results with matroids extend to matroid intersection in any way? That might imply some (bipartite) matching results. I would be interested in knowing that.\n\nAnswer: This is a great question that can be the subject of follow-up research. Note that bןpartite matching is both a special case of matching in a general graph and of matroid intersection. Hence, our zero-communication algorithm for MWM applies to bipartite matching, and some of our lower bounds (e.g., our lower bound for matching on unweighted instances) applies for bipartite graphs. \nWe do have an idea for an f(k)-data algorithm for matroid intersection, for an exponential function f. It would be very interesting to solve this for a polynomial function, or show a lower bound ruling this out. We will add this question to the discussion. \n\n- You should cite coresets in your paper. You're basically creating coresets. This is a rich body of work, which may have implications about some of your questions / results.\n\nAnswer: We thank the reviewer for this idea and will add a discussion on the relation of our results (specifically on matching) to coresets.\n\n- What's the difference between d-data and the definition of bandwidth?\n\nAnswer: We use the term bandwidth to refer to the maximum number of elements delivered to the coordinator from a single server (perhaps this is somewhat confusing and should be termed differently). An algorithm is a d-data algorithm if the bandwidth is at most d, but not necessarily equal to d."}, {"review_id": "O1qLM3zWp7", "reviewer": "Reviewer_qVML", "summary": "This paper investigates the problem of computing exact solutions for the Maximum Weight Matroid Independent Set (MW-IS) and the Maximum Weight Matching (MWM) problems under a strict zero-communication mode. Each of the m distributed servers processes part of the data and then transmits a message to the central coordinator without any inter-server coordination. The authors provide deterministic algorithms that solve this problem with tight bounds: O(k) per server data for the MW-IS problem and O(k^2) for the MWM problem where k is the solution size. This paper also presents matching lower bounds. The techniques proposed in this paper are further leveraged to derive deterministic parallel algorithms for both of the discussed problems (MW-IS and MWM).", "questions": "1. What happens in the presence of noisy or faulty server inputs? Do the bounds proposed in this paper still hold?\n2. Have the authors tested any of these methods in practice? If so, could they comment on how these deterministic algorithms compare in runtime to the randomized ones discussed in the paper?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- Good theoretical contributions with rigorous proofs and tight bounds for both the algorithm results and the lower bounds. \n- Relevant exploration of a severely constrained communication model.\n- Demonstrates applicability in parallel computing by linking distributed computation to efficient parallelism. \n\nWeaknesses:\n- There weren't any experimental results provided but this is a soft weakness since the authors may think it's not necessary. \n- The initial setting of this paper (zero-communication exact algorithms) is a fairly specialized setting so applicability to the real-world is only lightly motivated. Perhaps it could be further motivated.", "was_revised": true, "final_justification": "The paper makes a clear theoretical contribution in a specialized zero-communication model. The authors rebuttal helped clarify the motivation and addressed some open questions, including possible extensions and the impact of noise. However, the lack of empirical results and limited discussion of real-world relevance remain as minor weaknesses. I still find the work interesting and well-executed on the theoretical side, and I am keeping my original score.", "rebuttal": "We thank the reviewer for their helpful comments and suggestions. We answer their questions below.\n\n\n\n\n- There weren't any experimental results provided, but this is a soft weakness since the authors may think it's not necessary.\n\n\nAnswer: We thank the reviewer for this remark. We believe the contribution of this paper is foremost theoretical. However, if the reviewer thinks the paper would benefit from empirical experiments, we would be happy to consider adding such experiments to the full version of the paper.   \n\n- The initial setting of this paper (zero-communication exact algorithms) is a fairly specialized setting, so applicability to the real world is only lightly motivated. Perhaps it could be further motivated.\n\nAnswer: We agree with the reviewer that we should elaborate more on motivating the model and will do so in the ready version of the paper. We believe the zero-communication model is worth studying for several key reasons. First, as mentioned by the reviewer, we showed its close connection to parallel algorithms. Second, it allows a clean setting to distinguish between the difficulty of problems in a common distributed setting. We can think of problems that fit well in this model as “communication-efficient” – that can be distributed with small/no communication overhead. Knowing which problems exhibit this property can have practical implications and enable robust algorithms that do not have to process large data on a single processor. Thus, “easy” problems like shortest paths in a classic computational model that are hard in this model show the usefulness of the model in distinguishing problems according to a restrictive model of communication complexity. Finally, the model generalizes well-studied problems in the literature, such as one-direction communication, making it a natural extension of prior work (as discussed in the introduction).\n\n\nQuestions of the reviewer:\n\n1. What happens in the presence of noisy or faulty server inputs? Do the bounds proposed in this paper still hold?\n\nAnswer: This is a very interesting question. The noise can be either on (1) the actual element – whether it is given to the server or not, (2) the feasibility – the server may not know exactly which subsets of elements are feasible, and (3) the weights can be noisy. This of course, only makes the problem more difficult, and our lower bounds hold, and the question is if the algorithms given in the paper can be generalized to tackle any of these scenarios. While the answer depends on the exact formulation of the noise model, our bounds are unlikely to hold as is now; it remains an interesting question for follow-up research to rigorously define a variation of our model on faulty servers and give tight bounds for the discussed problems (and more) in such a model. We will add this to the discussion.\n\n2. Have the authors tested any of these methods in practice? If so, could they comment on how these deterministic algorithms compare in runtime to the randomized ones discussed in the paper?\n\nAnswer: As mentioned above, we did not test our results empirically, but we can do so if the reviewer finds it useful. We naturally expect that for small values of k, our parallel running time bounds will be similar to the randomized ones, but degraded for larger values of k approaching n. On the other hand, these randomized algorithms are algebraic and may have practical overheads in contrast to our relatively simple deterministic approach."}]

Author rebuttal:

Meta-review: All reviewers gave positive scores; some appreciated the paper's theoretical contribution and writing quality. The authors successfully addressed several concerns, leading to higher scores. While there were initial doubts about the paper's fit for NeurIPS, the discussion concluded that this should not be a reason for rejection.
Decision: Accept (poster)