Zobrazeno 1 - 10
of 650
pro vyhledávání: '"Weiß, Armin"'
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the only geodetic Cayley graphs which occur are odd cycles and compl
Externí odkaz:
http://arxiv.org/abs/2406.00261
We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for groups and quasigroups (=Latin squares), given as input in terms of their m
Externí odkaz:
http://arxiv.org/abs/2402.00133
In this paper we investigate computational properties of the Diophantine problem for spherical equations in some classes of finite groups. We classify the complexity of different variations of the problem, e.g., when $G$ is fixed and when $G$ is a pa
Externí odkaz:
http://arxiv.org/abs/2308.12841
Autor:
Stober, Florian, Weiß, Armin
In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a wide range of papers appeared investigating their peculiar properties. Yet, a comp
Externí odkaz:
http://arxiv.org/abs/2308.08970
Autor:
Mattes, Caroline, Weiß, Armin
The Baumslag group had been a candidate for a group with an extremely difficult word problem until Myasnikov, Ushakov, and Won succeeded to show that its word problem can be solved in polynomial time. Their result used the newly developed data struct
Externí odkaz:
http://arxiv.org/abs/2206.06181
Autor:
Stober, Florian, Weiß, Armin
It is a long-standing open question to determine the minimum number of comparisons $S(n)$ that suffice to sort an array of $n$ elements. Indeed, before this work $S(n)$ has been known only for $n\leq 22$ with the exception for $n=16$, $17$, and $18$.
Externí odkaz:
http://arxiv.org/abs/2206.05597
The power word problem for a group $G$ asks whether an expression $u_1^{x_1} \cdots u_n^{x_n}$, where the $u_i$ are words over a finite set of generators of $G$ and the $x_i$ binary encoded integers, is equal to the identity of $G$. It is a restricti
Externí odkaz:
http://arxiv.org/abs/2201.06543
Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. S{\'e}nizergues and the fifth author (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable
Externí odkaz:
http://arxiv.org/abs/2110.00900
Autor:
Mattes, Caroline, Weiß, Armin
Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and $(x,y) \mapsto x\cdot 2^y$. The same authors applied power circui
Externí odkaz:
http://arxiv.org/abs/2102.09921
The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell (2002) where they showed that this problem is in polynomial time for nilpotent groups while it is NP-complete for non-solva
Externí odkaz:
http://arxiv.org/abs/2010.11788