<p>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...</p>

CC BY-SA 3.0
2013-05-24T22:01:18.037Z
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)$.
Jeffε
CC BY-SA 3.0
2013-05-26T05:05:47.953Z
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.
domotorp
CC BY-SA 3.0
2013-05-27T14:11:12.413Z
@ 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.
Gorav Jindal
CC BY-SA 3.0
2013-05-28T07:19:43.493Z
For the definition of lower envelopes, see: http://en.wikipedia.org/wiki/Davenport%E2%80%93Schinzel_sequence#Application_to_lower_envelopes
domotorp
CC BY-SA 3.0
2013-05-28T07:22:42.787Z
For duality, see: http://www.cs.uiuc.edu/~jeffe/teaching/compgeom/notes/schreiber.pdf
domotorp
CC BY-SA 3.0
2013-05-28T14:36:45.320Z
@ domotorp, any references for the fact that "if you have a convex polygon with integer vertices in $[0,K]^2$, then it can have at most $O(K^\frac 23)$ sides"
Gorav Jindal
CC BY-SA 3.0
2013-05-28T14:58:27.467Z
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].
domotorp
CC BY-SA 3.0
2013-05-28T19:30:38.580Z
@domotorp, almost understood your argument. But few confusions. When you say "vector", you mean difference of end points of sides? And also, when you say "But having $\frac{1}{2}K^{\frac{2}{3}}$ vectors of length $\geq K^{\frac{1}{3}}$ pushes us out from $[0,K]$", I don't really get this statement.
Gorav Jindal
CC BY-SA 3.0
2013-05-29T06:31:22.763Z
1-yes, I mean that difference.
domotorp
CC BY-SA 3.0
2013-05-29T06:33:39.197Z
2-the vectors that belong to the $[0,K]^2$ quadrant must come after each other as the sides of the convex polygon. This means that if you sum all of them up, you get a vector between two vertices of the polygon. That should be again in $[0,K]^2$, but it won't be, as the sum of either the $x$- or the $y$-coordinates will be bigger than $K$.
domotorp
CC BY-SA 3.0
2013-05-29T08:26:07.950Z
@domotorp, For sum to be bigger than $K$, don't we need $K^{\frac{2}{3}}$ vectors instead  of $\frac{1}{2}K^{\frac{2}{3}}$?
Gorav Jindal
CC BY-SA 3.0
2013-05-29T10:34:28.983Z
Yes, you are right, so then let us start with 16 instead of 8.
domotorp
CC BY-SA 3.0
2013-05-29T16:00:23.713Z
@domotorp, Many many thanks for your patience. I think I understand your solution now.
Gorav Jindal
CC BY-SA 3.0
2013-05-24T12:50:25.633Z
2013-05-24T12:50:25.633Z
domotorp
<p>Klivans and Spielman give isolation lemma for linear forms in their paper <a href="http://www.cs.utexas.edu/~klivans/ran3.ps" rel="nofollow">Randomness Efficient Identity Testing of Multivariate Polynomials</a>. Lemma 4 in this paper says.</p>

<blockquote>
  <p>"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$".</p>
</blockquote>

<p>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$.</p>

<p>Let me introduce a different notion of "stronger". Suresh Chari, Pankaj Rohatgi and  Aravind Srinivasan give <strong>Generalized isolating lemma</strong> in their paper <a href="http://ecommons.cornell.edu/handle/1813/6129" rel="nofollow">Randomness-Optimal Unique Element Isolation, With Applications to Perfect Matching and Related Problems</a>. Lemma 2[Generalized isolating lemma] in this paper says</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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 <a href="http://www.cs.utexas.edu/~klivans/ran3.ps" rel="nofollow">Randomness Efficient Identity Testing of Multivariate Polynomials</a>. We also want that weights should not be too large, again weights sublinear in $K$ should be interesting.</p>

CC BY-SA 3.0
2013-05-29T16:02:50.193Z
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$.
Gorav Jindal
<cc.complexity-theory>
Stronger version(2) of Isolation Lemma for linear forms
Gorav Jindal
# Stronger version(2) of Isolation Lemma for linear forms

(Asked by: username_0 on 2013-05-12)

Klivans and Spielman give isolation lemma for linear forms in their paper [Randomness Efficient Identity Testing of Multivariate Polynomials](http://www.cs.utexas.edu/~klivans/ran3.ps). 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](http://ecommons.cornell.edu/handle/1813/6129). 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](http://www.cs.utexas.edu/~klivans/ran3.ps). We also want that weights should not be too large, again weights sublinear in $K$ should be interesting.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_0**: 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$.  

---

## 1 answers

### Answer by username_1 on 2013-05-24. Score: 5 | Accepted answer

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...

> **Comments:**
> **username_2**: 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)$.  
> **username_1**: 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.  
> **username_0**: @ 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.  
> **username_1**: For the definition of lower envelopes, see: http://en.wikipedia.org/wiki/Davenport%E2%80%93Schinzel_sequence#Application_to_lower_envelopes  
> **username_1**: For duality, see: http://www.cs.uiuc.edu/~jeffe/teaching/compgeom/notes/schreiber.pdf  
> **username_0**: @ domotorp, any references for the fact that "if you have a convex polygon with integer vertices in $[0,K]^2$, then it can have at most $O(K^\frac 23)$ sides"  
> **username_1**: 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].  
> **username_0**: @domotorp, almost understood your argument. But few confusions. When you say "vector", you mean difference of end points of sides? And also, when you say "But having $\frac{1}{2}K^{\frac{2}{3}}$ vectors of length $\geq K^{\frac{1}{3}}$ pushes us out from $[0,K]$", I don't really get this statement.  
> **username_1**: 1-yes, I mean that difference.  
> **username_1**: 2-the vectors that belong to the $[0,K]^2$ quadrant must come after each other as the sides of the convex polygon. This means that if you sum all of them up, you get a vector between two vertices of the polygon. That should be again in $[0,K]^2$, but it won't be, as the sum of either the $x$- or the $y$-coordinates will be bigger than $K$.  
> **username_0**: @domotorp, For sum to be bigger than $K$, don't we need $K^{\frac{2}{3}}$ vectors instead  of $\frac{1}{2}K^{\frac{2}{3}}$?  
> **username_1**: Yes, you are right, so then let us start with 16 instead of 8.  
> **username_0**: @domotorp, Many many thanks for your patience. I think I understand your solution now.  

---

