Accelerating Matroid Optimization through Fast Imprecise Oracles

Authors: franziska  eberle
felix  hommelsheim
alexander  lindermayr
zhenwei  liu
nicole  megow
jens  schlöter
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:02:17

Abstract: Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models which give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle. We design and analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty oracles, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.

Main paper: 
 introduction: 
 We study the power of a two-oracle model [1, 4, 5, 34, 36] for fundamental matroid optimization problems, which generalize many problems in combinatorial optimization.The two-oracle model is an emerging technique for augmenting a problem where algorithms access information via oracles. The idea is to abstract from subroutines, such as Neuronal Network (NN) inference or graph algorithms, which compute required information from underlying models. Already today the size of such models can be arbitrarily large, and they are expected to grow further in the near future. Thus, computing precise results for each oracle query can be (too) expensive. To mitigate these costs, we assume to have access to a second oracle that is less expensive but gives possibly imprecise answers. Such an oracle can be an efficient heuristic or a smaller NN. The goal is to leverage this fast dirty oracle to obtain enough information in order to query the expensive clean oracle as little as possible. This model has been successfully applied to, e.g., clustering [4, 34] , sorting [1] , priority queues [5] , or data labeling [36] .We study this model in the context of matroid optimization. Matroids play a central and unifying role in combinatorial optimization as numerous classic problems can be framed as matroid basis problems, e.g., problems in resource allocation and network design. A matroid M = (E, I) is a downward-closed set system with a certain augmentation property. It is represented by a ground set E of elements and a family I ⊆ 2 E of independent sets. A basis is an inclusion-wise maximal independent set, and all bases of a matroid have the same size, which is the rank of the matroid; we give formal definitions later. A prominent matroid is the graphic matroid in which, given an undirected graph, every subset of edges that induces an acyclic subgraph is independent.Since |I| can be exponential in n := |E|, algorithms operating on matroids are given access to oracles. The independence oracle answers for a query S ⊆ E whether S ∈ I. Given a weight w e ≥ 0 for every e ∈ E, a classic goal in matroid optimization is to find a basis of M of maximum total weight. In his seminal work, Edmonds [18] showed that the greedy algorithm, which greedily adds elements in order of non-increasing weight, solves this problem using an optimal number of n oracle calls, and, vice versa, that matroids are the most general downward-closed set systems for which this algorithm is correct. For graphic matroids, this greedy algorithm corresponds to the classic algorithm of Kruskal [15] for computing a minimum-weight spanning tree in an edgeweighted graph, which is commonly taught in undergraduate algorithm classes.To motivate the two-oracle model for matroid optimization, we continue with the special case of computing a minimum spanning tree in a large network. This problem arises, e.g., to ensure connectivity in a telecommunication network or as a subroutine to approximate a cheap tour between certain points of interest in a road network. Here, the elements E correspond to the edges of the network. The clean oracle for this graphic matroid has to decide whether a set of edges is cyclefree. While this is doable in time linear in the query size, it can be prohibitively expensive for huge queries. However, there are several ways to design a dirty oracle of reasonable quality:• Networks, especially telecommunication networks, often evolve over time. In this case, the dirty oracle could quickly return cached results of the previous (now outdated) network. • If the network is clustered into many highly connected components that are only loosely connected to each other, such as road networks are clustered around big cities, the dirty oracle can check the query for each (city) component individually. Since there may only be few highways between the cities, this can be quite close to the clean answer. • The dirty oracle could operate in a sparsified subnetwork, e.g., by restricting it to only major roads or data links.We initiate the study of the following two-oracle model for general matroid problems: In addition to the clean oracle of a given matroid M = (E, I), an algorithm has access to a fast dirty oracle. For simplicity, we assume that this oracle belongs to a matroid M d = (E, I d ) and answers for a query S whether S ∈ I d . In fact, the former assumption is not necessary, and we will adapt our results to weaker dirty-oracle variants such as arbitrary downward-closed set systems. We emphasize that the algorithm has no knowledge about the relationship between the dirty oracle and the true matroid M. Finally, we assume for now that calling the dirty oracle is free and discuss mitigations later. Since calling the dirty oracle is free, our goal is to minimize the number of clean-oracle calls required to solve the underlying matroid problem.Our work neatly aligns with the celebrated framework of learning-augmented algorithms [30] , which is receiving tremendous attention [29] . Here, an algorithm has access to a problem-specific prediction and yields a good performance when the prediction is accurate (consistency) and does not perform too bad when given arbitrary predictions (robustness). Ideally, the performance degrades gracefully with the prediction's quality, measured by an error function (smoothness). The type of performance thereby depends on the problem, and could be, e.g., a quality guarantee of the computed solution of an optimization problem, or the running time of an algorithm. The latter is intricately related to the goal of the two-oracle model: the overall running time highly depends on the number of clean-oracle calls. From this perspective, the consistency of an algorithm in the two-oracle model is the worst-case number of clean-oracle calls it uses when the dirty oracle is perfect, i.e., M = M d , while the robustness is the worst-case number of clean oracles independent of the quality of the dirty oracle.More generally, we can interpret algorithms for one model also in the other model and vice versa: On the one hand, our two-oracle model fits into the learning-augmented algorithm framework by considering an optimal solution w.r.t. the dirty oracle as a possibly imprecisely predicted solution.On the other hand, a predicted solution B d ⊆ E can be used to construct the dirty oracle M d = (E, 2 B d ). Thus, our main results are also applicable in the learning-augmented setting.In this paper, we design optimal algorithms in the two-oracle model for the problem of finding a maximum-weight basis (defined later) of a matroid.1. Two-oracle algorithms: For any integer k ≥ 1, there is an algorithm which computes a maximum-weight basis of a matroid M using at mostmin { n -r + k + η A • (k + 1) + η R • (k + 1)⌈log 2 r d ⌉, ( 1 + 1 k) n } many oracle calls to M (see Theorem 3.8) .Here, r is the rank of the matroid, i.e., the size of any basis, and r d the rank of M d . In terms of learning-augmented algorithms, our algorithm has a consistency of at most n -r + k and a robustness of at most (1 + 1 k )n. Moreover, the bound of our algorithm smoothly degrades w.r.t. the quality of the dirty oracle, measured by our error measures η A and η R (the prediction errors). Intuitively, η A and η R denote the number of elements that have to be added to and removed from a maximum-weight basis of M d , respectively, to reach a maximum-weight clean basis; we give a formal definition later. Our algorithm has a tuning parameter k to regulate the level of robustness against a dirty oracle of bad quality; a beneficial feature when the quality of the dirty oracle can be roughly estimated. In Section 2, we present slightly improved bounds for the case of unit weights.Observe that, given a dirty oracle of reasonable quality, our algorithm significantly improves upon the greedy algorithm whenever the rank r is not too small (due to the dependence on n -r), which is always the case for, e.g., graphic matroids in sparse networks like road or telecommunication networks. We further show that this dependence is best possible for any deterministic algorithm for any rank r. Moreover, our algorithm is optimal w.r.t. to the dependence on η A and η R : 2. Tight lower bounds: For every rank r, every deterministic algorithm requires at least n -r + η A and at least n -r + η R ⌈log 2 r d ⌉ clean-oracle calls to compute a basis of a matroid (Appendix B).Yet we present an algorithm which bypasses the dependence on n-r by leveraging the slightly more powerful clean rank oracle (see Section 4.1 for the definition). Note that any algorithm requires at least n clean rank oracle calls in the traditional setting for this problem in the worst case.Noisy oracles, two-oracle model, imprecise predictions. Optimization in the presence of imprecise oracles is a fundamental problem and has been studied extensively, also for submodular optimization [25, 26, 27, 28, 35] , which is connected to matroid optimization via the submodularity of rank functions. The majority of previous work assumes access only to a single noisy oracle, where the noise usually is of stochastic nature. Only recently, a two-oracle model as in our work has been studied from a theoretical perspective. Bai and Coester [1] consider sorting with a clean and a dirty comparison operator. They minimize the number of clean-comparison-operator calls and give guarantees that smoothly degrade with the number of wrong dirty-comparison answers. Similar strong and weak oracles have also been considered by Bateni et al. [4] for the Minimum Spanning Tree problem and clustering, and by Benomar and Coester [5] in the context of priority queues. In contrast to our model, they consider oracles for accessing the distance between two points and not for deciding cycle freeness (graphic matroid). Besides these explicit results on two-oracle models, explorable uncertainty with predictions [20, 21] can also be interpreted as such a model. [2, 3, 12, 13, 19, 22, 23, 33] but also for matroids [8, 9, 14, 24] . Most of these works consider a combined objective optimizing the quality of the second stage solution and the distance between the first-and second-stage solutions. In contrast, we insist on an optimal secondstage solution and minimize the number of clean-oracle calls. Furthermore, to our knowledge, all previous work on matroid problems in these models assumes that the matroid stays the same for all stages but the weights of the elements change, whereas we assume the opposite. Blikstad et al. [7] consider the somewhat similar problem of dynamically maintaining a basis of a matroid, but in a different oracle model. The main results of this paper consider the problem of finding a maximum-weight basis, i.e., given matroid M = (E, I) and weights w e for all e ∈ E, the goal is to find a basis B ∈ B maximizing ∑ e∈B w e . The greedy algorithm solves this problem by iteratively adding elements in non-increasing order of their weight to the solution if possible, i.e., if the solution stays independent in M [18] . Given a weighted ground set, we always assume that the elements of E = {e 1 , . . . , e n } are indexed according to the weight order, i.e., i ≤ j implies w ei ≥ w ej , with ties broken arbitrarily. Given that, for any i and S ⊆ E we define S ≤i = {e j ∈ S | j ≤ i} (S ≥i analogously).Requirements on algorithms and optimal solutions. For all considered problems, we require algorithms to execute clean queries (oracle calls) until the answers to these queries reveal sufficient information to solve the given problem, e.g., find a maximum-weight basis for the clean matroid. More precisely, the queries executed by the algorithm together with the answers must be a certificate that a third party with only access to the clean matroid and without any additional knowledge can use in order to find a provable solution. In particular, an optimal algorithm that knows the answers to all clean queries upfront has to execute queries in order to satisfy the certificate requirement.We refer to the robustness of an algorithm, when bounding the maximum number of clean-oracle calls the algorithm needs for any input instance, independently of the quality of the dirty oracle.Definition of our error measure. We define an error measure that quantifies the quality of the dirty oracle w.r.t. the clean oracle. We define the error measure for the case that the dirty oracle is a matroid and describe in the next section how this extends to arbitrary downward-closed set systems. B d \ R ∪ A ∈ B. Hence r = r d + η A -η R . Also, for all S 1 , S 2 ∈ B d , |A(S 1 )| ≤ |A(S 2 )| if and only if |R(S 1 )| ≤ |R(S 2 )|.Computing a dirty basis upfront. For all our results on computing a (maximum-weight) basis, it suffices to first compute a (maximum-weight) dirty basis and afterwards switch to exclusively using the clean oracle. A similar observation can be made for the results of Bai and Coester [1] on sorting, where it would be possible to initially compute a tournament graph for the dirty comparator and afterwards switch to only using the clean comparator without increasing the number of cleancomparator calls. In Section 4, we observe that separating the usage of the dirty and clean oracles in this way does not work anymore if dirty-oracle calls also incur costs.Counting wrong answers as error measure. Bai and Coester [1] use the number of wrong dirtycomparator answers as error measure. While this is a meaningful error measure for sorting, a similar error measure for our problem does not seem to accurately capture the quality of the dirty oracle. Consider an instance with unit weights, where we have B d ⊂ B. This can lead to an exponential number of wrong dirty oracle answers, but the dirty oracle still allows us to compute a clean basis. For this reason, we use the modification distance as error measure instead.Relaxing requirements on the dirty oracle. We illustrate how to extend the error definition of Section 1.3 to arbitrary downward-closed set systems in the unweighted case: For every inclusion-wise maximal set S of the dirty oracle we compute A(S) and R(S) as before. The addition and removal error are then defined analogously by replacing B * d with the set of all inclusion-wise maximal independent sets (instead of all maximum sets in the unweighted case). Then, all our results in this paper also carry over to this more general setting. Using an error definition with respect to some greedy algorithm on weighted downward-closed set systems, one can also obtain the same result for arbitrary weighted downward-closed set systems. However, for clarity, we only prove our statements for the case that the dirty oracle is a matroid.We begin in Section 2 with a gentle introduction to our techniques and algorithms by studying the simpler problem of computing any basis of a matroid. Then, we extend these ideas in Section 3 and present our main algorithmic results. Finally, in Section 4, we demonstrate how to generalize and adapt our approach to other settings and problems. Many proofs for these sections are deferred to the appendix. In Appendix B, we also included a detailed section on our lower bounds. 
