Today, I'll be talking about the paper, property testing of LP-type problems, and this is joint work with Rogers Epstein. First, I'll briefly define our problem.

Then I'll state our main result about LP-type problems. I'll give some corollaries of our main result. And finally, I'll give a sample of some of the lower bounds that we have. So what exactly is property testing? In property testing, we assume we have a huge object. It could be a graph, a string, or points in R to the D.

Then we assume that we have corollaries to access this huge object at a specific location. In the case of a graph, our corollaries could be get the degree of some vertex v or get the third neighbor of v, and so on. And our goal is to determine

if the object has some property p or if it's far from having p. So some properties that we might be interested include, is it graph bipartite, is it acyclic, in the graph case. And by far, we mean that the object must be changed a lot to satisfy the property p.

What do we mean by a lot? We have some parameter epsilon, and we say the object is epsilon far if an epsilon fraction of the representation of the object must be changed for the object to satisfy p. So again, in the case of a graph, epsilon far would mean that an epsilon fraction

of the edges of the graph need to be changed, either added or deleted, for the graph to satisfy the property p. So formally, our setting is the following. We're given corollary access to some object, a specified property p, and a parameter epsilon.

And our goal is to give an algorithm that has the following behavior. We want to accept with probability two thirds if the object satisfies p, and we want to reject with probability two third if the object is epsilon far from satisfying p. And of course, our goal is to use

as few queries as possible. In particular, we don't want to access the whole object. So this line of work has many interesting results. Too many to list here, and I would point the reader to the excellent book, Introduction to Property Testing by Goldwright

for a comprehensive list of references. So our setup in particular is the following. Our object is a set S of constraints. Our queries are, we can access the i-th constraint for any i,

and the property that we care about is, is phi of S at most k, where phi is some function over the constraints S. So for instance, phi is an objective function that we want to minimize, subject to the constraints in S. And by epsilon far, we mean that we have to remove

or change an epsilon fraction of the constraints in S to achieve phi of S's at most k. So of course, this alone is too broad. Many things can be modeled as S and some objective function phi. So we have to narrow our interest.

So in particular, we look at the case where S and phi satisfy a special structure known as LP type problems. And I'll go into more detail what that means in a bit. Just as a historical note, there have been related papers that study notions that are similar,

and I would point to our paper for a list of references. For instance, the paper by Shumai and Chola. So as intuition, in LP type problems, the constraints S have a special geometric structure that relates to the objective function phi.

And they are natural generalization of linear programs, even though the function phi doesn't have to be linear. And these types of problems have been extensively studied in computational geometry. So the formal definition of LP type problems

is the following. This S and phi satisfy the following two conditions. Monotonicity, which is defined as follows. For any set A and B where A is a subset of B, we have phi of A is at most phi of B,

and locality defined as in the screen. Intervally, what these two constraints or what these two conditions say are the following. Monotonicity says, adding more constraints makes it harder to minimize an objective function phi. And locality says that if we add a new constraint,

if we add two new constraints, x and y, and our objective value doesn't change, then adding them both at the same time also doesn't change our objective value. I'll give more concrete examples of LP type problems for the reader to internalize the intuition behind them.

So some examples are the following. S consists of linear programming constraints that we're used to. For instance, x1 plus x2 minus two x3 is at most phi. And phi is something like minimize the value of x1.

Or another example is the following. S could be a set of points in R to the D, and phi is, and the objective phi is to minimize the radius of the smallest enclosing ball. Translating this into the property testing version, we have the following. We're given a set S of points in R to the D,

some parameters k and epsilon. And we have to give an algorithm that accepts if the radius of the smallest enclosing ball of S is at most k, or in other words, if phi of S is at most k, and we have to reject if an epsilon fraction of the points in S need to be removed

to satisfy phi of S is at most k. So of course, both of these have to happen with probability two thirds, but let's ignore that for now. And our queries, again, are that we can access a particular point in S. So our main contribution is the following.

We give an algorithm for property testing of general LPTide problems. And the query complexity of our algorithm is over delta over epsilon, where delta is something that's known as the dimension of the LPTide problem. And intuitively, it's the intrinsic dimensionality of the problem. So something important to note is that often,

