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): Zhang, C., Qiao, Y.

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., Qiao, Y. & Subrahmanyam, K.V. 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

Mukhopadhyay, P. & Qiao, Y. 2017, 'Sparse multivariate polynomial interpolation on the basis of Schubert polynomials', Computational Complexity, pp. 1-29.
View/Download from: 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 (ICALP), 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, The 24th ACM International on Conference on Information and Knowledge Management (CIKM'15), 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