warm-up: computing an unweighted basis: 
 The goal of this section is to give a gentle introduction to our algorithmic methods, which we extend in the next sections. Consider the basic problem of finding any basis of a matroid. Note that without the dirty oracle, we need exactly n clean-oracle calls to find and verify any basis in the worst-case.In the following, we assume that we are given an arbitrary basis B d of the dirty matroid M d , which can be computed without any call to the clean oracle. We first analyze the so-called simple algorithm: If B d ∈ I, we set B to B d . Otherwise, we set B to the empty set. Next, for each element e ∈ E \ B, we add it to B if B + e ∈ I and output B at the end.The idea of the simple algorithm is to only use the dirty basis B d if it is independent in the clean matroid, as we then can easily augment it to a clean basis. Otherwise, we abandon it and effectively run the classic greedy algorithm. Formalizing this sketch proves the following lemma.Lemma 2.1. The simple algorithm computes a clean basis using at most n + 1 clean-oracle calls. Further, if B d ∈ B, it terminates using at most n -r + 1 clean-oracle calls.Surprisingly, in Appendix B, we will see that this simple algorithm achieves a best-possible trade-off between optimizing the cases B d ∈ B and B d / ∈ B at the same time.The simple algorithm discards the dirty basis B d if it is not independent in M. This approach may be wasteful, especially if removing just one element from B d , such as in the case of a circuit, leads to independence. This seems particularly drastic if the clean and dirty oracle are relatively "close", i.e., the error measured by the modification distance is small. This suggests a refinement with a more careful treatment of the dirty basis B d . We propose a binary search strategy to remove elements from B d until it becomes independent. A key feature is that this allows for an errordependent performance guarantee bounding the number of clean-oracle calls by η A and η R , the smallest numbers of elements to be added and removed to turn a dirty basis into a basis of the clean matroid.We )|(1 + ⌈log 2 r d ⌉) + n -r d + 1 oracle calls. We conclude using |R(B d )| ≤ η R and r = r d -η R + η A .The error-dependent algorithm has a good bound on the number of clean-oracle calls (less than n) when η A and η R are small. However, in terms of robustness-i.e., the maximum number of oracle calls for any instance, regardless of the dirty-oracle quality-this algorithm performs asymptotically worse than the gold standard n, achieved by the classic greedy algorithm. This is the case when the dirty basis is equal to E, but the clean matroid is empty: the error-dependent algorithm executes n binary searches over narrowing intervals, using log 2 (n!) ∈ Θ(n log n) clean-oracle calls. By looking closer at the error-dependent algorithm, the special structure of this example can be explained because queries charged to n -r + η A are essentially also done by the greedy algorithm. Hence, they are in a sense already robust. Motivated by the greedy algorithm, another extreme variant of the removal process would be to go linearly through B d and greedily remove elements. This gives an optimal robustness, but is clearly bad if η R is small. For our main result in the unweighted setting, we combine both extremes into a robustification framework and achieve a trade-off using the following key observation. If we have to remove many elements (η R is large), some elements must be close to each other. In particular, if the next removal is close to the last one (in terms of the fixed total order), a linear search costs less than a binary search. Based on this, after a removal, we first check the next Θ(log(r d )) elements of B d linearly for other removals before executing a binary search. This bounds the number of binary searches by Θ( r d log(r d ) ), each incurring a cost of ⌈log 2 (r d )⌉. However, the linear search also incurs some cost. Thus, we further parameterize this idea (see Algorithm 3), and obtain the following main result. Theorem 2.3. For every k ∈ N + , there is an algorithm that, given a dirty matroid M d of rank r d with unknown η A and η R , computes a basis of a matroid M of rank r with at most min{n -r computes an arbitrary maximal independent set B ′ ⊆ B d and then easily augments B ′ to a clean basis. In the weighted setting, however, there clearly can be independent sets B ′ ⊆ B d that are not part of any maximum-weight basis; hence we need to be more careful. Finding such a special independent subset of B d only by removing elements from B d and testing its independence seems difficult: B d itself could be independent, but not part of any maximum-weight basis. However, even in this case, B d can be very close to a maximum-weight basis w.r.t. η A and η R . Therefore, we cannot avoid carefully modifying B d since strategies like the greedy algorithm would use too many queries. Thus, we alternatingly add and remove elements to and from B d . Intuitively, we want to ensure, as the greedy algorithm, that we do not miss adding elements with large weight. Thus, we try to add them as soon as possible. However, even if they are part of every basis in B * , this might result in a dependent current solution unless we now remove elements, which were not detectable before. An example of such a situation is given in Figure 1 . This observation rules out simple two-stage algorithms as used in the unweighted case.+ k + η A + η R • (k + 1)⌈log 2 r d ⌉, (1 + 1 k )n} oracle calls to M.We now present our algorithm. Its full description is shown in Algorithm 1. Given elements E = {e 1 , . . . , e n } in non-decreasing order of their weight, it maintains a preliminary solution, which initially is set to the dirty basis B d . It modifies this solution over n iterations and tracks modifications in the variable sets A ⊆ E\B d (added elements) and R ⊆ B d (removed elements). In every iteration ℓ, the algorithm selects elements to add and remove such that at the end of iteration ℓ its preliminary solution (B d \ R) ∪ A satisfies two properties, which we define and motivate now. Property (i) requires that the preliminary solution (B d \ R) ∪ A up to e ℓ should be a maximal subset of some maximum-weight basis. For the sake of convenience, we introduce the matroid M * = (E, I * ), where I * is the set of all subsets of B * . Then, we can use the following definition. Definition 3.1. A set S is k-safe if S ≤k ∈ I * and for every e ∈ E ≤k \S ≤k it holds that S ≤k +e / ∈ I * .In other words, a set S is k-safe if it is a basis of the truncated matroid of the kth prefix of E. Using this definition, Property (i) requires that at the end of iteration ℓ, the current solution(B d \ R) ∪ A is ℓ-safe.Establishing this property in every iteration will give us that the final solution is n-safe, and, thus, a maximum-weight basis of M. This works because the algorithm does not modify its solution for the ℓth prefix of E after the ℓth iteration.To establish Property (i) after every iteration without using too many clean queries, it also maintains Property (ii): at the end of every iteration the current solution is independent, i.e., (B d \ R) ∪ A ∈ I.We now give some intuition on how our algorithm achieves this. Initially, say for ℓ = 0, before Line 2 Property (i) is fulfilled trivially. For Property (ii), before Line 5 the algorithm greedily adds minimum-weight elements of B d to R that close a circuit in the smallest prefix of (B d \ R) ∪ A (Lines 2-4). This subroutine can be implemented via binary search. To guarantee both properties at the end of iteration ℓ, first observe that Property (ii) holds as long as A and R have not changed in this iteration. However, this might be necessary to establish Property (i). Intuitively, our algorithm wants to act like the classic greedy algorithm to ensure ℓ-safeness. Thus, it checks whether e ℓ should be in the solution by considering its solution for E ≤ℓ . Clearly, if e ℓ ∈ B d \ R or e ℓ ∈ R, there is nothing to modify (Line 6), because the current solution is independent due to Property (ii) for the previous iteration. Similarly, if e ℓ / ∈ B d and the current solution for E ≤ℓ together with e ℓ is independent, we add e ℓ to our solution (Lines 6-7). However, by adding an element, Property (ii) can become false due to an introduced circuit, which we have to break (Lines 8-10). Finally, there might be the situation that e ℓ ∈ B d has been added to R in an earlier iteration, so e ℓ ∈ R. In this Algorithm 1: Find a maximum-weight basis Input:dirty basis B d ⊆ E, matroid M = (E, I) A ← ∅; R ← ∅ {added / removed elements} while (B d \ R) ∪ A / ∈ I do Find the smallest index i s.t. ((B d \ R) ∪ A) ≤i / ∈ I via binary search R ← R + e i for ℓ = 1 to n do if e ℓ / ∈ B d and ((B d \ R) ∪ A + e ℓ ) ≤ℓ ∈ I then A ← A + e ℓ if (B d \ R) ∪ A / ∈ I then Find the smallest index i s.t. ((B d \ R) ∪ A) ≤i / ∈ I via binary search 10 R ← R + e i return (B d \ R) ∪ Acase, we clearly do not want to even consider adding e ℓ again, as queries for verifying this addition cannot be bounded by our error measure. Indeed, removing and re-adding an element cannot be part of any minimal modification distance. Thus, our algorithm skips such elements (Line 6). To justify this, we prove that removing element e ℓ is always necessary, in the sense that there always is a circuit that e ℓ breaks and that cannot be broken by removing elements in later iterations by Lines 8-10. This follows from classic matroid properties for circuits. Formally, we prove in Appendix C:Lemma 3.2 (Property (ii)). At the start (end) of each iteration of Line 5, it holds (B d \ R) ∪ A ∈ I. Lemma 3.3 (Property (i)). At the end of every iteration ℓ of Line 5, (B d \ R) ∪ A is ℓ-safe.Since there are at most n elements in R, the algorithm clearly terminates, and we conclude as follows. To conclude, we use a charging scheme and Lemma 3.5 to derive the following bound; for details, we refer to Appendix C. Lemma 3. 
rank oracles:: 
 There is an algorithm which computes a basis of a matroid M using at most 2 + η A ⌈log 2 (n -r d )⌉ + η R ⌈log 2 r d ⌉ and at most n + 1 calls to the rank oracle of M (Section 4.1).Finally, we initiate the study of extensions, with which we hope to foster future research. 