delta will be independent of the size of S. We also have some matching lower bounds for some specific problems. So formally, the dimension of an LPTide problem is the following. A subset B of S is called the basis if for all subsets B prime of B,

we have phi of B prime is less than phi of B. And the dimension delta of an LPTide problem is simply the largest cardinality of a basis. So let's give a concrete example. Note that D plus one points determine

the smallest enclosing ball of a set of points in R to the D. For instance, in the plane, three points will determine the smallest enclosing circle. So in the case of the smallest enclosing ball, the dimension of this problem is just D, in fact.

So the intuition for our main algorithm is the following. In the case that phi of S is actually at most K, or in the case that we need to accept, every subset of S will satisfy phi of B is at most K by the locality property of LPTide problems

that we talked about previously. Whereas in the epsilon of R case, we need to show that a large subset of B will violate phi of B is at most K, and we'll have to show that we can actually define such a subset B.

So our main algorithm is the following. First, we sample O of delta over epsilon constraints from S. We check that if phi of R is greater than K, in that case, we can reject and abort. Then we sample O of one over epsilon,

more constraints from S minus R. And then we check if phi of R unit X is not equal to phi of R. If this is the case, then we reject and abort. And at the end, if we haven't rejected, we accept.

So note that the query complexity is O of delta over epsilon, where delta is, again, the dimension of the LPTide problem that we care about. So some corollaries of our main result are that we get property testing versions of many classical LPTide problems,

some of which haven't been studied in the property testing world. So for instance, the smallest enclosing ball, which is testing at points in R to the D, can be covered by a ball of some radius R. Note that this problem has been studied previously. What's an example of other problems?

Include the smallest intersecting ball, testing if a set of closed convex bodies can be intersected by a ball of radius R or the smallest volume annulus, testing if a set of points in R to the D can be enclosed by an annulus of volume V, and so on. Something interesting is that the problems

that are listed here all have LPTide dimension D. So the query complexity of these problems is O of D over epsilon. But of course, this need not be the case, and we have many other examples. With slightly more work, we also get corollaries.

We also get the following corollaries. We can test if a set of linear inequalities in D dimension is feasible or if it's epsilon far from feasible. We can test if points in R to the D can be labeled with labels plus or minus one.

We can, sorry, we can test if points in R to the D labeled plus or minus one are linearly separable or not, or if epsilon far from that, and these problems also have query complexity of D over epsilon. Note that we can also generalize two labels to arbitrarily many labels in our paper.

So now let me discuss the correctness of our algorithm. Let's focus on the case that S and phi are epsilon far from satisfying, phi of S is at most k. Note that this is a case that we have to reject. So let's recall our algorithm

and check where it can possibly reject. In step two, if we reject, then that's fine, that only helps us. So let's just assume that we don't even reject in step two, and let's see what happens in step three. In step three, we claim that there must be at least epsilon times the size of S,

choices of X, for us to abort. Abort. So that's our claim. So why is this claim true? So this claim actually follows in a straightforward manner using the locality property of LPTide problems.

In particular, let's assume that phi of R union X is equal to phi of R is equal to phi of R union Y. Then by locality, we have phi of R is also the same as phi of R union X and Y, where X and Y are two constraints that are not in R already.

So if the claim was not true, then we could find a set S prime of S such that S prime has size at least one minus epsilon times the size of S, and S prime satisfies phi of S prime is at most k.

But this is impossible by assumption that we're in the epsilon-far case. So in particular, this claim holds true and we reject with sufficiently high probability in the far case. So in the second case, assume that S and phi do satisfy

phi of S is at most k. This is the case that we have to accept. To show that our algorithm does not reject in this case, we need the concept of violators. So a violator of a set R is a set of new constraints

that are not in R such that phi of R union X is not equal to phi of R. Note that finding a violator would mean that we reject, so we have to show that we won't find violators with high probability in our algorithm in the good case.

By good, I mean the case that we have to accept. So mathematically, this is a set of violators written again. So in the LPT type literature, there's a lemma known as the sampling lemma,

which roughly states that if R is chosen uniformly at random and S and phi is an LPT type problem, then the expected size of the violators can be bounded as follows. Expected size of the violators of R

is at most delta times size of S over the size of R. So informally, the sample lemma states that the number of violators is bounded by some function of the dimension of the LPT type problem. So I won't prove the sampling lemma here

