7
$\begingroup$

Klivans and Spielman give isolation lemma for linear forms in their paper Randomness Efficient Identity Testing of Multivariate Polynomials. Lemma 4 in this paper says.

"Let $C$ be any collection of distinct linear forms in variables $z_1\ldots z_l$ with coefficients in range {$0,\ldots, K$}. If $z_1,\ldots,z_l$ are independently chosen uniformly at random from set $S = \{0\ldots Kl/\epsilon\}$, then with probability greater than 1-$\epsilon$, there is a unique form of minimal value at $z_1,\ldots,z_l$".

Is there a stronger version of this lemma? Namely, can we choose set $S$ to be of size sublinear in $K$? Assume that $l$ is small compared to $K$.

Let me introduce a different notion of "stronger". Suresh Chari, Pankaj Rohatgi and Aravind Srinivasan give Generalized isolating lemma in their paper Randomness-Optimal Unique Element Isolation, With Applications to Perfect Matching and Related Problems. Lemma 2[Generalized isolating lemma] in this paper says

Let ($S$, $\mathcal{F}$) be any set system and let $Z$ be a give upper bound on the size of unknown family $\mathcal{F}$. There is a simple scheme which uses $O(\log Z + \log N)$ random weights to assign integer weights to the $x_i$'s in the range $[0,N^7)$ such that with probability atleast $\frac{1}{4}$, there is a unique minimum weight set in $\mathcal{F}$. Here $S=\{x_1,x_2,\ldots x_N\}$ and $\mathcal{F}\subset2^S$.

Do we have something similar for isolating linear forms? Namely, if we know that number of linear forms is bounded by $Z$, can we reduce random bits as compared to $O(N\log(KN))$ random bits used in Randomness Efficient Identity Testing of Multivariate Polynomials. We also want that weights should not be too large, again weights sublinear in $K$ should be interesting.

Improve this question
$\endgroup$
1
  • $\begingroup$ First part of question has been solved by domotorp. But I think it's still interesting to reduce number of bits when we know that number of linear forms is bounded by some $Z$. $\endgroup$
    – Gorav Jindal
    Commented May 29, 2013 at 16:02

1 Answer 1

Reset to default
5
+100
$\begingroup$

For your first question, if $l=1$, then $\frac{K^\frac 23}\epsilon$ is sufficient. This follows the fact that the lower envelope of some lines has the same complexity as the upper convex hull of its dual point system and if you have a convex polygon with integer vertices in $[0,K]^2$, then it can have at most $O(K^\frac 23)$ sides. I know I did not explain the details, but this is anyhow only a partial answer to your question...

Improve this answer
$\endgroup$
13
  • $\begingroup$ Nice observation! In fact, plugging this directly into Klivans and Spielman's proof reduces their bound from $Kl/\epsilon$ to $O(K^{2/3}l/\epsilon)$. $\endgroup$
    – Jeffε
    Commented May 24, 2013 at 22:01
  • 1
    $\begingroup$ Then up to the $l$ factor, this is best possible, as the above also gives a construction with $\Omega(K^\frac 23/\epsilon)$ non-unique minimal values. $\endgroup$
    – domotorp
    Commented May 26, 2013 at 5:05
  • $\begingroup$ @ domotorp, can you please explain your answer in more details? I do not have a heavy mathematics ground, so cannot understand your answer. If you can provide some details and also point to relevant definitions and techniques, it would be great. Thanks. $\endgroup$
    – Gorav Jindal
    Commented May 27, 2013 at 14:11
  • $\begingroup$ For the definition of lower envelopes, see: en.wikipedia.org/wiki/… $\endgroup$
    – domotorp
    Commented May 28, 2013 at 7:19
  • 1
    $\begingroup$ I can give you the proof instead. Suppose it has $8K^\frac 23$ sides. Direct them clockwise. Each becomes a vector from $[-K,K]^2$ and each vector can occur at most once. In one of the quadrants, say $[0,K]^2$, there are at least $2K^\frac 23$ vectors. At most $K^\frac 23$ of these are in $[0,K^\frac 13]^2$. The rest are either long in the $x$-direction or in the $y$-direction. But having $\frac 12 K^\frac 23$ vectors of length $\ge K^\frac 13$ pushes us out from [0,K]. $\endgroup$
    – domotorp
    Commented May 28, 2013 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.