costly oracles:: 
 In this model, every dirty-oracle call incurs cost 1, and every clean-oracle call costs p > 1. We are interested in minimizing the total cost. We illustrate that this model requires new algorithmic techniques compared to our main setting (see Section 4.2).Another common type of matroid oracles is the rank oracle: Given any S ⊆ E, a rank oracle returns the cardinality of a maximum independent set contained in S, denoted by r(S). Since r(S) = |S| if and only if S ∈ I, our algorithmic results for independence oracles directly transfer. Moreover, for the unweighted setting, we can even reduce the number of oracle calls using a rank oracle, implying that some lower bounds do not translate. For example, givenB d we can compute its rank r(B d ) to obtain η R = |B d | -r(B d) and decide whether to remove elements via binary search or immediately switch to the greedy algorithm. Further, we can improve the dependency on η A if η A is small as we can find the elements to be added via a binary search. Hence, we get the following result.{ n + 1, 2 + η R • ⌈log 2 r d ⌉ + min { η A • ⌈log 2 (n -r d )⌉, n -r d }} clean rank-oracle calls.The full discussion on rank oracles can be found in the appendix. For future work it would be interesting to see if the error-dependency and the worst-case bound can be improved, and if rank oracles can be used to improve the results for the weighted setting.We consider the generalized setting where a dirty-oracle call has cost 1 and a clean-oracle call has cost p > 1 with the objective to minimize the total cost. Lemma B.1 translates to this setting, giving a lower bound p(n -r + 1). Note that the previous results assume that p ≫ 1 in this setup.The main takeaway of this generalization is that it can be beneficial for an algorithm to delay dirtyoracle calls for clean-oracle calls, depending on p and r. This contrasts the previous sections, where we can meet lower bounds by computing a dirty basis upfront.To see this, we consider two algorithms and assume for simplicity that M d = M. The first algorithm starts with E and removes elements via binary search until it reaches an independent set. It only uses clean-oracle calls of total cost p(n -r)⌈log 2 (n)⌉ + p. The second algorithm computes a dirty basis and verifies it, incurring a total cost of n + p(n -r + 1), as M d = M. Thus, for small p and large r, the first algorithm incurs less cost than the second algorithm, which is optimal among the class of algorithms which only initially use dirty-oracle calls. Specifically, having access to rank oracles, one can compute the value of r upfront using one clean-oracle call and, thus, select the better algorithm.In the matroid intersection problem, we are given two matroids M 1 = (E, I 1 ) and M 2 = (E, I 2 ), and we seek a maximum set of elements X ⊆ E that is independent in both matroids, i.e., X ∈ I 1 ∩ I 2 .The textbook algorithm for finding such a maximum independent set is to iteratively increase the size of a solution one by one using an augmenting-path type algorithm until no further improvement is possible. This algorithm has a running time of O(r 2 n) [17] . There are faster algorithms known for matroid intersection, which run in time O(nr 3/4 ) [6] and in time O(n 1+o (1) ) for the special case of two partition matroids [11] . (In a partition matroid M = (E, I), the elements are partitioned into classes C i with capacities k i , and a set S ⊆ E is independent if and only if |C i ∩ S| ≤ k i holds for each C i .) Here, we focus on improving the running time of the simple textbook algorithm by (i) using dirty oracles calls in each of the augmentation steps and (ii) by computing a warm-start solution using an optimal dirty solution, i.e., a feasible solution of a certain size dependent on the error.Matroid intersection via augmenting paths. Our error measure is as follows: We defineη 1 = {F ∈ I 1 d | F / ∈ I 1 } and η 2 = {F ∈ I 2 d | F / ∈ I 2 }to be the number of different sets which are independent in the dirty matroid but not independent in the clean matroid. In order to simplify the setting, we assume here that (i) the dirty matroids are supersets of the clean matroids, i.e., I 1 ⊆ I 1 d and I 2 ⊆ I 2 d , and (ii) that the clean matroids are partition matroids. We note that in general the intersection of two partition matroids can be reduced to finding a maximum b-matching. Proposition 4.2. There is an algorithm that computes an optimum solution for matroid intersection using at most (r + 1)• (2 + (η 1 + η 2 ) • (⌈log 2 (n)⌉ + 2)) clean-oracle calls.Matroid intersection via warm-starting. We show how to exploit the dirty matroids to obtain a good starting solution that is independent in both clean matroids. The idea of warm-starting using predictions has been used for other prediction models in [10, 16, 31] for problems like weighted bipartite matching or weighted matroid intersection. These results are tailored to the weighted setting and do not directly translate to improvements in the unweighted case. As error measure we adjust the removal error for matroid intersection: Lets * d = max S d ∈I 1 d ∩I 2 d |S d | and define S * d = {S d ∈ I 1 d ∩ I 2 d | |S d | = s * d }to be the set of optimum solutions to the dirty matroid intersection problem. We define η r = maxS d ∈S * d min Sc∈I 1 ∩I 2 {|S d \ S c | : S c ⊆ S d }.Our algorithm computes an optimal solution to the dirty matroid, then greedily removes elements until we obtain a feasible solution for the clean matroid. By observing that this reverse greedy algorithm is a 2-approximation in the number of elements to be removed, η r , we obtain the following result. Proposition 4.3. There is an algorithm that computes a feasible solution S ′ c ∈ I 1 ∩ I 2 of size |S ′ c | ≥ s * d -2η r using at most 2 + 2η r • (1 + ⌈log 2 (n)⌉) clean-oracle calls.n -r + k + η A + η R (k + 1)⌈log 2 r d ⌉.Second, we prove the robust upper bound that is independent of η A and η R . To this end, we partition B d = {e 1 , . . . , e r d } into segments separated by the removed elements. Each segment (except the last one, which we treat separately below) contains exactly one removed element at the end. If a linear search (Lines 5 and 10) finds the element to be removed, we call the corresponding segment short. Otherwise, we say it is long.Let the total length of short segments be L short . The cost of a short segment is equal to its length, plus one for the check between the two linear searches in Line 8 if its length is at least k. Thus, the total cost of all short segments is at most (1 + 1 k )L short . Let the total length of long segments be L long . In a long segment, there are exactly k⌈log 2 r d ⌉ queries done by the linear searches (Lines 5 and 10), one query due to Line 8 and at most ⌈log 2 r d ⌉ many queries by the binary search in Line 12. Thus, the total cost of a long segment is at most (k + 1)⌈log 2 r d ⌉ + 1. Moreover, there can be at most Llong k⌈log 2 r d ⌉+1 many long segments. Therefore, the total cost of all long segments is at most (1 + 1 k )L long . Finally, let L last be the length of the last segment, where no elements are removed. If this does not exist we set L last = 0. When the algorithm considers this segment, the condition that B ∪ S ∈ I in Line 8 is true because no further elements are removed afterwards. Regarding the other condition in Line 8, there are two cases. If |S| ≤ k -1, then we do not query B ∪ S ∈ I and terminate the while-loop. Before that, we use exactly L last many oracle calls in Line 5. Otherwise, that is |S| ≥ k, we use k -1 oracle calls in Line 5 and one query in Line 8, which evaluates true and terminates the while-loop. Since k ≤ |S| ≤ L last , we conclude that in both cases we use at most L last many oracle calls during the last segment.Therefore, the total number of queries done in Lines 3-13 is at most( 1 + 1 k ) (L short + L long ) + L last ≤ ( 1 + 1 k ) r d .Together with the n -r d oracle calls in Line 15, we conclude that the total number of oracle calls is at mostn -r d + ( 1 + 1 k ) r d ≤ ( 1 + 1 k ) n.This concludes the proof of Theorem 2.3.We present lower bounds on the worst-case number of clean queries required by any deterministic algorithm. Note that all lower bounds hold even if the dirty oracle indeed follows a matroid. First, we show that, even if M = M d , the worst-case number of clean queries is at least n -r + 1.The following lemma also shows that this is best-possible number of queries for instances with M = M d and the best-possible worst-case bound of n queries cannot be achieved at the same time.Lemma B. | ≤ r-1 and |S ∩C 2 | ≤ 1 is independent in M = M d ,and we denote the set of independent sets by I and the set of bases by B. Each basis of this matroid completely contains C 1 and exactly one member of C 2 . Thus, the rank of M is indeed r. We show that even if the algorithm knows that the underlying matroid is a partition matroid (but it does not know the exact classes), it needs at least n -r + 1 queries.As we require algorithms to show some certificate for a clean basis (see Section 1.3), every feasible algorithm has to verify that (i) someB ∈ B d = B is independent in M and that (ii) B ∪ {e} is not independent in M = M d for every e ∈ E \ B.Consider the instance defined above. To prove (i), an algorithm has to make the oracle call B ∈ I as calls to supersets of B will return false and calls to sets A with B ̸ ⊆ A cannot prove that B is independent.Let e denote the element of C 2 that is part of the basis B selected by the algorithm. To prove (ii), the algorithm has to verify that the elements {e r , . . . , e n } \ {e} are all part of the same class as e and that this class has capacity one. Otherwise, the queries by the algorithm would not reveal sufficient information to distinguish between the matroid M and a potential alternative matroid M ′ that has a third class with capacity one. However, as B would not be a basis for M ′ , the queries by the algorithm must reveal sufficient information to distinguish M and M ′ .To prove that an element e ′ is part of the same class as e, an algorithm has to execute a query A ∈ I with A ∩ C 2 = {e ′ , e ′′ } for an element e ′′ that is already known to be in the same class as e. This is because queriesA ∈ I with either |A ∩ C 2 | = 1, |A ∩ C 2 | ≥ 3 or e ′ ̸ ∈ A would alwaysgive the same answer even for the potential alternative matroid M ′ in which e ′ forms a class of capacity one on its own.In total, this leads to at least n -r + 1 oracle calls. Further, consider the robustness case that the algorithm is given an instance with a dirty matroid as described above and a clean matroid whose only independent set is the empty set. By the above arguments, in order to use only n -r + 1 queries for the case M = M d , the algorithm has to query some B ∈ B d . But this query does not help the algorithm to find out that the only clean basis is the empty set, i.e., it still needs n more queries to show the fact.The next lemma gives a lower bound that justifies the linear dependency on η A in our algorithmic results. In fact, it prohibits improvements over the linear dependency unless the error grows quite large. But even then, we complement the result with a different lower bound that grows stronger with increasing number of errors. Lemma B.2. For every η A ≥ 1, there is no deterministic algorithm that uses less than{ n -r + η A if 1 ≤ η A ≤ n-r d 2 1 + ⌈log 2 ( n-r d η A ) ⌉ if η A ≥ n-r d 2clean queries in the worst-case, even if it knows η A upfront.We prove the lemma by dividing the two different lower bounds into two lemmas, Lemma B.3 and Lemma B.4, which we prove individually. Lemma B.3. For every number of addition errors η A with 1 ≤ η A ≤ n-r d 2 , there is no deterministic algorithm that uses less than n -r + η A clean queries in the worst-case even if the algorithm knows the value of η A upfront and η R = 0.Proof. For the statement of the lemma, we assume that the algorithm has full knowledge of η A . However, we still require that the queries of the algorithm can be used as a certificate for a third party without knowledge of η A to find a provable clean basis. Nevertheless, the assumption that the algorithm knows η A still restricts the query answers that can be returned by an adversary. Consider an arbitrary algorithm for the instance. Depending on the algorithm's oracle calls, the adversary will create a clean partition matroid M = (E, I) with the three classes of elements C 1 = {e 1 , . . . , e r d }, C 2 and C 3 . The elements of N := {e r d +1 , . . . , e n } will be distributed to C 2 and C 3 depending on the algorithm's actions, and the class capacities will be r d for C 1 , 0 for C 2 and η A for C 3 . The adversary will assign exactly η A elements to C 3 , so the only basis of the clean matroid will be C 1 ∪ C 3 and the addition error will be indeed η A .The adversary starts out with empty C 2 and C 3 and later on adds elements to these sets in a consistent manner. We distinguish between two types of oracle calls by the algorithm: Before we move on to type-(i) queries, we give some intuition on the strategy of the adversary for type-(ii) queries. The adversary is designed to reveal the elements C 3 that lead to addition errors as fast as possible if the algorithm executes type-(ii) queries. If the algorithm would only execute type-(ii) queries, then after η A such queries the algorithm would have identified C 3 . Since the algorithm knows η A , it then also knows that none of the remaining elements of N \ C 3 can be added to the basis C 1 ∪ C 3 and, thus, has also identified C 2 . However, in order to query a certificate that proves to a third party without knowledge of η A that the elements of C 2 can indeed not be added, the algorithm will still require |C 2 | additional queries. Therefore, revealing C 3 fast will lead to|C 2 | + |C 3 | = n -r + η A queries ifthe algorithm only executes type-(ii) queries. If the adversary would instead reveal the elements of C 2 first, then the algorithm that only executes type-(ii) queries could use the knowledge of η A to conclude after n -r queries that C 1 ∪ C 3 must be an independent set, as otherwise the number of errors would be too small. In contrast to the previous case, the algorithm can prove this efficiently with a single query to C 1 ∪ C 3 . Thus, revealing C 2 first would allow the algorithm to save queries. For queries of type (i), the adversary will use a different strategy. If the adversary would also start by returning true for type-(i) queries, then every element of N \ C 3 that is part of the query would have to be added to C 3 . Since there are at least two such elements by definition of type-(i) queries, a single query would prove membership of C 3 for at least two elements. This would allow to reduce the number of queries below n -r + η A .Instead, we define the adversary to return false as long as this is possible. To make this query result consistent with the clean matroid, the adversary has to add one of the queried elements to C 2 . If S ∩ C 2 ̸ = ∅ already holds for the queried set S and the current set C 2 , then the adversary can return false without adding a further element to C 2 . Otherwise, we define the adversary to select two elements e 1 , e 2 of (S ∩ N ) \ (C 3 ∪ C 2 ). These elements must exist by definition of type-(i) queries and as we assume S ∩ C 2 = ∅. The adversary will later on add one of e 1 and e 2 to C 2 depending on the algorithms actions. Assume without loss of generality that e 1 is the element that appears first (or at the same time as e 2 ) in another later oracle call. Once e 1 appears in this second query, the adversary adds e 1 to C 2 . If C 2 already contains n -r d -η A elements, then the adversary has to add it to C 3 instead and answer the query accordingly.To show the lower bound, we consider two cases: (1) n -r d -η A elements are added to C 2 before η A elements are added to C 3 and (2) η A elements are added to C 3 before n -r d -η A elements are added to C 2 . If we show that the algorithm in both cases needs at least n -r + η A queries, the lemma follows.Case 1. First, assume the algorithm queries in such a way that n -r d -η A elements are assigned to C 2 before η A elements are assigned to C 3 . Since this is the case, an element e is only added to C 2 if there was a type-(i) query for which the adversary selected {e, e ′ } with e ̸ = e ′ to potentially add to C 2 . By definition of the adversary, each such element e is afterwards added to C 2 while appearing in a second query after the type-(i) query. Thus, e must appear in at least two queries. Note that these two queries are distinct for each e ∈ C 2 because the assignment of e is fixed immediately once e appears in a second query after being selected by the adversary as part of the pair {e, e ′ } in the type-(i) query. In particular, for e ′ to also be added to C 2 , it would need to be selected by the adversary in another type-(i) query and appear in another query afterwards. Since|C 2 | = n -r d -η A , this leads to a total number of queries of least 2 • (n -r d -η A ). As η A ≤ n-r d 2 , we have 2 • (n -r d -η A ) ≥ 2 • (n -r d ) -(n -r d ) = n -r d = n -r + η A .If there exist elements that are never selected by the adversary in response to a type-(i) query, then the adversary must add those elements to C 3 as C 2 is already full. Since the algorithm knows η A , it potentially knows that this is the case and can prove that these elements are in C 3 with a single additional query to C 1 ∪ C 3 .Case 2. Next, assume the algorithm queries in such a way that η A elements are added to C 3 before n -r d -η A elements are added to C 2 . Then, the algorithm must have executed η A type-(ii) queries to sets S where the unique element of (S ∩ N ) \ C 3 was added to C 3 afterwards.Each element e ∈ C 2 must appear in a query to a set S for which each other member is either part of C 1 or C 3 (or eventually added to C 3 ). As the algorithm knows η A , it might be able to conclude that none of the elements in N \C 3 can be added to the independent set C 1 ∪C 3 without actually querying them. However, the queries of the algorithm must be a certificate for a third party without knowledge of η A . Thus, despite knowing that none of these elements can be added, the algorithm still has to prove it using type-(ii) queries. This leads to a total of at least n -r d -η A + η A = n -r + η A queries.Since the previous lemma only holds for errors of at most n-r d 2 , we complement it with the following lower bound for large errors. Fix a number of addition errors η A ≥ 1. The adversary will create a clean matroid M = (E, I) by selecting η A elements from C 2 and add to C 1 instead. Formally, the clean matroid will be a partition matroid with the two classesC ′ 1 = C 1 ∪ A and C ′ 2 = C 2 \ A for some set A ⊆ C 2 with |A| = η A .The capacities for the classes are r d + η A and 0, respectively. Firstly, the algorithm has to query C 1 , otherwise it cannot know whether there's some element in C 1 that should be removed (it does not know η R ). Then, the adversary has to identify the set A (or equivalently C 2 \ A) in order to execute a final query to the clean basis C 1 ∪ A. In order to do so, it has to use queries of the formD 1 ∪ D 2 where D 1 ⊆ C 1 and D 2 ⊆ C 2 . The adversary has ( |C2| η A) choices to decide A, and each of the queries by the algorithm can rule out at most one half of these choices (the adversary can always choose to answer "yes" or "no" depending on which preserves more choices). Thus the algorithm needs at least ⌈log 2( |C2| η A ) ⌉ = ⌈log 2 ( n-r d η A ) ⌉ queries.Note that this bound is weaker than that in Lemma B.3 when η A is small compared to n -r d .We show that there exists an improved algorithm in terms of the error dependency if η R = 0 and η A ≥ k 0 + k 1 + k 2 = n-r d 2 .Hence, the number of queries executed by the algorithm is at most3 • (k 0 + k 1 ) + k 2 = n -r d 2 + 2k 0 + 2k 1 ≤ n -r d 2 + 2(2k 0 + k 1 ) = n -r d 2 + 2(n -r d -η A ) ≤ n -r d 2 + 2 ( n -r d 4 -1 ) = n -r d -2 = n -r + η A -2.The last inequality uses our assumed lower bound on η A .We note that there is a straightforward example which shows that this analysis is tight, where in particular k 0 = 0 and the algorithm alternatingly adds two and one elements.Finally, if |N | is odd, we have one additional query in Step 1 of the algorithm. Thus, the number of queries is in this case at most n -r + η A -1.Finally, we justify the logarithmic error-dependency on the removal error η R in our algorithmic results for small η R . Lemma B.6. For every η R ≥ 1, there is no deterministic algorithm that uses less than n -r Fix a number of removal errors η R ≥ 1. The adversary will create a clean matroid M = (E, I) by selecting η R elements to remove from C 1 and add to C 2 instead. Formally, the clean matroid will be a partition matroid with the two classes+ 1 + ⌈log 2 ( r d η R ) ⌉ cleanη R upfront. Further, if η R ≤ r d 2 k for some fixed k ≥ 0, the bound is at least n -r + 1 + ⌈η R (log 2 r d -k)⌉.C ′ 1 = C 1 \ R and C ′ 2 = C 2 ∪ R for some set R ⊆ C 1 with |R| = η R .The capacities for the classes are r d -η R and 0, respectively. Consider an arbitrary deterministic algorithm. For each e ∈ C 2 = C ′ 2 \ R, the algorithm has to query a set S with S ∩ C 2 = {e} and S \ {e} ⊆ C ′ 1 , as this is the only way of verifying that the elements in C 2 cannot be added to the basis. Even if the algorithm knows that η A = 0, it still has to prove this by using such queries. This leads to at least n -r d ≥ n -r + 1 queries.For the elements in R, the algorithm has to do the same. However, it does not know which elements of C 1 belong to R and which do not. Instead, the algorithm has to iteratively query subsets of C 1 until it has sufficient information to identify the set R. Note that queries to sets containing members of C 1 and C 2 always return false independent of whether the queried members of C 1 belong to R or not, which means that such queries do not reveal any information helpful for identifying R.We can represent each such algorithm for identifying R as a search tree. A vertex v in the search tree represents the current state of the algorithm and is labeled by the set P v ⊆ C 1 of elements that still could potentially belong to R given the information already obtained by the algorithm and a family of subsets S v such that each S ∈ S v is guaranteed to contain at least one member of R given the algorithm's information. For the root r of the search tree, we have P r = C 1 and S r = {C 1 }. As the algorithm executes queries to sets S ⊆ C 1 , it gains more information about which elements could potentially belong to R. Thus, each vertex v in the search tree has (up-to) two successors v ′ , v ′′ with different labels P v ′ and P v ′′ depending on the answer to the query executed by the algorithm while being in the state represented by v. The algorithm can only terminate once it reaches a state u in the search tree with |P u | = η R , because only then it has identified the set R = P u . We refer to such vertices as leaves. Since, depending on the query results returned by the adversary, each subset of S ⊆ C 1 with |S| = η R could be the set R, there are at least( |C1| η R ) = ( r d η R ) leaves.The search tree representing the algorithm has a maximum out-degree of two and at least( r d η R) leaves, which implies that the depth of the search tree is at least ⌈log2 ( r d η R ) ⌉.Since the adversary can select the query results in such a way that it forces the algorithm to query according to a longest root-leaf-path, this implies that the algorithm needs at least ⌈log 2 ( r d η R) ⌉ queries to identify R.In total, the algorithm has to execute at least n -r+ 1 + ⌈log 2 ( r d η R ) ⌉ queries. Note that ( n k ) ≥ n k k k for any positive integer n, k with k ≤ n. If η R is small compared to r d , say, η R ≤ r d 2 k for some constant k ≥ 0, then log 2 ( r d η R ) ≥ η R (log 2 r d -k).C Proofs omitted from Section 3 If in iteration ℓ = j, the condition in Line 6 is not satisfied, then A, R do not change and we are done. The remaining case is that e j is added to A. If then (B d \ R) ∪ A ∈ I, Line 8 evaluates false and we are done. Otherwise, that is, (B d \ R) ∪ A / ∈ I, we execute the binary search in Line 9 and add an element to R. To conclude also this case, we argue that at the end of this iteration we have that (B d \ R) ∪ A ∈ I. Adding e j to our solution, which by induction hypothesis was independent before, creates at most one (in this case exactly one) circuit in our solution (cf. Theorem 39.35 in [32] ). Since the binary search in Line 9 detects exactly this unique circuit, an element of the circuit is added to R, which breaks the circuit and makes (B d \ R) ∪ A independent again.d \ R) ∪ A is ℓ-safe.Proof. First, we introduce some notations. Let A k , R k be the sets represented by the variables A, R at the end of iteration k (equivalently at the beginning of iteration k + 1). We prove by induction over the iterations of Line 5 that the statement holds at the end of every iteration. First, note that every set is 0-safe, thus, this also applies to our solution before the first iteration of Line 5. Let ℓ ∈ {1, . . . , n}. We write B = (B d \ R ℓ-1 ) ∪ A ℓ-1 for our preliminary solution after iteration ℓ -1, and B ′ = (B d \ R ℓ ) ∪ A ℓ for the solution after iteration ℓ. By induction hypothesis, we can assume that B is (ℓ -1)-safe, and we now prove that B ′ is ℓ-safe. To this end, we distinguish three cases concerning element e ℓ .In the first case we assume that e ℓ / ∈ B d , Then, the algorithm makes one more query (Line 6). If B ≤ℓ + e ℓ / ∈ I, it must hold that B is ℓ-safe, and since in this case B = B ′ , we are done. Otherwise, that is, B ≤ℓ + e ℓ ∈ I, we add e ℓ to A and, thus, B ≤ℓ + e ℓ = B ′ ≤ℓ . We now prove that B ′ ≤ℓ is part of a maximum-weight basis, which implies that B ′ is ℓ-safe. Let B * be some optimal basis such that B ≤ℓ-1 ⊆ B * . Such a basis exists because B is (ℓ -1)-safe by assumption. If e ℓ ∈ B * , then also B ′ ≤ℓ ⊆ B * , and we are done. Otherwise, that is, e ℓ / ∈ B * , there must be a circuit C in B * + e ℓ .Moreover, C must contain some other element e k with k > ℓ, because B ′ ≤ℓ ∈ I due to Lemma 3.2. By the ordering of the elements, w e ℓ ≥ w e k , and therefore B * + e ℓ -e k is a maximum-weight basis. Further, it contains B ′ ≤ℓ . Thus, we conclude B ′ ≤ℓ ∈ I * . For the second case, suppose that e ℓ ∈ B d \ R ℓ-1 . Thus, the condition in Line 6 evaluates false, and we have B = B ′ . Thus, B ′ ≤ℓ = B ≤ℓ-1 + e ℓ , and we can prove analogously to the previous case that B ′ ≤ℓ in included in a maximum-weight basis. Finally, it remains the case where e ℓ ∈ R ℓ-1 . In this case, e ℓ is added to R in some earlier iteration ℓ ′ < ℓ, and, thus, e ℓ / ∈ B ′ . Also, B = B ′ because e ℓ ∈ B d . We show that B ′ ≤ℓ-1 + e ℓ is dependent, which implies that B ′ is ℓ-safe. To this end, we prove for q = ℓ ′ , . . . , ℓ -1 the invariant that ((B d \ R q ) ∪ A q ) ≤ℓ-1 + e ℓ contains a circuit C such that e ℓ ∈ C and that e ℓ is the element with the largest index in C. Note that the invariant holds at the time e ℓ is added to R in iteration ℓ ′ due to Lines 3 and 10. Suppose the invariant holds for q = j -1, witnessed by circuit C 1 . We now prove the invariant for q = j.If C 1 ⊆ ((B d \ R j ) ∪ A j ) ≤ℓ-1 + e ℓ ,we are done. Otherwise, the algorithm must have added element e j ∈ C 1 to R in iteration j. By Lines 2 and 9, e j is the element with largest index in a circuit C 2 in (B d \ R j-1 ) ∪ A j . As e ℓ has the largest index in C 1 by induction hypothesis and e j ∈ C 1 , we conclude j < ℓ. Thus,e ℓ / ∈ C 2 . Since e j ∈ C 1 ∩ C 2 and e ℓ ∈ C 1 \ C 2 , there exists a circuit C 3 ⊆ (C 1 ∪ C 2 ) \ {e j } such that e ℓ ∈ C 3 (cf.Theorem 39.7 in [32] ). In particular,C 3 ⊆ ((B d \ R j ) ∪ A j ) ≤ℓ-1 + e ℓand e ℓ has the largest index in C 3 . This makes C 3 a witness for the invariant for q = j, and, thus, concludes the proof. Hence, we assume from now on I ̸ = I * for the sake of contradiction. Let κ < n be the number of distinct weights. We partition E according to weight into weight classes of elements with the same weight. We use subscript i on any set of elements to refer to the subset of elements of the ith weight class. Since I is n-safe by Corollary 3.4, both I and I * have maximum weight. Using again the observation that A ∩ R = ∅, we have that|R i | -|A i | = |R * i | -|A * i | and |I i | = |I * i | (1)for every i ∈ [κ].We EQUATION)That is, R * and Ã * are minimum modification sets.Let i be the weight class of the largest weight such that Otherwise, it must hold that A * i ⊆ A i , and there must exist an element e ∈ (II i ̸ = I * i . Since |I i | = |I * i |, we have I * i \ I i ̸ = ∅. If there exists an element e ∈ (I * i \ I i ) ∩ A * i ,* i \ I i ) ∩ ((B d ) i \ R * i ). If A * i = A i , there must exist an element e ′ ∈ ((B d ) i \ R i ) ∩ R * i such that I * -e + e ′ ∈ B * byFollowing the proof of Lemma B.6, the adversary can force the algorithm to use ⌈log 2 ( r d -1) ⌉ = ⌈log 2 (r d -1)⌉ oracle calls to find the element ē. If we pick r d as a sufficiently large power of two, we get ⌈log 2 (r d -1)⌉ = ⌈log 2 r d ⌉.Note that queries containing e n-1 do not contribute to finding ē as they always return false. This implies that the algorithm needs an additional query containing e n-1 to prove that (B d \ {ē}) ∪ {e n-1 } is not independent in the clean matroid. Combined with the two queries to B d and P and the ⌈log 2 r d ⌉ queries for finding ē, this already leads to 3+⌈log 2 (r d )⌉ queries. Any additional query would imply that the algorithm executes strictly more queries than the bound of the lemma.The algorithm however needs one additional query to verify that B d \ {ē} is independent. Note that the query B d \ {ē} could in principle be executed during the search for ē. However, the adversary would only answer true to a query of form B d \ {e} for any e ∈ B d if e is the only remaining choice for ē since returning true to that query would reveal e = ē, which the adversary never does. However, if e is the only remaining choice for ē, then algorithm already knows ē, which means that the query is not counted within the ⌈log 2 r d -1⌉ = ⌈log 2 r d ⌉ for finding ē. In total, this leads to4 + ⌈log 2 r d ⌉ > 3 + ⌈log 2 r d ⌉ queries.Case 2: The algorithm queries B d first. Then, the adversary will return true, which is consistent with the dirty matroid. In order to avoid three queries in case that the adversary chooses M = M d , the algorithm has to query P next. The adversary will answer that P is indeed independent and choose E as the only basis of the clean matroid. Afterwards, the algorithm has to query also E to prove that E is indeed independent. This leads to a total of three queries. However, we have n -r = 0, η A = 1 and η R = 0, which implies n -r+ η A + ⌈log 2 (r d )⌉ • η R + 1 = 2 < 3.Theorem 3.8. For any k ∈ N + , there is an algorithm that, given a dirty matroid M d of rank r d with unknown η A and η R , computes a maximum-weight basis of a matroid M of rank r with at mostmin{n -r + k + η A • (k + 1) + η R • (k + 1)⌈log 2 r d ⌉, (1 + 1 k )n} oracle calls to M.Proof. To prove this theorem, we consider Algorithm 2. It is not hard to see that the correctness of Algorithm 2 follows from the correctness of Algorithm 1. We now prove the stated bound on the number of clean-oracle calls.The algorithm uses clean-oracle calls only in Lines 5, 8, 9, and 11. We separately prove the errordependent bound and the robustness bound.Proof of the error-dependent bound. We start by bounding the number of queries in Lines 5, 9, and 11:• In Line 5, each element e ∈ E \ B d incurs a query and the total number of such queries is n -r d .• In Line 11, the binary search is incurred by elements in R. Thus, the total number of such queries is at most |R|⌈log 2 r d ⌉.• To bound the number of queries in Line 9, we observe that whenever q reaches k -1, we execute one such query, unless ℓ = d max , because then we know that ((B d \ R) ∪ A) ≤ℓ = (B d \R)∪A and the independence follows because the condition in Line 10 evaluated false. Therefore, it suffices to bound how often q reaches k -1. Note that q can be decreased to 0 only in Lines 8, 9, and 12. Lines 8 and 12 correspond to an element in R and Line 9 sets the variable LS to false which must have been set to true by Line 2 or Line 5 (in which case we added an element to A). Hence, we conclude that the number of times q reaches k -1, which upper bounds the number of queries executed in Line 9, is at most|R| + |A| + 1.In total, the number of clean queries in Lines 5, 9, and 11 is at mostEQUATIONIt remains to bound the number of queries executed in Line 8. To this end, we first show q ≤ k -2 when the algorithm terminates. This follows from the fact that at the end of the algorithm we have a feasible solution by Corollary 3.4. Assume for contradiction that q ≥ k -1 at the end of the algorithm. Then at some previous iteration, we entered Line 9. Consider the iteration with largest index in which we entered Line 9. Note that the if-statement in Line 9 has to be false as otherwise q was set to 0 again. But, in particular, this implies that the current solution (B d \R)∪A in this iteration is not independent and hence the algorithm must enter Line 8 or Line 11 at some later iteration in order to output an independent solution. This implies that q is set to 0 again, a contradiction.Observe that q is increased by 1 before each query executed in Line 8 and the number of times q is increased is at most the total decrease of q plus k -2 (the value of q at the end of the algorithm).As shown before, q can only be decreased by k -1 in Line 9 which happens at most |A| + 1 times, or decreased by at most k⌈log 2 r d ⌉ in Lines 8 or 12, which happens |R| times. To be more precise, Line 9 is executed at most |A| (rather than |A| + 1) times if q > 0 at the end of algorithm. This follows from the fact that q > 0 implies LS = true at the end of the algorithm, which means Line 9 is not executed after the last execution of Line 5.To finally bound the number of queries in Line 8 we distinguish whether q = 0 or q > 0 holds at the end of the algorithm. If q > 0 at the end of the algorithm, then the number of queries executed in Line 8 is at most|A| • (k -1) + |R| • k⌈log 2 r d ⌉ + k -2,where the additive k -2 are caused by the final at most k -2 increases of q at the end of the algorithm after the last reset of q. If q = 0, then there are no final queries after the last reset of q. However, as argued above, Line 9 is potentially executed (|A| + 1) times instead of only |A| times. Thus, the number of queries in Line 8 in that case is at most(|A| + 1) • (k -1) + |R| • k⌈log 2 r d ⌉.In both cases, the number of queries in Line 8 is at mostEQUATIONWe can conclude the target bound on the number of clean queries by summing up Equation (3) and Equation ( 4), plugging in r d +|A|-|R| = r and using Lemma 3.5, which also holds for Algorithm 2:n -r d + |R|⌈log 2 r d ⌉ + |R| + |A| + 1 + |A| • (k -1) + |R| • k⌈log 2 r d ⌉ + k -1 = n -r d + |R| + |A| • k + |R| • (k + 1)⌈log 2 r d ⌉ + k = n -(r -|A| + |R|) + |R| + |A| • k + |R| • (k + 1)⌈log 2 r d ⌉ + k = n -r d + |A| • (k + 1) + |R| • (k + 1)⌈log 2 r d ⌉ + k ≤ n -r d + η A • (k + 1) + η R • (k + 1)⌈log 2 r d ⌉ + k.Proof of the robustness bound. Let Q A denote the set of queries of Line 5 that trigger the execution of A ← A + e l , i.e., Q A contains the queries that detect an addition error. Let Q N denote the queries of Line 5 that do not trigger the execution of A ← A + e l and let Q R denote the set of all remaining queries.First, observe that each query in Q N is incurred by a distinct element of E \ (B d ∪ A). Thus, we have|Q N | = n -r d -|A|.Next, we continue by bounding |Q A | and |Q R |. To this end, we partition Q R into segments T i . A segment T i contains the queries of Q R that occur after the i'th reset of variable q but before reset i + 1. We use reset to refer to an execution of Line 2, 8, 9 or 12 that sets the variable q to 0. Since we count the execution of Line 2 as a reset, segment T 1 contains the queries of Q R that take place between the execution of Line 2 and the first execution of Line 8, 9 or 12 (if such an execution exists).For a segment T i , let q i denote the current value of variable q at the final query of the segment. We distinguish between long, short and tiny segments:• A segment T i is long if it contains queries executed in Line 11.• A segment T i is tiny if it satisfies q i ≤ k -1.• A segment is T i is short if it is neither long nor tiny.First, consider the long segments. Let I long denote the index set of the long segments and let L long = ∑ i∈Ilong q i . Each long segment T i contains k⌈log 2 r d ⌉ queries of Line 8 since q i must increase to at least this value in order to trigger queries in Line 11 and q is reset afterwards. Additionally, the segment must contain a query of Line 9 as q i increases to a value larger than k -1. Finally, T i contains up-to ⌈log 2 r d ⌉ queries of Line 11. Thus, a long segment T i contains at most (k + 1)⌈log 2 r d ⌉ + 1 queries. The number of long segments is at most Llong k⌈log 2 r d ⌉ as each long segment T i has q i = k⌈log 2 r d ⌉. By using that the total number of long segments is also at most |R| (since each execution of Line 11 finds a distinct removal error), we get that the total number of queries over all long segments is∑ i∈Ilong |T i | ≤ L long k⌈log 2 r d ⌉ ((k+1)⌈log 2 r d ⌉+1) = ( 1 + 1 k ) L long +|I long | ≤ ( 1 + 1 k ) L long +|R long |,where R long ⊆ R denotes the set of removal errors that where added to R in Line 12.Next, consider the short segments. As before let I short denote the index set of the short segments and let L short = ∑ i∈Ishort q i . A short segment T i contains exactly q i queries of Line 8. Furthermore, it must contain a query of Line 9 since it is not tiny and, thus, has q i ≥ k -1. This implies that T i contains q i + 1 = (1 + 1 qi )q i queries. As T i is not tiny, we have(1 + 1 qi )q i ≤ (1 + 1 k )q i .We can conclude that the total number of queries over all short segments is at most∑ i∈Ishort |T i | ≤ ( 1 + 1 k ) ∑ i∈Ishort q i = ( 1 + 1 k ) • L short .Finally, consider the tiny segments. As before let I tiny denote the index set of the tiny segments and let L tiny = ∑ i∈Itiny q i . Observe that each tiny segment T i either ends with the reset in Line 14 or it ends even before the reset because the algorithm terminates before q i reached value k -1. The latter case can happen at most once in the final segment. Since each reset in Line 9 sets the LS flag to false and the flag is only set to true again in Line 5 when an addition error is detected, the number of tiny segments is at most 1 + |A|.Each tiny segment contains at most q i + 1 queries (up-to q i in Line 8 and up-to one in Line 9). Let t denote the index of the final segment and let Ltiny = ∑ i∈Itiny\{t} q i . Without the final segment, we get∑ i∈Itiny\{t} |T i | = ∑ i∈Itiny\{t} (q i + 1) = Ltiny + |I tiny | -1 = Ltiny + |A|.We can combine the bound for the queries of these tiny segments with a bound for |Q A |. Since each query of Q A detects an addition error in Line 5, we have |Q A | = |A|. Furthermore, we have Ltiny + |A| = k • |A| as there are |A| tiny segments that are not the final one and each such segmentT i has q i = k -1.Putting it together we achieve the following combined bound:∑ i∈Itiny\{t} |T i | + |Q A | = Ltiny + |A| + |A| ≤ ( 1 + 1 k ) • ( Ltiny + |A|).It remains to consider the final segment T t . If this segment does not query in Line 9, then we have |T t | = q t . In this case, we can combine all previous bounds and use that L long + L short + Ltiny + q t + |A| ≤ r d + |A| -|R long | to conclude that the total number of queries is at most:|Q N | + |Q R | + |Q A | = |Q N | + ∑ i∈Ilong |T i | + ∑ i∈Ishort |T i | + ∑ i∈Itiny\{t} |T i | + |Q A | + |T t | ≤ n -r d -|A| + ( 1 + 1 k ) • ( Ltiny + |A| + L short + L long ) + |R long | + q t ≤ n -r d -|A| + ( 1 + 1 k ) • (r d + |A| -|R long |) + |R long | ≤ ( 1 + 1 k ) (n -r d -|A| + r d + |A| -|R long | + |R long |) = ( 1 + 1 k ) n.Note that the last inequality holds because |A| ≤ n -r d .If T t executes a query in Line 9, then we have |T t | = q t + 1. On the other hand, the query in Line 9 implies ℓ < d max for the current index ℓ when the query is executed and for d max = max ei∈B d i. This means that the variable q is increased at most r d -|R long | -1 times and, thus,L long + L short + Ltiny + q t + |A| ≤ r d + |A| -|R long | -1.Plugging these inequalities into the calculations above yields the same result:|Q N | + |Q R | + |Q A | = |Q N | + ∑ i∈Ilong |T i | + ∑ i∈Ishort |T i | + ∑ i∈Itiny\{t} |T i | + |Q A | + |T t | ≤ n -r d -|A| + ( 1 + 1 k ) ( Ltiny + |A| + L short + L long ) + |R long | + q t + 1 ≤ n -r d -|A| + ( 1 + 1 k ) (r d + |A| -|R long | -1) + |R long | + 1 ≤ ( 1 + 1 k ) (n -r d -|A| + r d + |A| -|R long | -1 + |R long | + 1) = ( 1 + 1 k ) n.This concludes the proof of Theorem 3.8.D.1 Discussion omitted from Section 4.1Another commonly used type of matroid oracle is the rank oracle: given any S ⊆ E, a rank oracle returns the cardinality of a maximum independent set contained in S, denoted by r(S). We show in this section that a rank oracle can be much more powerful than an independence oracle for our problem. First note that since r(S) = |S| if and only if S ∈ I, our previous results for independence oracles immediately translate. Moreover, we can even reduce the number of oracle calls using a rank oracle. We briefly discuss key ideas for the unweighted case below. It would be interesting to see whether these ideas can also be used for the weighted case.We Using the same idea, we can improve the number of oracle calls whenever B d ∈ B for the errordependent algorithm from Section 2.1 to 2. Furthermore, we can also improve its worst-case number of queries from Θ(n log 2 n) to n + 1. Recall that this bad case happens when η R is large. However, now we can simply compute r(B d ) and obtain η R = |B d | -r(B d ). Depending on η R , we then decide whether to remove elements via binary-search or immediately switch to the greedy algorithm. In particular, achieving this worst-case guarantee of n + 1 does not affect the error-dependent bound on the number of oracle calls.Finally, we can improve the dependency on η A . Recall that in the error-dependent algorithm, we iteratively augment an independent set B with η A many elements from E \ B d to a basis. But with a rank oracle, we can find these elements faster via binary search: find the first prefix (E \ B d ) ≤i which satisfies r(B ∪ (E \ B d ) ≤i ) > r(B), and add (E \ B d ) =i to B. Doing this exhaustively incurs at most η A ⌈log 2 (n -r d )⌉ clean-oracle calls. Thus, whenever η A < n-r d ⌈log 2 (n-r d )⌉ , this strategy gives an improved error-dependent bound over considering elements in E \ B d linearly. Furthermore, this condition can be easily checked with the rank oracle. Note that this contrasts Lemma B.2.To conclude the discussion, we obtain the following proposition.{ n + 1, 2 + η R • ⌈log 2 r d ⌉ + min { η A • ⌈log 2 (n -r d )⌉, n -r d }} clean rank-oracle calls.D.2 Proofs omitted from Section 4.3In the matroid intersection problem we are given two matroids M1 = (E, I 1 ) and M 2 = (E, I 2 ) on the same set of elements E and we seek to find a maximum set of element X ⊆ E such that X ∈ I 1 ∩ I 2 , i.e., it is independent in both matroids. For i ∈ {1, 2} we define r i to be the rank of matroid I i .The textbook algorithm for finding such a maximum independent set is to iteratively increase the size of a solution by one and eventually reach a point in which no improvement is possible; in that case we also get a certificate: U ⊆ E with |X| ≥ r 1 (U ) + r 2 (E \ U ). Given some feasible solution X ∈ I 1 ∩ I 2 , in every iteration the algorithm executes the following steps.1. Construct the directed bipartite exchange graph D(X) for sets X and E \ X, where for every x ∈ X and y ∈ E \ X there is an edge (x, y) if X -x + y ∈ I 1 and there is an edge(y, x) if X -x + y ∈ I 2 . Compute sets Y 1 = {y ∈ E \ X | X + y ∈ I 1 } and Y 2 = {y ∈ E \ X | X + y ∈ I 2 }. 2. If Y 1 = ∅ terminate with certificate U = E. If Y 2 = ∅ terminate with certificate U = ∅.Otherwise, compute a shortest path P between any vertex of Y 1 and any vertex of Y 2 .3. If no such path exists, terminate with the certificate U ⊆ E of elements for which there exists a directed path in D(X) to some element of Y 2 . Otherwise, augment X along P , that is, X ← X△P , and continue with the next iteration.We call the path found in step 2 an augmenting path. The running time of this classic algorithm is O(r 2 n) [17] , where n = |E| and r = min{r 1 , r 2 }. Recently, there has been a lot of significant progress concerning the running times for matroid intersection, culminating in the currently best running time of O(nr 3/4 ) for general matroids [6] and time O(n 1+o (1) ) for special cases, e.g., the intersection of two partition matroids [11] .Here, we focus on improving the running-time of the simple textbook algorithm for matroid intersection, by (i) using dirty oracles calls in each of the augmentation steps or (ii) by using warm-starting ideas, i.e., by computing a feasible solution of a certain size dependent on the error using an optimal dirty solution.Formally, additionally to the input for matroid intersection we are also given two dirty matroidsM 1 d = (E, I 1 d ) and M 2 d = (E, I 2 d ).Our goal is to improve the classic textbook algorithm from above by using dirty-oracle calls. We attempt the following approach: Given a feasible solution X (for the clean oracles), we do one iteration of the above algorithm using the dirty oracles. If there is an augmenting path, which is also an augmenting path for the clean matroids, we augment our solution and go to the next iteration. Otherwise, we found an augmenting path using dirty oracles, which is not an augmenting path for the clean matroids. In this case we do a binary search to find the error, update our dirty matroids and start the algorithm again. Finally, if there is no augmenting path in the dirty matroid, we need to augment the solution using clean-oracle calls, as we do not benefit from using the dirty oracle anymore. To avoid this situation, throughout this section we assume that the dirty matroids are supersets of the clean matroids, i.e., I 1 ⊆ I 1 d and I 2 ⊆ I 2 d . Further, in step 2 of the augmenting path algorithm it is crucial that the path from Y 1 to Y 2 is a path without chords 1 , as otherwise the computed solution may not be feasible. Note that in step 2 we compute a shortest path, which is always a path without chords. Therefore, if we use the dirty oracles to compute a shortest path w.r.t. the dirty oracles, we need to verify in each step that the computed path has no chords for the clean matroids as well. To avoid such a situation, we restrict to the case that the clean matroids are partition matroids, as for those matroids we do not need to find an augmenting path without chords, but just any augmenting path. We note that in general the intersection of two partition matroids can be reduced to finding a maximum b-matching.Therefore, from now on we assume that the clean matroids are partition matroids and that the dirty matroids are supersets of the clean matroids. Our algorithm works as follows. We assume that we are given a feasible solution for the clean matroid and wish to increase its size by one if possible. Additionally, we are given two lists F 1 and F 2 of false dirty queries for M 1 d and M 2 d , respectively, i.e., two list of sets F ⊆ E for which we have already queried that F is not independent in M 1 or M 2 , respectively (but it was independent in the respective dirty matroid). For each iteration, we use the following algorithm.Input: A feasible solution X ∈ I 1 ∩ I 2 and two lists of false dirty queries F 1 , F 2 Compute augmenting path P in D F d (X) if there is no such path P then return X (in this case X is optimal) if P is augmenting path for clean matroids thenX ′ ← X∆P , F ′ 1 ← F 1 , F ′ 2 ← F 2 if P is notan augmenting path for clean matroids then find the first edge on P such that e / ∈ D(X) via binary search. Add corresponding set to F 1 or F 2 and go to Line 1.Here, D F d (X) is the bipartite exchange graph for the dirty matroids M 1 d and M 2 d , in which we have excluded the list of false queries F. More formally, for every x ∈ X and y ∈ E \ X there is an edge (x, y) in D F d (X) if X -x + y ∈ I 1 and X -x + y / ∈ F 1 and there is an edge(y, x) in D F d (X) if X -x + y ∈ I 2 and X -x + y / ∈ F 2 .Next, we analyze this augmenting path algorithm. In order to define an error measure, letη 1 = {F ∈ I 1 d | F / ∈ I 1 } and η 2 = {F ∈ I 2 d | F / ∈ I 2} be the number of different sets which are independent in the dirty matroid but not independent in the clean matroid. We now show the following result, which is stronger than Proposition 4.2.Proposition D.1. Let M 1 and M 2 be two partition matroids and M 1 d and M 2 d be two dirty matroids such that M 1 d and M 2 d are supersets of M 1 and M 2 , respectively. Given a feasible solution X ∈ I 1 ∩ I 2 of value k, there is an algorithm that either returns a solution of value k + 1 or outputs that X is maximum using at most 2 + (η 1 + η 2 ) • (⌈log 2 (n)⌉ + 2) clean-oracle calls.Moreover, there is an algorithm that computes an optimum solution for matroid intersection using at most (r + 1)• (2 + (η 1 + η 2 ) • (⌈log 2 (n)⌉ + 2)) clean-oracle calls.Proof. We first prove that the solution output by the algorithm is feasible. If there is no augmenting path in D F d (X), then there is no augmenting path in D(X) since the dirty matroids are supersets of the clean matroids and in F 1 and F 2 we only save queries which are not independent in the clean matroid. Once we find an augmenting path P in D F d (X), we always verify it using two clean-oracle calls: We query if X∆P is independent in M 1 and in M 2 . Hence, we only augment X if the augmenting path P is also an augmenting path in D(X). Since both clean matroids are partition matroids, we do not need to verify that P is an augmenting path without chords and hence X∆P is an independent set in both clean matroids.It remains to prove that we use at most 2 + (η 1 + η 2 ) • ⌈log 2 (n)⌉ clean-oracle calls. As described above, after finding an augmenting path P in D F d (X), we verify it using two clean-oracle calls: We query if X∆P is independent in M 1 and in M 2 . If it is independent, we are done. This check needs 2 clean-oracle calls. Otherwise, one of the queries tells us that X∆P is not independent, i.e., one of the edges e in P corresponds to a resulting set X e such that X e is independent in, say M 1 d , but not independent in M 1 . In particular, in this case Line 7 is executed.We now show the following: Whenever Line 7 is executed, we add to F 1 or F 2 an additional set and we can find such a set using at most log 2 (n) many clean-oracle calls. Since |F 1 | + |F 2 | ≤ η 1 + η 2 by definition, this shows the desired bound.The exchange graph D(X) is a subgraph of the exchange graph D F d (X) since the dirty matroids are supersets of the clean matroid and by definition of F 1 and F 2 . Hence, if P = e 1 , e 2 , ..., e p is an augmenting path in D F d (X) but not an augmenting path in D(X), there must be an edge e i ∈ P which is not in D(X). Let e i be the first such edge. In order to find e i , we simply do a binary search:In each iteration, we have two pointers ℓ and r, satisfying 0 ≤ ℓ ≤ i and i ≤ r ≤ p, for which we know that the first ℓ edges of P are also in D(X) and among the edges e ℓ+1 , ..., e r there must be an edge which is not in D(X). Then, for P ′ = e 1 , e 2 , ..., e ℓ+⌊ r-ℓ 2 ⌋ we simply query if X∆P ′ is independent in both clean matroids. If yes, then we set ℓ = ℓ + ⌊ r-ℓ 2 ⌋. If no, we set r = ℓ + ⌊ r-ℓ 2 ⌋. We repeat this until we found e i . This binary search algorithm finds the first edge e ∈ P which is not in D(X) using at most ⌈log 2 (n)⌉ many clean-oracle calls, where n is the number of elements |E|. The additional +2 in the bound appears since whenever we compute a new candidate augmenting path P , we first test if it is also an augmenting path in D(X) using 2 clean-oracle calls. Therefore, we obtain the bound of at most 2 + (η 1 + η 2 ) • (⌈log 2 (n)⌉ + 2) clean-oracle calls.We obtain the final bound of (r+1)•(2+(η 1 +η 2 )•(⌈log 2 (n)⌉+2)) clean-oracle calls for computing an optimum solution for matroid intersection as follows: In each iteration we increase the size of the current solution by one or prove that there is no improvement possible (and hence the solution is optimal). Therefore, there are at most r + 1 iterations, which proves the bound.In this subsection we consider the task of using a solution to the dirty matroid intersection instance as a "warm-start" for the clean matroid intersection instance. In particular, we compute a maximal subset of the dirty solution using only few clean-oracle calls, which again will depend on the error of the dirty matroids. Similar approaches for warm-starting using predictions have been used in [10, 16, 31] for problems like weighted bipartite matching or weighted matroid intersection. We show here that this is also possible using dirty matroids.Before we start with the algorithm, let us define our error measure for this subsection. Here, we are just interested in the removal error: for a given maximum solution S d for the dirty matroid intersection, we compute the shortest distance to obtain a feasible solution to the clean matroid intersection problem. Then, the error is simply the maximum value of this shortest distance among all maximum solutions S d for the dirty matroid intersection. More formally, let s * d = max S d ∈I 1 d ∩I 2 d |S d | and define S * d = {S d ∈ I 1 d ∩ I 2 d | |S d | = s * d }′ c ∈ I 1 ∩ I 2 of size |S ′ c | ≥ s * d -2η r using at most 2 + 2η r • (1 + ⌈log 2 (n)⌉) clean-oracle calls.Proof. Feasibility is clear since we check in Line 3 for both matroids whether the solution is indeed feasible. We first prove that we remove at most 2η r many elements from S d to obtain a feasible solution S ′ c ∈ I 1 ∩ I 2 . By the definition of the error η r , there is some setS c ∈ I 1 ∩ I 2 with S c ⊆ S d of size |S d | -η r . Hence, there is some set R 1 η such that S d \ R 1 η ∈ I 1 and some set R 2 η such that S d \R 2 η ∈ I 2 , where |R 1 η | ≤ η r and |R 2 η | ≤ η r . Therefore, S ′ c := S d \(R 1 η ∪R 2 η ) ∈ I 1 ∩I 2 and |S ′ c | ≥ |S d |-2η r .Note that since M 1 and M 2 are matroids, the set R 1 η can be found by greedily removing elements from S d such that S d \ R 1 η ∈ I 1 and, afterwards, the set R 2 η can be found by greedily removing elements fromS d \ R 1 η such that (S d \ R 1 η ) \ R 2 η ∈ I 2 .Since Algorithm 5 computes such a set, we conclude that Line 5 is executed at most 2η r times.Next, we show that whenever Line 5 is executed, we use at most ⌈log 2 (n)⌉ many clean-oracle calls. We fix some i ∈ {1, 2}. Let e 1 , e 2 , ..., e |S d | be any order of the elements. To find the first element e j ∈ S d such that {e 1 , ..., e j-1 } ∈ I i and {e 1 , ..., e j } / ∈ I i , the algorithm performs a binary search. By folklore results, we use at most ⌈log 2 (n)⌉ many clean-oracle calls to do so. Furthermore, whenever Line 5 is executed, we have previously executed a clean query in Line 3. Finally, we additionally need 2 clean-oracle calls, as Line 5 is executed for both matroids even if there is no error at all. Therefore, we use at most 2 + 2η r • (1 + ⌈log 2 (n)⌉) many clean-oracle calls.Justification: We have clearly stated the necessary assumptions in the respective theorem statements. While we give (some) proof sketches in the main parts, the formal proofs to all our theoretical results can be found in the appropriate section in the appendix.• 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [NA] Justification: The paper does not include experiments.• 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 a 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 it 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 to 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or 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 reproducibility.In the case of closed-source models, it 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 to have some path to reproducing or verifying the results.• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • 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 a 96% CI, if the hypothesis of Normality of errors 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 of range (e.g. negative error 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. 