since it's a well-known fact in the LPT type literature, but there are references in our paper. So let's go back to the correctness of the algorithm. Again, assuming that we are in the case that phi of S is at most K,

unless we call our algorithm. So note that in step two, we will never reject by the monotonicity property of LPT type problems, so we don't have to worry about that. And in step three, we claim that there aren't too many choices of X for us to find. In particular, we claim that there are less

than epsilon times S over 10 choices of X. In step 3a, that will abort. So that's our claim. So this claim follows from the sampling lemma. In particular, by just plugging in the size of R,

we get that there are at most epsilon times S over 10 choices of X that will cause us to abort. And we can work out the calculation that, you know, let's say sampling two over epsilon choices of X will not find any violators

with good enough probability by a standard calculation. So just as a historical note to the sampling lemma, this has been used in computational geometry to give fast randomized algorithms for LPT type problems. And there are some references that we presented at the end of the talk, but we won't prove it here

for the sake of time. So let me give a sample of some of the lower bounds we have. In particular, this is my favorite lower bound that we have in our paper. So our result implies that testing if points in R to the D that are labeled plus and minus one,

testing if these points are linearly separable or not, can be done in O of D over epsilon queries. And we will give an example that shows that this query complexity is actually tight.

So our lower bound is the following. Again, just to state where we want to show, we want to test if points in R to the D labeled plus or minus one, or test if these points are linearly separable. This testing problem requires at least D over epsilon queries.

So to do so, we will give two families of points, F1 and F2, such that F is linearly separable, while F2 is epsilon far from linearly separable. We call it epsilon far would mean either epsilon far of the points need to be removed or epsilon fraction of the points need to be removed

or an epsilon fraction of the labels need to be changed. Either works in our setting. We want to give these families F1 and F2 such that any algorithm would need at least D over epsilon queries to distinguish between these families.

So let's present a side lemma about what families to use. So let X sub i be the point defined as follows. Note that this point, these points live in R to the D. And the coordinates of these points are i, i squared, and so on up to i to the D.

And we'll have three D plus one many points, X sub i. And we claim that these points, X sub i that live in R to the D, sorry, this is a typo here, it should be they live in R to the D. These points satisfy the following two conditions.

There exists a labeling of these points yeah, sorry, S here refers to the set of points X sub i. We claim that there exists a labeling of these points such that at least D points would have to be relabeled

for these points to be linearly separable. And these labels are gonna be plus or minus one. And we also claim that any subset of three D plus one of these points can be arbitrarily labeled plus or minus one and they will be linearly separable.

So the proof of this claim is in our paper and to prove this, we use special properties of what's known as the moment curve. Okay, so given the existence of these special points, let's construct our families F1 and F2.

So F1 will be the following. We pick D plus one points in Xi. We'll copy D of them, epsilon n over D times, and we'll copy one of them, one minus epsilon times n times. And for the second family, we'll pick all of these points X sub i.

We'll copy three D of them, epsilon n over three D times and we'll copy one of them, one minus epsilon times n times. So in particular, F1 and F2 both have n points. So our previous claim about the properties of these points X sub i imply that F1 is linearly separable

while F2 is epsilon far from linearly separable. This is because our previous result tells us that any D plus one subset of these points Xi, X sub i can be linearly separable given arbitrary labels in plus and minus one.

While for F2, our results imply that we need to change many labels of the points in F2. And if we work out the calculation, we can show that an epsilon fraction of the points in F2 need to be relabeled

or removed. Now the crux of the lower bound is that to distinguish between F1 and F2, we need to discover D plus one unique points, X sub i and F2. Because if we don't, sorry,

we need to discover at least that many unique points because if we don't, then it looks like, then it looks like we only have, let's say D plus one points from X sub i, but in that case, we know the points are linearly separable.

So in particular, in the case that our set of points are F2, we need to discover many unique points X sub i. And now finally, a coupon collector type argument implies the query complexity. In particular, we need at least D over epsilon queries

to determine that there are many different points in F2. Remember that points in F2 are repeated, so we have to see what so-called unique points. And just on the screen, we just present the calculation. In our paper, we gave more details about it.

Yeah, so that concludes the proof for lower bound. Here are the references using the slides. And of course, there are more in our paper. And thank you for listening.