|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Rank and fooling set size | | Aya Hamed
; Troy Lee
; | | Date: |
28 Oct 2013 | | Abstract: | Say that A is a Hadamard factorization of the identity I_n of size n if the
entrywise product of A and the transpose of A is I_n. It can be easily seen
that the rank of any Hadamard factorization of the identity must be at least
sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be
achieved, and showed a boolean Hadamard factorization of the identity of rank
n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard
factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen
and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard
factorization of the identity A of size r(r-1)+1 and rank r over F_p.
Here we resolve the question for fields of zero characteristic, up to a
constant factor, giving a construction of Hadamard factorizations of the
identity of rank r and size (r+1)r/2. The matrices in our construction are
blockwise Toeplitz, and have entries whose magnitudes are binomial
coefficients. | | Source: | arXiv, 1310.7321 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER