Algorithms and complexity for testing isomorphism of algebraic structures

Funding: 2015: $125,000
2016: $125,000
2017: $125,000

Project Member(s): Qiao, Y., Zhang, C.

Funding or Partner Organisation: Australian Research Council (ARC DECRA Scheme)

Start year: 2015

Summary: The algorithmic problem of isomorphism test asks to decide whether two objects from a mathematical category are essentially the same. This project focuses on the setting when the categories are from algebra, including but not limited to groups and polynomials. It is a family of fundamental problems in complexity theory, with important applications in cryptography. The project aims to develop efficient algorithms with provable guarantee, or formal hardness proofs for these problems. Algorithms will be implemented to examine the impacts on certain cryptography schemes. The successful completion of this project will enhance the understanding of computational complexities of these problems, and identify the security of certain crypto schemes.

Publications:

Qiao, Y, Sun, X & Yu, N 2020, 'Local Equivalence of Multipartite Entanglement', IEEE Journal on Selected Areas in Communications, vol. 38, no. 3, pp. 568-574.
View/Download from: Publisher's site

Halasi, Z, Maróti, A, Pyber, L & Qiao, Y 2019, 'An improved diameter bound for finite simple groups of Lie type', Bulletin of the London Mathematical Society, vol. 51, no. 4, pp. 645-657.
View/Download from: Publisher's site

Ivanyos, G & Qiao, Y 2019, 'Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing', SIAM Journal on Computing, vol. 48, no. 3, pp. 926-963.
View/Download from: Publisher's site

Ji, Z, Qiao, Y, Song, F & Yun, A 1970, 'General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), International Conference on Theory of Cryptography, Springer International Publishing, Nuremberg, pp. 251-281.
View/Download from: Publisher's site

Ivanyos, G, Kulkarni, R, Qiao, Y, Santha, M & Sundaram, A 2018, 'On the complexity of trial and error for constraint satisfaction problems', Journal of Computer and System Sciences, vol. 92, pp. 48-64.
View/Download from: Publisher's site

Ivanyos, G, Qiao, Y & Subrahmanyam, KV 2018, 'Constructive non-commutative rank computation is in deterministic polynomial time', computational complexity, vol. 27, no. 4, pp. 561-593.
View/Download from: Publisher's site

Ivanyos, G & Qiao, Y 1970, 'Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing', Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Symposium on Discrete Algorithm, Society for Industrial and Applied Mathematics, New Orleans, LA, USA, pp. 2357-2376.
View/Download from: Publisher's site

Grochow, JA & Qiao, Y 2017, 'Algorithms for Group Isomorphism via Group Extensions and Cohomology', SIAM Journal on Computing, vol. 46, no. 4, pp. 1153-1216.
View/Download from: Publisher's site

Ivanyos, G, Qiao, Y & Subrahmanyam, KV 2017, 'Non-commutative Edmonds’ problem and matrix semi-invariants', computational complexity, vol. 26, no. 3, pp. 717-763.
View/Download from: Publisher's site

Li, Y & Qiao, Y 2017, 'On rank-critical matrix spaces', Differential Geometry and its Applications, vol. 55, pp. 68-77.
View/Download from: Publisher's site

Mukhopadhyay, P & Qiao, Y 2017, 'Sparse multivariate polynomial interpolation on the basis of Schubert polynomials', computational complexity, vol. 26, no. 4, pp. 881-909.
View/Download from: Publisher's site

Bei, X, Qiao, Y & Zhang, S 1970, 'Networked Fairness in Cake Cutting', Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, Twenty-Sixth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, pp. 3632-3638.
View/Download from: Publisher's site

Belovs, A, Ivanyos, G, Qiao, Y, Santha, M & Yang, S 1970, 'On the polynomial parity argument complexity of the combinatorial nullstellensatz', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site

Ivanyos, G, Qiao, Y & Venkata Subrahmanyam, K 1970, 'Constructive non-commutative rank computation is in deterministic polynomial time', Leibniz International Proceedings in Informatics, LIPIcs, Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl, Berkeley, CA, USA, pp. 1-18.
View/Download from: Publisher's site

Li, Y & Qiao, Y 1970, 'Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model', 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Berkeley, CA, USA, pp. 463-474.
View/Download from: Publisher's site

Li, Y, Qiao, Y, Wang, X & Duan, R 2016, 'Tripartite-to-bipartite Entanglement Transformation by Stochastic Local Operations and Classical Communication and the Structure of Matrix Spaces', Communications in Mathematical Physics, vol. 358, no. 2, pp. 791-814.
View/Download from: Publisher's site

Grochow, JA, Mulmuley, KD & Qiao, Y 1970, 'Boundaries of VP and VNP', Leibniz International Proceedings in Informatics, LIPIcs, International Colloquium on Automata Languages and Programming, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Rome, Italy.
View/Download from: Publisher's site

Ivanyos, G, Karpinski, M, Qiao, Y & Santha, M 2015, 'Generalized Wong sequences and their applications to Edmonds' problems', Journal of Computer and System Sciences, vol. 81, no. 7, pp. 1373-1386.
View/Download from: Publisher's site

Wang, H, Zhang, P, Tsang, I, Chen, L & Zhang, C 1970, 'Defragging Subgraph Features for Graph Classification', Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM'15: 24th ACM International Conference on Information and Knowledge Management, ACM, Melbourne, VIC, Australia, pp. 1687-1690.
View/Download from: Publisher's site

Keywords: isomorphism test; algorithm design; group theory

FOR Codes: Application Tools and System Utilities, Computer System Security, Analysis of Algorithms and Complexity, Expanding Knowledge in the Information and Computing Sciences, Applied Discrete Mathematics, Applied mathematics not elsewhere classified, System and network security, Computational complexity and computability, Information systems, technologies and services not elsewhere classified

Acknowledgement of Country

UTS acknowledges the Gadigal people of the Eora Nation, the Boorooberongal people of the Dharug Nation, the Bidiagal people and the Gamaygal people, upon whose ancestral lands our university stands. We would also like to pay respect to the Elders both past and present, acknowledging them as the traditional custodians of knowledge for these lands.