| Title:
|
Computation of rigidity of order $\frac{n^2}r$ for one simple matrix (English) |
| Author:
|
Pudlák, Pavel |
| Author:
|
Vavřín, Zdeněk |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
32 |
| Issue:
|
2 |
| Year:
|
1991 |
| Pages:
|
213-218 |
| . |
| Category:
|
math |
| . |
| Summary:
|
We shall compute the exact value of rigidity of the triangular matrix with entries 0 and 1. (English) |
| Keyword:
|
rigidity of matrices |
| Keyword:
|
lower bounds to complexity |
| MSC:
|
15A03 |
| MSC:
|
68Q15 |
| idZBL:
|
Zbl 0753.15011 |
| idMR:
|
MR1137781 |
| . |
| Date available:
|
2008-10-09T13:11:55Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/116958 |
| . |
| Reference:
|
[1] Alon N.: On the rigidity of Hadamard matrices.manuscript. |
| Reference:
|
[2] Razborov A.A.: On rigid matrices (in Russian).preprint. |
| Reference:
|
[3] Valiant L.G.: Graph-theoretic arguments in low-level complexity.Proc. Math. Found. Comp. Sci., Springer (1977) 162-176. Zbl 0384.68046, MR 0660702 |
| . |
