About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Pudlák, Pavel ; Vavřín, Zdeněk
Computation of rigidity of order $\frac{n^2}r$ for one simple matrix. (English). Commentationes Mathematicae Universitatis Carolinae, vol. 32 (1991), issue 2, pp. 213-218
MSC: 15A03, 68Q15 | MR 1137781 | Zbl 0753.15011
Keywords:
rigidity of matrices; lower bounds to complexity
Summary:
We shall compute the exact value of rigidity of the triangular matrix with entries 0 and 1.
References:
[1] Alon N.: On the rigidity of Hadamard matrices. manuscript.
[2] Razborov A.A.: On rigid matrices (in Russian). preprint.
[3] Valiant L.G.: Graph-theoretic arguments in low-level complexity. Proc. Math. Found. Comp. Sci., Springer (1977) 162-176. MR 0660702 | Zbl 0384.68046
Partner of
EuDML logo