Return to Question

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\mathbf{w}^{\top}\mathbf{v}$ (assume that $\mathbf{w}^{\top}\mathbf{v}\neq 0$ for all $\mathbf{v}\in S$). Set $S$ is known, but both the labelling assignment of its points and vector $\mathbf{w}$ are initially unknown. In a sequential fashion, at each time step, we can select one point of $S$ and ask for its label. Then its label is revealed.

Question: What is the minimum number $q$ (expressed as a function of $n$ and $d$) of point label queries necessary to determine the labels of all points in $S$, over all possible sets $S\in\mathbb{R}^d$?

Example: If $d=1$, $q$ is logarithmic in $n$.

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\mathbf{w}^{\top}\mathbf{v}$ (assume that $\mathbf{w}^{\top}\mathbf{v}\neq 0$ for all $\mathbf{v}\in S$). Set $S$ is known, but both the labelling assignment of its points and vector $\mathbf{w}$ are initially unknown. 

In a sequential fashion, at each time step, we can select one point of $S$ and ask for its label. Then its label is revealed.

Question: What is the minimum number $q$ (expressed as a function of $n$ and $d$) of point label queries necessary to determine the labels of all points in $S$, over all possible sets $S\in\mathbb{R}^d$?

Example: If $d=1$, $q$ is logarithmic in $n$.

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\mathbf{w}^{\top}\mathbf{v}$ (assume that $\mathbf{w}^{\top}\mathbf{v}\neq 0$ for all $\mathbf{v}\in S$). Set $S$ is known but both the labelling assignment of its points and vector $\mathbf{w}$ are initially unknown. In a sequential fashion, at each time step, we can select one point of $S$ and ask for its label, so that its label is revealed.

Question: What is the minimum number $q$ (expressed as a function of $n$ and $d$) of point label queries necessary to determine the labels of all points in $S$, over all possible sets $S\in\mathbb{R}^d$?

Example: If $d=1$ clearly $q$ is logarithimic in $n$.

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\mathbf{w}^{\top}\mathbf{v}$ (assume that $\mathbf{w}^{\top}\mathbf{v}\neq 0$ for all $\mathbf{v}\in S$). Set $S$ is known, but both the labelling assignment of its points and vector $\mathbf{w}$ are initially unknown. In a sequential fashion, at each time step, we can select one point of $S$ and ask for its label. Then its label is revealed.

Question: What is the minimum number $q$ (expressed as a function of $n$ and $d$) of point label queries necessary to determine the labels of all points in $S$, over all possible sets $S\in\mathbb{R}^d$?

Example: If $d=1$, $q$ is logarithmic in $n$.

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\mathbf{w}^{\top}\mathbf{v}$. Set $S$ is known but both the labelling assignment of its points and vector $\mathbf{w}$ are initially unknown. In a sequential fashion, at each time step, we can select one point of $S$ and ask for its label, so that its label is revealed.

Question: What is the minimum number $q$ (expressed as a function of $n$ and $d$) of queries necessary to determine the labels of all points in $S$, over all possible sets $S\in\mathbb{R}^d$?

Example: If $d=1$ clearly $q$ is logarithimic in $n$.

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\mathbf{w}^{\top}\mathbf{v}$ (assume that $\mathbf{w}^{\top}\mathbf{v}\neq 0$ for all $\mathbf{v}\in S$). Set $S$ is known but both the labelling assignment of its points and vector $\mathbf{w}$ are initially unknown. In a sequential fashion, at each time step, we can select one point of $S$ and ask for its label, so that its label is revealed.

Question: What is the minimum number $q$ (expressed as a function of $n$ and $d$) of point label queries necessary to determine the labels of all points in $S$, over all possible sets $S\in\mathbb{R}^d$?

Example: If $d=1$ clearly $q$ is logarithimic in $n$.