You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
We give new polynomial-time algorithms for testing isomorphism of a class of groups given by multiplication tables (GpI). Two results (Cannon & Holt, J. Symb. Comput. 2003; Babai, Codenotti & Qiao, ICALP 2012) imply that GpI reduces to the following: given groups G, H with characteristic subgroups of the same type and isomorphic to $\mathbb{Z}_p^d$, and given the coset of isomorphisms $Iso(G/\mathbb{Z}_p^d, H/\mathbb{Z}_p^d)$, compute Iso(G, H) in time poly(|G|). Babai & Qiao (STACS 2012) sol...
We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality to this graphical setting. Given a simple undirected graph G, an allocation is envy-free on G if no agent envies any of her neighbor's share, and is proportional on G if every agent values her own share no less than the average among her neighbors, with respect to...
We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks to decide, given two tuples of (skew-)symmetric matrices $(B_1, \dots, B_m)$ and $(C_1, \dots, C_m)$, whether there exists an invertible matrix $A$ such that for every $i\in\{1, \dots, m\}$, $A^tB_iA=C_i$. We show that this problem can be solved in randomized polynomial time over finite fields of odd size, the real field, and the complex field. The second problem asks to decide, g...
A matrix space of size $m\times n$ is a linear subspace of the linear space of $m\times n$ matrices over a field $\mathbb{F}$. The rank of a matrix space is defined as the maximal rank over matrices in this space. A matrix space $\mathcal{A}$ is called rank-critical, if any matrix space which properly contains it has rank strictly greater than that of $\mathcal{A}$. In this note, we first exhibit a necessary and sufficient condition for a matrix space $\mathcal{A}$ to be rank-critical, when $...
We extend our techniques developed in our earlier paper appeared in Computational Complexity, 2017 (preprint: arXiv:1508.00690) to obtain a deterministic polynomial time algorithm for computing the non-commutative rank together with certificates of linear spaces of matrices over sufficiently large base fields. The key new idea is a reduction procedure that keeps the blow-up parameter small, and there are two methods to implement this idea: the first one is a greedy argument that removes certa...
A classical difficult isomorphism testing problem is to test isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. It is known that this problem can be reduced to solving the alternating matrix space isometry problem over a finite field in time polynomial in the underlying vector space size. We propose a venue of attack for the latter problem by viewing it as a linear algebraic analogue of the graph isomorphism problem. This viewpoint leads us to explore the...
In 1967, Edmonds introduced the problem of computing the rank over the rational function field of an $n\times n$ matrix $T$ with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds' problem: compute the rank of $T$ over the free skew field. It is known that this problem relates to the ring of matrix semi-invariants. In particular, if the nullcone of matrix semi-invariants is defined by elements of degree $\leq \sigma$, then there follows ...
We study the problem of transforming a tripartite pure state to a bipartite one using stochastic local operations and classical communication (SLOCC). It is known that the tripartite-to-bipartite SLOCC convertibility is characterized by the maximal Schmidt rank of the given tripartite state, i.e. the largest Schmidt rank over those bipartite states lying in the support of the reduced density operator. In this paper, we further study this problem and exhibit novel results in both multi-copy an...
No project research data found
No project statistics found
Scientific Results
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.
PUBLICATIONS BY ACCESS MODE
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.
Publications in Repositories
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.