Кодово-комбинаторный подход к задаче двоичных сжатых измерений или поиск со лжецом

Начнем с выпуклых многогранников, вершины которых берутся из булева куба $B^d=\{0,1\}^d\subset \mathbb{R}^d$, т.е. будем рассматривать выпуклые оболочки
$$ < A >=\{\sum_{a\in A} \lambda_a a:\sum_{a\in A} \lambda_a=1,\; \lambda_a\geq 0\} $$
множеств $A\subset B^d$ мощности не более $t$. Множество $\mathcal{C}$ вершин $d$-мерного булева куба $B^d$ будем называть $t$-независимым, если для любых двух его непересекающихся подмножеств $A,B\subset \mathcal{C}$ таких, что $|A|,|B|\leq t$, их выпуклые оболочки не пересекаются.
Вопрос. Чему равна максимально возможная мощность $m_t(d)$ $t$-независимого множества в $B^d$?
Ответ: $m_t(d)=2^{c_td}$, где $c_t=\Omega(t^{-1}\log t)$.\ Эта задача является частным случаем задачи о поиске фальшивых монет на точных весах, когда веса фальшивых монет могут быть различны и априори неизвестны. А последняя задача может рассматриваться как задача о нахождения носителя неизвестного $t$-разреженного вектора $x\in {\mathbb R}^d$ по результатам линейных измерений, что, в свою очередь, является подзадачей задачи сжатых измерений.
Мы предлагаем новый подход построения двоичных матриц измерений, основанный на разделяющих кодах и отличный от RIP-матриц, который позволяет решать перечисленные выше задачи.