matroid intersection:: 
 We give two different approaches on how our techniques can be incorporated in textbook algorithms for reducing the number of clean-oracle calls in the fundamental matroid intersection problem using dirty oracles (see Section 4.3).All omitted proofs are deferred to the appendix. 
algorithm 1 computes a max-weight basis with at most n-r+1+2η: 
 A +η R •⌈log 2 (r d )⌉ clean queries.We complement this algorithmic result by a lower bound. It proves that our error-dependent guarantees in the unweighted case are not possible in the weighted case. Hence, it separates both settings.Lemma 3.7. Every deterministic algorithm for finding a maximum-weight basis executes strictly more than n -r+ η A + η R • ⌈log 2 (r d )⌉ + 1 clean-oracle calls in the worst-case.Application of the robustification framework. As in the unweighted case, our algorithm may perform poorly when the dirty oracle is of low quality, i.e., η A and η R are large. We extend the ideas for robustifying the error-dependent algorithm (cf. Section 2.2) and combine them with the concepts developed above. The key idea for robustifying Algorithm 1 is to start a binary search only after a sufficient number of linear search steps. However, as observed above (cf. Figure 1 ), we cannot remove all blocking elements in one iteration. While the simple argument that the linear search partitions B d still holds, it does not cover the total removal cost, because a later addition can create a removal at a previously checked position. To overcome this, we observe that in Algorithm 1, immediate removal of every detected element from the current solution is not necessary; we just need to decide whether in iteration ℓ element e ℓ should be part of the solution.Algorithm 2: Find a maximum-weight basis (robustified)Input: dirty basis B d , matroid (E, I), integer k ≥ 1 A ← ∅; R ← ∅; d max ← max ei∈B d i q ← 0; LS ← true {linear search counter / flag} for ℓ = 1 to n do if e ℓ / ∈ B d then if ((B d \ R) ∪ A + e ℓ ) ≤ℓ ∈ I then A ← A + e ℓ and LS ← true else if e ℓ ∈ B d \ R and LS = true then q ← q + 1 if ((B d \ R) ∪ A) ≤ℓ / ∈ I then R ← R + e ℓ and q ← 0 if ℓ = d max or (q = k -1 and (B d \ R) ∪ A ∈ I) then q ← 0 and LS ← false else if q = k⌈log 2 r d ⌉ then Find the smallest index i s.t. ((B d \ R) ∪ A) ≤i / ∈ I via binary search 12 R ← R + e i and q ← 0 return (B d \ R) ∪ AIn our robustified algorithm (Algorithm 2) we exploit this as follows. While in Algorithm 1 we linearly check prefixes of E \ B d for additions, we now linearly check prefixes of E for additions (Lines 4-5) and removals (Lines 6-8). However, for the sake of a good error-dependency, we count these removal checks (cf. increment counter q in Line 7) and execute a binary search only if we checked enough elements in B d linearly (Lines 10-12). Then, we can again bound the total cost for the binary searches using a density argument. Whenever we remove an element, we charge the previous cost of the linear searches to this removal error and reset q, which re-activates the linear search. However, if the current solution is already independent, we do not want to search for removal errors at all (cf. Lines 2 and 8 in Algorithm 1). Unfortunately, doing such a check after every addition and removal already rules out a robustness close to n. Thus, we slightly delay this check w.r.t. the counter q, and stop the removal search accordingly (Line 9). Finally, whenever an element is added, we make sure that the linear search is running or that we start it again (Line 5), as a new circuit could have been introduced in our solution. Formalizing this sketch proves our main theorem.Theorem 3.8. For any k ∈ N + , there is an algorithm that, given a dirty matroid M d of rank r d with unknown η A and η R , computes a maximum-weight basis of a matroid M of rank r with at mostmin{n -r + k + η A • (k + 1) + η R • (k + 1)⌈log 2 r d ⌉, (1 + 1 k )n} oracle calls to M.4 Extensions and future work 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 or 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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Since our research does neither involve human subjects or participants nor use any datasets, the research process did not cause harm. Since we do not directly train ML models, but rather analyze a theoretical framework within which ML models can be used for matroid optimization, we do not anticipate negative societal impact or potential harmful consequences.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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Since we do not directly train ML models, but rather analyze a theoretical framework within which ML models can be used for matroid optimization, we do not anticipate a direct societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Since we do not train a ML model but analyze a theoretical framework of how to decrease their query time or how to incorporate them into pre-existing algorithms, our paper does not directly pose such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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: As the paper is purely theoretical, we are not using existing assets. Where applicable, we do cite the relevant papers with related and / or similar models.Guidelines:• The answer NA means that the paper does not use 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 a URL.• Depending on 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).A chord e of some s-t path P is an edge such that P + e admits an s-t path P ′ that is strictly shorter than P . 
 
 Appendix:  


