Testing -Submodularity
Abstract
We initiate the study of property testing for –submodular functions, a higher-dimensional analogue of submodular functions defined on partial partitions of a ground set. While –submodularity retains the diminishing-returns flavor of ordinary submodularity, it also introduces a pairwise monotonicity constraint comparing competing assignments of the same element. This additional local structure makes the testing problem qualitatively different from the classical case.
Our results show a sharp contrast between distance regimes. In the regime for , we prove that every bounded –submodular function is close to a junta on the hypergrid. Combined with an implicit-learning tester for hypergrid domains, this yields a constant-query tester for –submodularity. In the Hamming distance regime, –submodularity admits two qualitatively different local witnesses – violated squares for diminishing marginal gains, and violated triangles for pairwise-monotonicity failures – and the latter has no counterpart at . We prove density theorems for both witness types via repair on filters and ideals of partial partitions, yielding non-adaptive, one-sided sub-exponential-query testers for the two component properties of –submodularity. We then exhibit a configuration in which the two repair directions are forced into opposition on a shared vertex, identifying a structural barrier to combining these into a tester for the full property.
Finally, for bounded-range functions, we give an adaptive tester for monotone –submodularity via a pseudo-DNF representation and learning on the hypergrid. Several of the structural and learning tools developed here may be useful for testing other properties over product domains.
Keywords and phrases:
property testing, sublinear algorithms, submodular functionsCategory:
RANDOMFunding:
Diptaksho Palit: Supported by the U.S. National Science Foundation under Grant No. 2022446.Copyright and License:
2012 ACM Subject Classification:
Theory of computation Streaming, sublinear and near linear time algorithmsAcknowledgements:
T.H. worked on -submodularity testing as a final project for the 2024 Sublinear Algorithms course taught by Ronitt Rubinfeld. T.H. and D.P. started working on this project for a course on Sublinear Algorithms taught by Sofya Raskhodnikova [14]. We thank Fabian Spaeh for inspiring us to investigate this question through his work on -submodular optimization.Editors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
Submodularity is one of the canonical examples of a global property with a simple local interpretation. A set function is submodular when it satisfies the principle of diminishing marginal returns: the incremental value of adding an element can only decrease as the set to which it is added grows. Formally, a set function is said to be submodular if, for all subsets , it satisfies the inequality:
This local-to-global nature makes submodularity a natural target for property testing [8], where one is given oracle access to an unknown function and must distinguish functions satisfying a property from those that are far from satisfying it. Yet even for ordinary submodularity, the query complexity of testing remains poorly understood. Seshadhri and Vondrák [16] gave a tester using roughly queries and proved a linear lower bound; the latter was later improved to a nearly quadratic lower bound by Hatami and Vondrák [10]. The resulting exponential gap has remained open, and has motivated the study of more structured regimes, such as bounded-range submodular functions [15] and testing under distance rather than Hamming distance [1].
In this work we ask what happens to this picture for a higher-dimensional analogue of submodularity. For a fixed integer , a point in can be viewed as a partial partition of the ground set : each element is either assigned to one of parts, or left unassigned. A function on these partial partitions is –submodular if marginal gains diminish no matter which part an element is assigned to. The case is ordinary submodularity, while already for the domain has multiple incompatible directions in which a single element may be added. This function class has been studied extensively in optimization [12, 4], with applications including tensor placement [12] and online ad allocation [5].
From a testing perspective, –submodularity is not merely submodularity on a larger domain. A useful characterization, due to Ward and Živný [17], decomposes –submodularity into two conditions. The first is diminishing marginal gains, which generalizes the familiar submodular inequality inside each direction of the hypergrid. The second is pairwise monotonicity, a constraint comparing the marginal gains of assigning the same element to two different parts. One way to understand this decomposition is to separate two kinds of local interactions. When two partial partitions make compatible choices, –submodularity behaves like ordinary diminishing returns along the corresponding direction. When they make incompatible choices for the same element, the join operation discards that element from both parts; the resulting inequality says that assigning the element to two different parts cannot have two strongly negative marginal gains at the same time. This second condition has no analogue when , and it is the source of much of the new combinatorial structure in the testing problem.
We initiate the study of testing –submodularity. Our results show a sharp contrast between two distance regimes. In the regime, analytic structure survives the passage from the Boolean hypercube to the hypergrid: we prove a junta-approximation theorem for –submodular functions and combine it with an implicit-learning tester on hypergrids. In the Hamming distance regime, the local structure fragments: we obtain testers for the two local constraints by developing square and triangle witness structures, and show that their repair procedures expose a genuine obstruction to the standard local-repair paradigm for full –submodularity. Along the way, we develop testing and learning tools for hypergrid domains that may be useful beyond this problem.
1.1 Our Results
We organize our contributions around three questions. First, does the analytic structure that makes submodularity testable in distance survive on the richer domain of partial partitions? Second, in the Hamming distance regime, can the local-violation framework for submodularity be adapted to the two distinct constraints that characterize –submodularity? Third, can bounded range assumptions recover efficient testability for a meaningful subclass of –submodular functions?
testing from hypergrid junta structure
Our first result is a constant-query tester for –submodularity in distance. Here and throughout this section, constant means independent of the ambient dimension .
Theorem 1.
For all , there exists an adaptive, one-sided error -tester for -submodularity making queries.
The main structural input is not a black-box reduction to the submodular case. We prove that every bounded –submodular function is close to a function depending on only a small number of coordinates, even though each coordinate can move in competing directions. This requires choosing influential coordinates in a way that respects all parts of a partial partition, and uses the fact that –submodular functions satisfy a self-bounding variance inequality.
Theorem 2.
Let be a –submodular function and be a small enough constant. Then there exists a –submodular function that depends only on dimensions, where
and the function satisfies
We then develop the testing component needed to turn this structure into an algorithm. The implicit-learning framework of Blais and Bommireddi [1] relies on identifying influential coordinates and checking consistency with a small junta. We formulate and analyze this framework on hypergrid domains using Fourier analysis over generalized product spaces, and simplify parts of the original argument by separating the learning and final testing samples.
Theorem 3.
Let . Suppose is a property of functions such that for any there exists a -junta satisfying . Then, there exists a tester that, given query access to an unknown function , will make queries to and with probability at least accept if and reject if is -far from in the norm.
Local testing in Hamming distance
Our second set of results addresses the Hamming-distance regime, where the Seshadhri–Vondrák local-repair paradigm for ordinary submodularity does not extend directly. Pairwise monotonicity is vacuous when , but on the hypergrid its violations form a new witness shape – triangles – incomparable with the squares that witness diminishing-marginal-gain failures. Repair likewise shifts from Boolean subcubes to filters and ideals of partial partitions, and the density arguments must be re-proved in this setting. We obtain non-adaptive, one-sided testers for the two component properties of –submodularity:
Theorem 4.
Let be given via oracle access. There exist non-adaptive, one-sided error testers for the diminishing marginal gains and pairwise monotonicity properties with the following guarantees:
-
If satisfies the property, the tester accepts with probability .
-
If is -far from the property (i.e., at least values must be modified to satisfy it), the tester rejects with probability at least .
The tester for diminishing marginal gains makes queries; the tester for pairwise monotonicity makes queries.
Notably, only the pairwise-monotonicity tester has query complexity depending on , despite governing the structure of the domain.
Combined, these results expose a structural difference between –submodularity and ordinary submodularity that the analytic () regime does not see. In Section 4.3 we exhibit an explicit configuration (Figure 1) on a high item-weight filter in which repairing a triangle violation forces value changes in the opposite direction from those needed to repair an overlapping square violation, on a shared vertex. The two repair directions are not merely incompatible at one point – they are jointly inconsistent across an entire region. We record this as Observation 32: it rules out the natural component-wise extension of local repair to full –submodularity, and isolates a concrete barrier that any sub-exponential local-witness tester must overcome by enlarging the witness vocabulary beyond squares and triangles.
Bounded range and monotone –submodularity
Finally, we show that efficient Hamming-distance testing can be recovered for monotone –submodular functions with bounded range. The result is again obtained through learning, but the relevant representation is no longer a junta. Instead, we utilize pseudo-DNF representations for functions on the hypergrid and prove that bounded-range monotone –submodular functions have bounded-width pseudo-DNFs.
Theorem 5.
Let be constants. There exists a tester which, given query access to a function satisfies the following.
-
1.
If is monotone –submodular, then accepts with probability .
-
2.
If is -far from monotone –submodularity, then rejects with probability .
-
3.
makes at most queries.
The learning result for bounded-width pseudo-DNFs uses a hypergrid version of the switching-lemma/Fourier-sparsity route and yields a tester via the Kushilevitz-Mansour algorithm. We expect this learner to be useful beyond –submodularity.
1.2 Prior Work
Testing whether a given function is submodular was first examined by Parnas, Ron and Rubinfeld [13], who studied the limited setting of testing for a class of matrices called Monge matrices. In its full generality, the problem was considered by Seshadhri and Vondrák [16]. They developed the local-witness and repair framework for Hamming-distance testing on the Boolean hypercube, proving an upper bound of and a linear lower bound. The latter was later improved to by Hatami and Vondrák [10]. Blais and Bommireddi [1] subsequently studied the problem in the norm, and using an approximation result from [6], designed an implicit-learning tester with constant query complexity in the input length. Raskhodnikova and Yaroslavtsev [15] studied bounded-range submodular functions through a learning-based approach and proved a polynomial-time upper bound in this regime. Chakrabarty and Huang [3] studied the problem of testing for coverage functions, which are a special type of submodular function.
Our work is informed most directly by the three submodularity-testing frameworks of Seshadhri and Vondrák [16], Blais and Bommireddi [1], and Raskhodnikova and Yaroslavtsev [15]. These works provide the conceptual starting points for the three regimes we study. The passage to –submodularity introduces new difficulties in each case: local witnesses split into squares and triangles in the Hamming regime, influential coordinates must account for competing assignments in the regime, and bounded-range learning requires representations over the hypergrid rather than the Boolean cube.
To our knowledge, there is no prior work on testing -submodularity, though the property has been studied extensively from the optimization perspective [12, 4]. We also use the structural characterization of Ward and Živný [17], which identifies –submodularity with the conjunction of diminishing marginal gains and pairwise monotonicity.
1.3 Technical Overview
The main technical theme is that the hypergrid introduces several inequivalent notions of locality. In the regime, locality is analytic and is captured by influential coordinates. In the Hamming regime, locality is combinatorial and is captured by small violated configurations. For bounded-range functions, locality appears through compact symbolic representations. In each part of the paper we develop the corresponding notion of locality for partial partitions.
The analytic regime: finding the right influential coordinates
The tester has two ingredients: a junta-approximation theorem for –submodular functions, and a tester for properties that are close to juntas on the hypergrid. The obstacle in the first ingredient is that a coordinate has possible nonzero directions. Several natural ways of declaring a coordinate influential in one part at a time almost work, but fail to interact correctly with the boosting lemma for down-monotone families (Lemma 12).
Our solution is to define the relevant influence threshold by looking across all partitions of the remaining coordinates. This lets the selection rule remain compatible with the combinatorial boosting argument while still respecting the multi-directional nature of the domain. The second key input is a variance bound: we prove that –submodular functions are -self bounding (Lemma 14). Together, these ingredients yield a junta depending on only coordinates.
Once the junta structure is established, the testing step is conceptually separate. We analyze implicit learning directly on using Fourier analysis over product domains. The tester identifies a candidate set of influential coordinates and then checks whether the observed behavior is consistent with a junta from the target property. Using an independent sample in the final testing stage also simplifies the decorrelation issues that arise in the original Boolean-domain analysis of [1].
The Hamming regime: local witnesses and repair
In Hamming distance, a tester needs many local witnesses whenever the function is far from the property. For ordinary submodularity, the relevant witness is a violated square in the Boolean hypercube, and the analysis of Seshadhri and Vondrák [16] shows that few violated squares imply a global repair.
For –submodularity, a single witness shape is no longer sufficient. Using the characterization of Ward and Živný [17], we separate the property into diminishing marginal gains and pairwise monotonicity. Diminishing marginal gains is witnessed by generalized violated squares, while pairwise monotonicity is witnessed by violated triangles. We prove density statements for both witnesses by designing repair procedures on large inclusion-closed regions of the hypergrid: ideals and filters . This gives sub-exponential testers for the two component properties.
The same repair viewpoint also yields a structural observation about the full Hamming-distance problem (Observation 32, illustrated in Figure 1). On high item-weight filters, the repair direction needed for a violated square is forced into conflict with the repair direction needed for an overlapping violated triangle on a shared vertex. This is not a limitation of our proof – it is a structural property of the problem: any tester built on the squares-and-triangles vocabulary, no matter how the repair is organized, must encounter a configuration of this kind. A sub-exponential tester for full –submodularity in Hamming distance therefore requires an enriched witness vocabulary, not merely a more clever combination of square and triangle repairs.
The bounded-range regime: representation before testing
For bounded-range monotone –submodular functions, we take a representation-theoretic route. We first show that such functions admit bounded-width pseudo-DNF representations over the hypergrid. This representation captures the monotone threshold-like structure imposed jointly by bounded range and diminishing marginal gains.
We then prove a hypergrid switching lemma for pseudo-DNFs, using low-depth -ary decision trees in place of binary trees. Combined with Fourier analysis on the hypergrid, this implies sparse Fourier approximation for bounded-width pseudo-DNFs. The resulting learner, together with the Kushilevitz-Mansour algorithm [11], yields the bounded-range tester.
1.4 Discussion and Open Problems
Our results leave several natural questions open. The most immediate is whether full –submodularity can be tested in Hamming distance with sub-exponential query complexity. Our component testers for diminishing marginal gains and pairwise monotonicity show that each constraint has many local witnesses when violated, but the repair procedures for the two constraints can be forced to conflict. Resolving this – either by exhibiting a richer witness family with a compatible repair procedure, or by proving a sub-exponential lower bound that confirms the barrier is fundamental – is, in our view, the right next step in this regime.
A second direction is to understand the bounded-range setting without monotonicity. Our tester in this regime relies on a pseudo-DNF representation for monotone –submodular functions, and it is unclear whether a comparable representation exists for non-monotone functions.
Finally, it would be interesting to prove lower bounds for testing –submodularity. The known lower bounds for submodularity do not transfer directly, since natural embeddings can destroy pairwise monotonicity. Thus even formulating the right hard instances appears to require using the genuinely multi-part structure of the domain.
1.5 Organization
The paper is organized as follows. In Section 2, we formally define the problem and related structures on the hypergrid. In Section 3, we prove the junta approximability theorem for –submodular functions. In Section 4, we develop Hamming-distance testers for diminishing marginal gains and pairwise monotonicity, and analyze the obstruction to combining their repairs into a local-repair tester for full –submodularity. We refer to the full version of the paper [9] for the analysis of the hypergrid implicit-learning theorem and construction of our tester for monotone –submodularity in the bounded range regime.
2 Preliminaries
Definition 6 (Partial partition).
A partial partition of into subsets is defined , where each and for all . We let , and this allows us to associate partial partitions of into subsets with the hypergrid (each element of is associated to a bucket in , yielding a vector in ). If , we say that . We impose a partial order on partial partitions by defining if and only if for all . We let denote the item-weight of a partial partition, which is the total number of items picked. Numerically, this is equal to .
Definition 7 (Marginal gains).
Define the marginal gains of a function on a partial partition with respect to an index and an element as
Letting , we can rewrite this as .
Definition 8 (–submodularity).
A function is –submodular if, for all partial partitions , the following holds.
where and
The following theorem of Ward and Živnỳ [17] gives us an equivalent definition of –submodularity, one that is described by two more intuitive properties. The intuition is that every local comparison between two partial partitions can be decomposed into compatible and conflicting moves. Compatible moves are governed by the usual diminishing-returns principle: adding an unassigned element to part becomes less valuable as the current partial partition grows. Conflicting moves arise only when the same element could be assigned to two different parts. For example, comparing and gives and , so the –submodular inequality becomes
Thus pairwise monotonicity is the local condition that prevents two competing assignments of the same element from both being too costly.
Theorem 9 ([17]).
A function is –submodular if and only if the following two conditions hold.
-
Diminishing marginal gains. For all partial partitions such that , , and , the following holds.
-
Pairwise monotonicity. For all partial partitions , , and , the following holds.
3 Junta approximation of –submodular functions
In the following two sections, we prove the structural and algorithmic ingredients behind our tester for –submodularity. The structural ingredient is a junta approximation theorem for –submodular functions on the hypergrid. The main difficulty is choosing influential coordinates in a way that accounts for all directions of a coordinate while still giving a dimension-independent approximation.
This approximation theorem, combined with an implicit learning tester for properties on hypergrids with a good junta approximation, yields the desired tester.
We prove the following approximation theorem.
Theorem 10 (Reminder of Theorem 2).
Let be a –submodular function and be a small enough constant. Then there exists a –submodular function that depends only on dimensions, where
and the functions satisfies
Before we get to the proof of Theorem 2, we first set up some necessary machinery.
3.1 Setup
There are three main parts to the setup.
Boosting lemma.
We cite the following boosting lemma due Goemans and Vondrák [7].
Definition 11 (Down-monotone family).
Let be a finite set and be a collection of subsets of . The family is called down-monotone if the following condition holds.
Lemma 12 ([7] Boosting lemma).
Let be a finite set and be a down-monotone family. For , define
where is a random subset of such that each element is picked independently with probability . Then
where is a non-decreasing function for .
Self–bounding functions and concentration.
A very useful tool in bounding the variance of submodular functions comes from the literature of concentration for self–bounding functions.
Definition 13 (Self–bounding function).
A function is -self–bounding if there exist functions such that for all and all , the following conditions hold.
-
1.
; and
-
2.
.
Lemma 14 ([2] Bounded variance lemma).
If a function is -self–bounding then
Bounded variance of –submodular functions.
Submodular functions that are Lipschitz are self–bounding, which allows us to bound their variance. We show that a similar property holds for –submodular functions.
Definition 15 (Lipschitz function).
A function is -Lipschitz if for all and .
Lemma 16.
Let be –Lipschitz and –submodular. Then:
Proof.
We prove this by showing that is -self–bounding, and invoking Lemma 14. For , define the function as
Then the first condition
holds trivially (by choice of minimum value and the range of being ). By pairwise monotonicity of , the following holds.
Here, corresponds to item not being put into any bucket. Finally, the following holds for all due to the marginal gains property.
This yields the desired condition.
We have thus shown that is 2-self–bounding, and by Lemma 16, .
3.2 Weak junta approximation
We first prove the following “weak” junta approximation for –submodular functions.
Theorem 17 (Weak junta approximation).
Let be a –submodular function and be a constant. Then there exists a –submodular function that depends only on dimensions, where
and the function satisfies
We prove Theorem 17 by first describing a procedure to construct the set and then showing that there exists a -junta satisfying the desired properties.
Let and be some partition function over . We denote by the point on the hypergrid obtained by placing each into bucket . We denote by a random set generated by sampling each element in independently with probability .
First we show that the number of indices picked by Algorithm 1 is small.
Claim 18.
The set output by Algorithm 1 satisfies .
Proof.
Let be an arbitrary partition of , and be an arbitrary subset of . For any , let denote the set of items in that were added to before in Algorithm 1. Define
Then by diminishing marginal gains, at the end of the execution of Algorithm 1, we have
Next, we show that . If that is true, then
To prove our claim, we observe that by construction, for all ,
Writing , where is the indicator for whether , we get
Next, we show that for all partitions and any “unimportant” coordinate , the probability of the marginal gains on top of being large with respect to when adding to is very small if we sample elements from with probability rather than .
Claim 19.
For all , all , and all partitions , the following holds.
Proof.
Consider the following family of points
This is a down-monotone set – if then . This is due to diminishing marginal gains – . If we let for , then by Lemma 12,
for some non-decreasing function . The termination condition of Algorithm 1 guarantees that
which implies for . Since is non-decreasing, we have
We now define our junta function. Let . Define as
| (1) |
where is the point in the hypergrid where the coordinates in are assigned as they were in and the coordinates in are non-assigned.
First, we show that is –submodular.
Claim 20.
The function defined in Equation 1 is –submodular.
Proof.
We have to show that satisfies the two following conditions.
-
1.
Diminishing marginal gains. Let with and . Let . Then, we have
If , then as well, so the diminishing marginal gains condition holds. Otherwise, by the –submodularity of , we know that for all ,
which allows us to conclude that , and thus that satisfies diminishing marginal gains.
-
2.
Pairwise Monotonicity. Let , and . If , then . Otherwise, by the pairwise monotonicity of ,
We can thus conclude by Theorem 9 that is –submodular.
Our final step is to show that is a good approximation to in the -norm.
Definition 21 (Bad points).
A point in the restricted hypergrid is called bad if there exists and such that
or there exists
The distance can be bounded as below.
We first show that for appropriate parameters to Algorithm 1, the probability that a point is bad is small.
Claim 22.
If we set in Algorithm 1, then
Proof.
Recall that we consider a uniform distribution over . This distribution is the same as sampling a partition uniformly at random and returning . To see this, fix an arbitrary point . Let and . The probability of generating this particular with the latter sampling procedure is
So, via a union bound, Claim 19 and by plugging in , we get that
Finally, we show that for appropriate parameters to Algorithm 1, the variance of when is good is small.
Claim 23.
If we set in Algorithm 1, then
Proof.
When is good, we have that the marginal gain of adding any to any bucket is at most . Because of diminishing marginal gains, this bounds the marginal gains of over its entire domain by . Also, the marginal gains of are at least , because if there existed some , and with , then by pairwise monotonicity we must have for all that as
But this contradicts the upper bound of to the marginal gains. Thus, is –Lipschitz and we can appeal to Lemma 14 to get
We are now ready to finish the proof of Theorem 17.
Proof of Theorem 17.
We let by the output of Algorithm 1 with input and parameters
Then the function defined by Equation 1 is the desired junta function. Indeed, combining (22) and (23), we get
To bound the size of , we use Claim 18 to get
Using the weak junta approximation, we are able arrive at our final junta approximation.
3.3 Proof of Theorem 2
Let be a –submodular function. We will prove a bound of for the size of the approximating junta.
Observe that this bound holds trivially for , because then we are allowed to choose . For contradiction, suppose that there is for which the statement of Theorem 2 does not hold. Let be the set of all for which the statement does not hold, and pick an such that . Then, the statement still holds for .
By the statement of Theorem 2 for , there is a subset of variables of size and a –submodular function depending only on , such that .
Now we apply Theorem 17 to with parameter . Thus, there exists a –submodular function such that , and depends only on a subset of variables , . We have , and therefore (using ). We conclude that as required in Theorem 2. By the triangle inequality, we have .
However, this would mean that the statement of Theorem 2 holds for as well, which is a contradiction. ∎
4 Towards testing –submodularity in the -norm
In this section, we develop the local-witness theory for the two constraints that characterize –submodularity in Hamming distance. For diminishing marginal gains, the witnesses are generalized violated squares. For pairwise monotonicity, the witnesses are violated triangles. We prove that if either constraint is far from being satisfied, then the corresponding witnesses are dense enough to be found by a non-adaptive one-sided tester. The key step in both cases is a repair argument over ideals and filters in the hypergrid.
4.1 Setup
An inductive argument shows that absence of violating squares is equivalent to the diminishing marginal gains property:
Proposition 24.
A function satisfies the diminishing marginal gains property if and only if it has no violating squares.
Proof.
If a function satisfies the diminishing marginal gains property, then it is easy to see that it has no violating squares: take . We show the converse by considering , and . Suppose are the elements of not in that have . Then we have that:
By induction we can telescopically build the partial partition on the right hand side and recover the diminishing marginal gains property.
Definition 25 (Violating triangle).
Let , , and . We call a triangle. For a function , this is called an –violating triangle if
that is, it violates the pairwise monotonicity condition.
4.2 Testing diminishing marginal gains
We prove the following theorem.
Theorem 26.
Algorithm 2 has the following properties.
-
1.
If has diminishing marginal gains, then Algorithm 2 accepts with probability .
-
2.
If is -far from diminishing marginal gains, then Algorithm 2 rejects with probability at least .
-
3.
Algorithm 2 makes queries.
Items 1 and 3 are easy to verify – they are direct consequences of Theorem 9 and the description of Algorithm 2, respectively. The rest of this section will be dedicated to proving Item 2.
Intuitively, our proof proceeds as follows. We first show that if a function has a “low density” of violating squares, then it can be made to have the diminishing marginal gains property by changing the values of only a “few” points. By contrapositive, this means that a function that is “far” from diminishing marginal gains must have a “high density” of witnesses, which implies the correctness of our tester. To “repair” a function towards diminishing marginal gains, we modify its values over a union of ideals and filters, defined as follows.
Definition 27 (Ideal).
Let . The Ideal of is defined as
Definition 28 (Filter).
Let . The Filter of is defined as
We start with the following “repair” lemma for violating squares.
Lemma 29 (Square repair lemma).
Let be a function in which is an –violating square. There is a way to change only the values of the ideal or the filter to obtain a function in which is no longer an –violating square, and no additional –violating squares have been introduced.
Proof.
Because is an –violating square, we have
Fix any constant . We obtain by subtracting from for all . Clearly, this repairs the –violating square itself, but we must also argue that it does not introduce any new –violating squares.
Let be an –violating square that is not –violating. If , then none of the values in the square were modified. So we can assume . We consider the following cases.
-
1.
Neither nor . Then the points are not modified. Thus, the value of this square is
-
2.
Only and . Then the points are not modified. Thus, the value of this square is
The case of and is symmetric and identical.
-
3.
Both and . Then , and all the points are modified. Thus, the value of this square is
As a result, we have shown that no new violating squares are introduced after changing all the values in , and the original violating square rooted in is repaired. An identical argument suffices to prove that subtracting from the filter has the same consequence.
The proof of this lemma also implies the following corollary.
Corollary 30.
Let be a function and be a domain point. For any constant , the function obtained by subtracting from for all or all does not introduce any new –violating squares.
Next, we prove the following density lemma.
Lemma 31.
Let be a function with violating squares. If for , then can be made to have diminishing marginal gains by changing at most values.
Proof.
The proof is a counting argument on the number of points we will need to change by the square repair procedure above. We enumerate all violating squares and arrange them in order of item-weight (equal to ) of the bottom point. We split the hypercube evenly based on item-weight. It can be verified that this split occurs at weight .
-
1.
For violating squares where the bottom vertex has item-weight , we repair them by modifying values in the ideal. Let denote the bottom vertex in these violating squares. Then the total number of modified points is .
-
2.
For violating squares where the bottom vertex has item-weight , we repair them by modifying values in the filter. Let denote the top vertex in these violating squares. Then the total number of modified points is .
We first prove the counting argument for Item 1. We estimate this cardinality by combining two different bounds across levels of the hypergrid. Let . Then we can write
We can bound these terms in two ways. First, we have
Second, there is the more trivial bound of
This second bound is reminiscent of the binomial distribution . Combining this with a Chernoff bound, we can get an upper bound on the number of points with item-weight far from the mean. Now we just have to use the correct bound depending on .
-
1.
If for some constant , then
-
2.
If , then
Finally, setting yields
This concludes the counting argument for Item 1.
The counting argument for Item 2 is almost identical. We split the filters by level, and for , the Chernoff-inequality based upper bound still holds. For , we get the following bound.
The rest of the counting argument is exactly the same and thus omitted.
In conclusion, we need to modify values to make have diminishing marginal gains.
We are now ready to finish the analysis of our tester.
Proof of Theorem 26.
We prove each part separately.
-
1.
By Theorem 9, a function with diminishing marginal gains does not have any –violating squares. As a result, the tester will always accept.
-
2.
By the contrapositive of Lemma 31, a function that is -far from diminishing marginal gains has at least violating squares. The total number of squares is . Thus, by the witness lemma, queries suffice to catch an –violating square with high probability.
-
3.
This follows trivially from the design of the algorithm.
This completes the analysis of Algorithm 2.
4.3 An obstruction to component-wise local repair
The component testers of the previous two sections each rest on a dense witness theorem and a local repair argument. A natural attempt at a tester for full –submodularity is to apply both component testers in parallel and union-bound the failure probability over the two repair arguments. We now show that this attempt cannot succeed: there exist configurations on which the repair direction prescribed by a triangle witness is forced to oppose the repair direction prescribed by an overlapping square witness on a shared vertex.
For ideals rooted at item-weight , the repairs for both witness types proceed downward and can be aligned. The obstruction lives in the upward direction. On filters rooted at item-weight , repairing a violated square requires subtracting from a vertex, whereas repairing a violated triangle in the same filter requires adding to that vertex. The configuration in Figure 1 realizes both demands simultaneously on the vertices and .
The configuration is not isolated to a small region of the hypergrid. Embedding the same value pattern into any high-item-weight filter on a larger domain produces an instance of the same conflict, so an ideal-only repair strategy that avoids upward filters cannot route around it without losing the balance argument that makes the component testers work.
Observation 32 (Component-wise repair is insufficient).
For every there exist functions and high item-weight filters on which a violated triangle witness and an overlapping violated square witness prescribe local repairs of opposite sign on a common vertex. In particular, the standard component-wise repair argument – repair triangles and squares independently and combine via union bound – does not yield a tester for -submodularity.
Observation 32 does not rule out a Hamming-distance tester for -submodularity; it shows only that obtaining one will require either a richer witness vocabulary that simultaneously certifies both component constraints, or a non-local repair scheme that mediates between square and triangle repairs across the hypergrid.
References
- [1] Eric Blais and Abhinav Bommireddi. Testing submodularity and other properties of valuation functions. arXiv preprint arXiv:1611.07879, 2016. arXiv:1611.07879.
- [2] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208–240. Springer, 2003. doi:10.1007/978-3-540-28650-9_9.
- [3] Deeparnab Chakrabarty and Zhiyi Huang. Recognizing coverage functions. SIAM Journal on Discrete Mathematics, 29(3):1585–1599, 2015. doi:10.1137/140964072.
- [4] Alina Ene and Huy Nguyen. Streaming algorithm for monotone k-submodular maximization with cardinality constraints. In International Conference on Machine Learning, pages 5944–5967. PMLR, 2022. URL: https://proceedings.mlr.press/v162/ene22a.html.
- [5] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms, pages 182–194. Springer, 2010. doi:10.1007/978-3-642-15775-2_16.
- [6] Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 45(3):1129–1170, 2016. doi:10.1137/140958207.
- [7] Michel X Goemans and Jan Vondrák. Covering minimum spanning trees of random subgraphs. Random Structures & Algorithms, 29(3):257–276, 2006. doi:10.1002/RSA.20115.
- [8] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653–750, 1998. doi:10.1145/285055.285060.
- [9] Themistoklis Haris and Diptaksho Palit. Testing k-submodularity. CoRR, abs/2606.30433, 2026. doi:10.48550/arXiv.2606.30433.
- [10] Pooya Hatami and Jan Vondrák. Testing real-valued modularity and submodularity, 2016. URL: https://www.ias.edu/sites/default/files/math/csdm/15-16/HatamiVondrak.pdf.
- [11] Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Comput., 22(6):1331–1348, 1993. doi:10.1137/0222080.
- [12] Naoto Ohsaka and Yuichi Yoshida. Monotone k-submodular function maximization with size constraints. Advances in Neural Information Processing Systems, 28, 2015.
- [13] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM Journal on Computing, 32(5):1158–1184, 2003. doi:10.1137/S0097539702414026.
- [14] Sofya Raskhodnikova. CS 599: Sublinear Algorithms (Spring 2025). https://cs-people.bu.edu/sofya/sublinear-course/, 2025. Retrieved on 10 October, 2025. URL: https://cs-people.bu.edu/sofya/sublinear-course/.
- [15] Sofya Raskhodnikova and Grigory Yaroslavtsev. Learning pseudo-boolean k-dnf and submodular functions. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1356–1368. SIAM, 2013. doi:10.1137/1.9781611973105.98.
- [16] Comandur Seshadhri and Jan Vondrák. Is submodularity testable? Algorithmica, 69(1):1–25, 2014. doi:10.1007/S00453-012-9719-2.
- [17] Justin Ward and Stanislav Živnỳ. Maximizing k-submodular functions and beyond. ACM Transactions on Algorithms (TALG), 12(4):1–26, 2016. doi:10.1145/2850419.
