<p>Let $H$ be $\{-1,+1\}$ Hadamard matrix of size $2$ and $J$ be the same size all $1$ matrix. Let $W$ be $\frac{H+J}{2}$. Is the discrepancy of $W^{\otimes k}$ atmost $\sqrt{k^{-1}}$?</p>

CC BY-SA 3.0
2014-12-15T16:44:39.987Z
There is more than one thing called "discrepancy" that applies to matrices. Do you mean the discrepancy used in communication complexity?
Sasho Nikolov
CC BY-SA 3.0
2014-12-15T16:47:53.437Z
@SashoNikolov Yes.
Turbo
CC BY-SA 3.0
2014-12-19T18:49:10.767Z
Your 'Hadamard type matrix" is just the disjointness matrix. The discrepancy is at least $(2k + 1)^{-1}$ but I am not sure what the tight upper bound is.
Sasho Nikolov
<co.combinatorics>
Discrepancy of Hadamard type matrix
Turbo
# Discrepancy of Hadamard type matrix

(Asked by: username_0 on 2014-12-15)

Let $H$ be $\{-1,+1\}$ Hadamard matrix of size $2$ and $J$ be the same size all $1$ matrix. Let $W$ be $\frac{H+J}{2}$. Is the discrepancy of $W^{\otimes k}$ atmost $\sqrt{k^{-1}}$?

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: There is more than one thing called "discrepancy" that applies to matrices. Do you mean the discrepancy used in communication complexity?  
> **username_0**: @SashoNikolov Yes.  
> **username_1**: Your 'Hadamard type matrix" is just the disjointness matrix. The discrepancy is at least $(2k + 1)^{-1}$ but I am not sure what the tight upper bound is.  

---

## 0 answers

