Алгебраическое доказательство эквивалентности двух вариантов cut-нормы для многомерных симметричных матриц

В работе доказана эквивалентность двух специальных матричных норм. Обе нормы возникают в моделях, формулируемых в терминах взаимодействия бинарных переменных. При этом одна норма связана со взаимодействием этих переменных внутри одной группы, а другая – со взаимодействием переменных из разных групп. Утверждение позволяет легко переносить содержательные результаты со второго (более простого) случая на первый.

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: 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. P. 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. P. 448–455.

9. Асташкин С. В., Лыков К. В. О безусловности дробного хаоса Радемахера в симметричных пространствах // Изв. РАН. Сер. матем. 2024. Т. 88, № 1. C. 3–20. doi.org/10.4213/im9406

10. Frieze A., Kannan R. Quick Approximation to Matrices and Applications // Combinatorica. 1999. Vol. 19. P. 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.