Decision: The reviewers remark that claims appear to be well substantiated with proofs [2QVw, KsE6], the manuscript presents strong results [rC5n, AWmg] and is well-written/clear/logically [KsE6, AWmg], but the writing/organization/readability of the paper could still be improved [2QVw, rC5n], the complexity improvement for independence queries hinge on the rank of the matroid r to grow with larger element cardinality $n$ such that $n-r$ would grow sublinearly [AWmg], limited improvement over trivially running two algorithms in parallel [AWmg] and requiring strong assumptions for the extension to matroid intersection [AWmg].

Apart from answering reviewer questions, the rebuttal expresses the intention to add a full version, not bound by page limits, which features more details and illustrations [response to 2QVw], a gentle introduction to matroid optimization [response to rC5n], some empirical verification [responses to KsE6, rC5n], clarifications of how $2$-oracle matroid optimization relates to neural networks [response to 2QVw] and that "robust" refers in this context to worst-case guarantees over inputs [response to 2QVw].

The overall recommendation is to accept this submission with the agreed upon changes during the discussion phase. While the improvements might not be particularly substantial, there is not really much room for improvement as the bounds are tight [AWmg], the work comprehensively studies a relevant problem and the proofs as well as presentation appear to be generally of high quality although the writing might be a bit dense at times.

