Original covering arrays video: • How Covering Arrays ca...
arXiv preprint: arxiv.org/pdf/...
Here we discuss a recent proof of mine of a conjecture in my research area, which has to do with sizes of covering arrays. I first go over what the problem, which is determining the asymptotic sizes (# of rows) of covering arrays of "higher index", which is to say each interaction must appear at least a certain number of times, instead of just once. I give "easy" upper and lower bounds; unlike the prior video's scenario, there is a "gap" between them. Next I give some upper bounds that have been published and are "better", but there is still a small gap. My proof this year is that there is no gap between the "easy" lower bound and the new upper bound I prove, which is logarithmic in the number of columns, and additively linear in the index.
This proof also uses the probabilistic method, but with a new ingredient: the Lambert W function. My proof first uses the Cauchy-Schwarz inequality on the equation coming from the probabilistic method. The C-S inequality relates cross correlations of sums (hard to understand) to self-correlations (easy to understand), but paying a penalty; in other words, sum(a_i * b_i) changes to sum(a_i^2) * sum(b_i^2) * penalty. Then we use simple known upper bounds on the two sums that come out. The final "trick" is to use the Lambert W function, which is the inverse of f(W) = W * e^W. One would have to analyze the equation that comes out, and notice where in the Lambert W function one is; in this case, it is in the negative region. To finish everything off, we use lower bounds on W since in this region, W is negative (which translates to upper bounds on covering array sizes).
Easy Theory Website: www.easytheory...
Discord: / discord
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
Негізгі бет I proved a math conjecture
Пікірлер: 6