Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MATCHING VECTOR FAMILIES:
Reports tagged with matching vector families:
TR13-061 | 17th April 2013
Zeev Dvir, Guangda Hu

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>> TR24-061 | 5th April 2024 Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi #### Improved Lower Bounds for 3-Query Matching Vector Codes A Matching Vector ($\mathbf{MV}$) family modulo a positive integer$m \ge 2$is a pair of ordered lists$\mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K)$and$\mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K)$where$\mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n$with the following property: for any$i \in [K]$, the inner product$\langle \mathbf{u}_i, \mathbf{v}_i \rangle ... more >>>

ISSN 1433-8092 | Imprint