Reviews: review: paper_summary: paper_summary: The paper explores the concept of 2-oracle algorithms for matroid optimisation problems. The underlying idea is to equip algorithms with a second, somewhat "weaker" oracle. The second oracle is also permits the algorithm to query matroid information (similar to the first oracle) but only gets imprecise answer (different from the first oracle). Therefore the second oracle is also called "fast" as the assumption is that its use is cheaper than the use of the first oracle. In this context the problem of computing a maximum-weight basis for a matroid is investigated. The main result obtained is the existence of an algorithm for computing a maximum-weight basis with a prescribed number of oracle calls. Some related tools and aspects like error-depdent and robust algorithms are also considered.
strength_weakness: strength_weakness: - The paper is not easy to read; at the end of the introduction (i.e. Section 1) there should be an outline of the organisation of the paper to give the reader orientation

- The organisation of the paper is poor: the 9 pages text consist of 4 pages introduction (Section 1), 1.5 pages warm-up (computing an "unweighted" basis) (Section 2), 2 pages computing a max-weighted basis (Section 3) and 1.5 pages future work (Section 4); the way how the material is organised is really unfriendly for the reader

- The main results require a long list of lemmas (which are given in the paper or its appendix); so this might be tedious for the reader to follow the line of proof

- The presentation of the material in the paper is at most fair; changing this may require quite some rewriting of the paper
questions: questions: - While matroid optimisation is closely related to combinatorial optimisation it is not clear why this paper is submitted to NeurIPS as the connection to neural computing is not that obvious; so this should be justified better

