Skip to main content

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:

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

Li, Y, Qiao, Y, Wang, X & Duan, R 2018, '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: UTS OPUS or 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: UTS OPUS or Publisher's site

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

Mukhopadhyay, P. & Qiao, Y. 2017, 'Sparse multivariate polynomial interpolation on the basis of Schubert polynomials', Computational Complexity, pp. 1-29.
View/Download from: UTS OPUS or Publisher's site

Li, Y & Qiao, Y 2017, 'Linear algebraic analogues of the graph isomorphism problem and the erds-rényi model', Annual Symposium on Foundations of Computer Science - Proceedings, IEEE Annual Symposium on Foundations of Computer Science, IEEE, Berkeley, CA, USA, pp. 463-474.
View/Download from: UTS OPUS or Publisher's site

Grochow, J.A., Mulmuley, K.D. & Qiao, Y. 2016, '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: UTS OPUS or 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. 2015, 'Defragging Subgraph Features for Graph Classification', Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, ACM International Conference on Information and Knowledge Management, ACM, Melbourne, VIC, Australia, pp. 1687-1690.
View/Download from: UTS OPUS or 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