English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider two basic algorithmic problems concerning tuples of(skew-)symmetric matrices. The first problem asks to decide, given two tuplesof (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 inrandomized polynomial time over finite fields of odd size, the real field, andthe complex field. The second problem asks to decide, given a tuple of squarematrices $(B_1, \dots, B_m)$, whether there exist invertible matrices $A$ and$D$, such that for every $i\in\{1, \dots, m\}$, $AB_iD$ is (skew-)symmetric. Weshow that this problem can be solved in deterministic polynomial time overfields of characteristic not $2$. For both problems we exploit the structure ofthe underlying $*$-algebras, and utilize results and methods from the moduleisomorphism problem.  Applications of our results range from multivariate cryptography, groupisomorphism, to polynomial identity testing. Specifically, these results implyefficient algorithms for the following problems. (1) Test isomorphism ofquadratic forms with one secret over a finite field of odd size. This problembelongs to a family of problems that serves as the security basis of certainauthentication schemes proposed by Patarin (Eurocrypto 1996). (2) Testisomorphism of $p$-groups of class 2 and exponent $p$ ($p$ odd) with order$p^k$ in time polynomial in the group order, when the commutator subgroup is oforder $p^{O(\sqrt{k})}$. (3) Deterministically reveal two families ofsingularity witnesses caused by the skew-symmetric structure, which representsa natural next step for the polynomial identity testing problem following thedirection set up by the recent resolution of the non-commutative rank problem(Garg et al., FOCS 2016; Ivanyos et al., ITCS 2017).

Algorithms based on *-algebras, and their applications to isomorphism of  polynomials with one secret, group isomorphism, and polynomial identity  testing