On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions

Ivanyos, G; Qiao, Y

On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions

Ivanyos, G Qiao, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2023, 2023-January, pp. 4115-4126
Issue Date:: 2023-01-01

Closed Access

	Filename	Description	Size
	SODA23-229.pdf	Accepted version	397.85 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Ivanyos, G
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449
dc.date.accessioned	2024-02-06T10:33:00Z
dc.date.available	2024-02-06T10:33:00Z
dc.date.issued	2023-01-01
dc.identifier.citation	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2023, 2023-January, pp. 4115-4126
dc.identifier.isbn	9781611977554
dc.identifier.uri	http://hdl.handle.net/10453/175385
dc.description.abstract	Let G be a linear algebraic group acting on the vector space V. Given v, v′ ∈ V, the orbit closure intersection problem asks to decide if the orbit closures of v and v′ under G intersect. Due to connections with polynomial identity testing, the orbit closure intersection problems for the conjugation and left-right actions on matrix tuples received considerable attention in computational complexity and computational invariant theory, as seen in the works of Forbes-Shpilka (RANDOM 2013), Allen-Zhu-Garg-Li-Oliveira-Wigderson (STOC 2018), and Derksen-Makam (Algebra & Number Theory 2020). In this paper, we present new algorithms for the orbit closure problem for the conjugation and left-right actions on matrix tuples. The main novel feature is that in the case of intersecting orbit closures, our algorithm outputs cosets of one-parameter subgroups that drive the matrix tuples to a tuple in the intersection of the orbit closures.
dc.language	en
dc.relation.ispartof	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions
dc.type	Conference Proceeding
utslib.citation.volume	2023-January
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2024-02-06T10:32:59Z
pubs.publication-status	Published
pubs.volume	2023-January

Abstract:

Let G be a linear algebraic group acting on the vector space V. Given v, v′ ∈ V, the orbit closure intersection problem asks to decide if the orbit closures of v and v′ under G intersect. Due to connections with polynomial identity testing, the orbit closure intersection problems for the conjugation and left-right actions on matrix tuples received considerable attention in computational complexity and computational invariant theory, as seen in the works of Forbes-Shpilka (RANDOM 2013), Allen-Zhu-Garg-Li-Oliveira-Wigderson (STOC 2018), and Derksen-Makam (Algebra & Number Theory 2020). In this paper, we present new algorithms for the orbit closure problem for the conjugation and left-right actions on matrix tuples. The main novel feature is that in the case of intersecting orbit closures, our algorithm outputs cosets of one-parameter subgroups that drive the matrix tuples to a tuple in the intersection of the orbit closures.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/175385