- The paper speaks of "robust" algorithms and of "robustifying" error-dependent algorithms in a sense of dealing with errors from the second oracle; but robust optimisation has been studied widely in the combinatorial optimisation community is usually concerned with uncertainty in the costs or times given as input; so these two meaning of "robust" may easily be mixed up and may be confusing for the reader
limitations: limitations: n/a
paper_summary: paper_summary: The paper mainly studies the problem of finding a maximum weight basis in a matroid $\mathcal{M}=(E,\mathcal{I})$ using two types of independence oracles "clean" and "dirty". The clean oracle determines whether a set $S \subseteq E$ is an independent set in $\mathcal{M}$, and the dirty oracle determines independence according to another matroid $\mathcal{M}_d=(E,\mathcal{I}_d)$. The dirty oracle is free but might be imprecise for $\mathcal{M}$. For measuring the error of $\mathcal{M}_d$ with respect to $\mathcal{M}$, the parameters $\eta_A$ and $\eta_R$ are defined, which intuitively are the number of elements that have to be added to/removed from a maximum-weight basis of $\mathcal{M}_d$ to reach a maximum-weight basis of $\mathcal{M}$.
The main result of the paper is an algorithm that computes a maximum-weight basis of $\mathcal{M}$ using at most $\min (n-r+k+\eta_A \cdot (k+1)+ \eta_R \cdot (k+1) \lceil \log_2 r_d \rceil, (1+1/k)n )$ calls to the clean oracle, where $n=|E|$, $k$ is a positive integer, and $r$ and $r_d$ are the ranks of $\mathcal{M}$ and $\mathcal{M}_d$, respectively. The authors also prove lower bounds that show any deterministic algorithm should have dependencies with respect to $n$, $r$, $\eta_A$, and $\eta_B$ that are similar to those of the proposed algorithm.
strength_weakness: strength_weakness: * The parameter $k$ in the main result of the paper is intuitively used to determine how much we want to trust the dirty oracle. When 
$k$ is set close to 0 to heavily favor the dirty oracle, if the errors $\eta_A$ and $\eta_R$ turn out to be high, the algorithm might use $\Omega(n \log n)$ calls to the clean oracle. This significantly exceeds the calls required by the optimal worst-case algorithm without predictions, which uses $n$ calls to the clean oracle. In this sense, the algorithm is not robust.
* The results lack empirical verification. Even basic proof-of-concept experiments would be valuable to assess whether this model could be practically applicable.
questions: questions: * Minor remarks:
  * In lines 71-73 and 86-87, the wording was initially confusing to me. I think the way these results are stated later as the minimum or maximum of two values is easier to read.
  * The error measures defined in lines 375-380 can be exponential in $n$.
