Algebraic proof of the equivalence of two variants of the cut-norm for multidimensional symmetric matrices
Abstract
The paper proves the equivalence of two special matrix norms. Both norms arise in models formulated in terms of interactions between binary variables. One norm is associated with the interaction of these variables within a single group, while the other is related to the interaction of variables from different groups. The statement allows for an easy transfer of meaningful results from the second (simpler) case to the first.
About the Authors
P. N. Shvedkov
Belarusian State University
Belarus
Belarus
Minsk
K. V. Lykov
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
Minsk
References
1. McGeoch C. C. Adiabatic Quantum Computation and Quantum Annealing. Springer Nature Switzerland AG, 2014.
2. What is Quantum Annealing? [Electronic resourse]. – Mode of access: https://docs.dwavesys.com/docs/latest/c_gs_2.html.
3. Lucas A. Ising formulations of many NP problems. Front. in Phys., 2014, vol. 2, art. 5. doi.org/10.3389/fphy.2014.00005
4. Talagrand M. Mean field models for spin glasses. Berlin, Heidelberg, Springer, 2011.
5. Talagrand M. Spin Glasses: A Challenge for Mathematicians. Cavity and Mean Field Models. Berlin, Heidelberg, Springer, 2003.
6. Hebb D. O. The Organization of Behavior. New York, Wiley & Sons, 1949.
7. Hopfield J. J. Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. USA, 1982, vol. 79, iss. 8, pp. 2554–2558. DOI: 10.1073/pnas.79.8.2554
8. Salakhutdinov R., Hinton G. Deep Boltzmann Machine. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, PMLR, 2009, vol. 5, pp. 448–455.
9. Astashkin S., Lykov K. On the unconditionality of Rademacher’s fractional chaos in symmetric spaces. Izvestiya: Mathematics, 2024, vol. 88, no. 1, pp. 3–20 (in Russian). doi.org/10.4213/im9406
10. Frieze A., Kannan R. Quick Approximation to Matrices and Applications. Combinatorica, vol. 19, pp. 175–220. DOI: https://doi.org/10.1007/s004930050052
11. Håstad J. Some Optimal Inapproximability Results // J. Assoc. Comput. Machinery. 2001. P. 798–859. DOI: 10.1145/502090.502098
12. Alon N., Naor. A Approximating the cut-norm via grothendieck’s inequality // STOC’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. June 13–16, 2004. New York, USA, 2004. P. 72–80. doi.org/10.1145/1007352.1007371
13. Astashkin S., Lykov K. Random unconditional convergence of Rademacher chaos in L∞ and sharp estimates for discrepancy of weighted graphs and hypergraphs, Ver. 1 released 28.12.2024 [Electronic resourse]. – Mode of access: https://arxiv.org/abs/2412.20107.
14. De la Peña V. H. and Giné E. Decoupling: from dependence to independence. New York, Berlin, Heidelberg: Springer-Verlag, 1999.
Review
For citations:
Shvedkov P.N., Lykov K.V. Algebraic proof of the equivalence of two variants of the cut-norm for multidimensional symmetric matrices. Proceedings of the Institute of Mathematics of the NAS of Belarus. 2025;33(1):34-43. (In Russ.)
Views:
11
Email this article 