limitations: limitations: The authors state their theoretical results formally, describing all assumptions.
paper_summary: paper_summary: This paper aims to solve fundamental matroid optimization problems, specifically, computing a maximum-weight basis of a matroid, a complex combinatorial optimization problem, To this end, the author proposes a two-oracle model, which uses fast but dirty oracle to reduce the time to call clean oracles. Then, the author proposes the algorithm to compute the maximum-weight basis and gives the upper bound of the oracles calls needed. Finally, the author also discusses advanced settings like different kinds of oracles and other matroid optimization problem.
strength_weakness: strength_weakness: 1. The organization of this paper is very confusing, for example, the author includes a large part of the preliminary in its introduction rather than an independent section. Moreover, the author includes many extended results and propositions in its final section 4, but doesn't include a conclusion.

2. The paper studies combinatorial optimization problems which can be hard to comprehend for readers with not much background knowledge, while the paper is not self-contained enough. The preliminary in Section 1.3 alone is not enough to grasp an intuitive concept of that.

3. This paper doesn't include any empirical experiment.
questions: questions: Perhaps it will be beneficial to include more figures as illustrations? For example, you can give an example of the algorithm walkthrough as a toy example. Also, it can also be helpful for the readers to understand the new proposed concept like k-safe and modification example.
limitations: limitations: I think the author has stated the limitations as he/she clearly stated the necessary assumptions in the respective theorem.
paper_summary: paper_summary: The paper studies the problem of finding a maximum-weight basis of a matroid in a learning-augmented setting, where there are two different oracles that the algorithm can query to check whether a set is independent: An exact oracle that always gives correct answers (but may be slow), and a dirty oracle that may give incorrect answers. Formally, the answers of the dirty oracle correspond to some other "dirty" matroid (or more generally, downward closed set system) that ideally is close to the true matroid. In the setting considered, queries to the dirty oracle are free, and the goal is to minimize the number of queries to the exact oracle to find a maximum weight basis.

The quality of the dirty oracle is parametrized by two error measures, corresponding roughly to the numbers of elements that would need to be added/removed to move from a max-weight basis for the dirty matroid to a max-weight basis for the true matroid. The main result is an algorithm whose number of clean queries interpolates (as a function of the error parameters) between n-r+k (where n is the number of items in the ground set and r the size of any basis, and $k\ge 1$ is an algorithm parameter that can be chosen) and $n(1+1/k)$. One should note that without dirty queries, the problem requires n exact queries. The dependence on the error in the interpolation is shown to be asymptotically optimal.

If the algorithm has access to rank queries rather than just independence queries (rank queries return the rank of a set, i.e., the size of the maximal independent subset) the guarantees can be improved to a quantity interpolating beetween 2 and n+1 exact queries depending on the input.

An extension of the main results includes an application to the matrix intersection problem.
strength_weakness: strength_weakness: - In order for the improvement of the algorithm for independence queries to be a super-constant factor requires n-r is sub-linear in n. It is not clear how realistic this is. The authors hint at graphic networks in sparse graphs having high rank -- does this mean $r=\Omega(n)$ or even $r = n - o(n)$? The result in the case of rank queries avoids this issue though.
- Significant work is required for the robustness result, i.e., to ensure the number of clean queries is simultaneously bounded by a function of the error parameters and by a quantity slightly larger than n. However, the trivial approach of running two algorithms in parallel would achieve a similar result, losing only a factor of 2, so the improvement over this trivial approach is relatively small.
- The extension to matroid intersection seems relatively weak (strong assumptions and an error measure that can be exponentially large in n in the first setting). Since this is only an extension rather than a main result, this does not affect the main contribution though.
questions: questions: Please elaborate on the size of n-r in typical settings, in relation to the first possible weakness above.
limitations: limitations: Yes

Comments: comment: Dear authors,
Many thanks for your answers that helped in clarifying several points. I am more happy now.

Regarding 1) Justification for Conference Fit. The motivation for submitting the paper is clearer now. The connection to learning-augmented algorithms could be explained a bit more detailed (as done here in your reply). In my opinion, reference [26] is not a solid argument as it is unclear according to which criteria this list of papers in Github is put together and maintained. Perhaps you can phrase this differently.

Regarding 2) Term "robust" and its use in robust optimization. Thanks for the explanation. You could also include such a brief remark into the paper to avoid confusion. 

Regarding 3) Weak presentation. I understand that the page limit is a challenge, and you made a good effort to put a lot of content into the available space. My concern is not that you break a complex proof into a series of lemmas. I also like that you first study the unweighted case before you continue with the more general weighted case. My concern is rather that many readers will give up before they reach the end of the introduction (at the bottom of page 4), and that would be a pity. Good that you offered to include an overview of the paper’s organisation at the end of the introduction. The future reader of your paper will definitely benefit from this. (My recommendation would even be to subdivide the 4-page introduction and place this overview earlier; but this is up to you.)
Thank you for your response. I'm intending to keep my score.
Thanks to the authors for their response. Regarding the robustness guarantees, I mistakenly assumed that $k$ can be arbitrarily close to zero. Thanks for the clarification.

After reading all the reviews and responses, I have decided to maintain my original score.