Skip to main content

Questions tagged [group-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
44 views

How to motivate freshman students towards automatic groups?

I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automatic groups. I'm very experienced as a ...
Felipe's user avatar
  • 111
0 votes
0 answers
22 views

How to motivate freshman students towards automata groups? [duplicate]

I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automata groups. I'm very experienced as a ...
Felipe's user avatar
  • 111
1 vote
0 answers
35 views

Is the HSP with the symmetric group exactly equivalent to the Graph Isomorphism problem?

It is well known that an algorithm to solve the Hidden Subgroup Problem (HSP) with the symmetric group can solve the Graph isomorphism problem. But is this true in reverse? Will an algorithm for graph ...
Andrew Baker's user avatar
0 votes
2 answers
33 views

Doubt regarding conjugations of permutations

I was studying the Barrington Theorem in https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture2.pdf when I found a doubt regarding permutations. Particularly, with conjugations. It is ...
441Juggler's user avatar
3 votes
2 answers
308 views

Paint a Cube by rolling it (Puzzle Algorithm)

I stumbled across this game in Simon Tatham's puzzle app. It's called cube. The description according to the game is: You have a grid of 16 squares, six of which are blue; on one square rests a cube. ...
Zingerella's user avatar
0 votes
1 answer
48 views

Logic Programming - A definite program for the theory of groups

I am studying theoretical computer science using Ayala's book "Fundamentos da Programação Lógica e Funcional" (the book is written in Portuguese), but the part I am studying right now is ...
Gabriel F. Silva's user avatar
1 vote
1 answer
40 views

Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)

Let $G$ be an abelian group. We say that $G$ has property $V_n$ if for every $m > n$ and a list $L\subset G$ of $m$ elements s.t. $\sum_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\...
levav ferber tas's user avatar
0 votes
1 answer
45 views

Efficient algorithm/data structure that maps tic-tac-toe boards to floats

I'm implementing a q-learning agent for tic-tac-toe that requires mapping from tic-tac-toe boards to float values. Since certain game states are equivalent and should have the same value, it would be ...
Mahdi Khodabandeh's user avatar
1 vote
0 answers
33 views

matching vector families that form a group

Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)? You can find the definition of MV families here: https://homes....
Ali Gholami's user avatar
1 vote
1 answer
29 views

Number of binary words that form a group of Hamming weight at most d

Consider binary words in {0,1}^n whose Hamming weight is at most some constant d. We want to select some of these words such that they form a group under addition. How many words can we choose at most?...
Ali Gholami's user avatar
1 vote
1 answer
30 views

Is $\{\emptyset,a,\epsilon\}$ an algebraic structure with respect to $+$?

Let $R = \{\emptyset,a,\epsilon\}$ (the elements here are regular expressions) and let $+$ be the or operation, which can be applied over the regular expressions of $R$. Is $(R,+)$ some kind of an ...
Ayush Kumar's user avatar
3 votes
1 answer
94 views

Iteratively enumerating all permutations of $N$ objects using a generating set

The group theory of $S_n$ shows that all permutations of $n$ objects can be generated from the $n$-cycle $a:=(1 2 3 .. n)$ and the transposition $b:=(1 2)$. (See Theorem 2.5 at https://kconrad.math....
Jared Stewart's user avatar
4 votes
0 answers
53 views

Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
Jáchym Barvínek's user avatar
3 votes
1 answer
524 views

Minimum number of groups such that every element in graph is included?

Problem Description Note: I originally posted this question on Stack Overflow but was referred to this community instead. I have a graph containing selectors and elements. An element can have multiple ...
Akilan Manivannan's user avatar
1 vote
0 answers
36 views

How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?

Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$. Goal: An algorithm to generate a member from each ...
mathematrucker's user avatar
2 votes
0 answers
27 views

Special Properties for Oracles in HSP

Let $(G,+)$ be an abelian group, $X$ a finite set (of "colors"), and $f:G \to X$ a function such that there exists a subgroup $H<G$ for which $f$ separates cosets of $H$, i.e. $\forall a,...
Don Fanucci's user avatar
1 vote
1 answer
42 views

Strengthening a given attack on discrete log

I am trying to prove the following claim: Let $(G,*)$ be a cyclic group of size $m$ with generator $g$. Assume there exists some adversary $A'$ of size $T'=\frac{\left(T-O\left(\log m\right)\right)}{...
Ido's user avatar
  • 163
2 votes
0 answers
55 views

Permutation with stable partitions

I am searching a fast pseudo-random permutation function with the following requirements. Given a predefined set of values $V$ and an integer $k$. Split $V$ to $k$ subset, and iterate over any subset ...
Dávid Horváth's user avatar
1 vote
1 answer
61 views

Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points

I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a ...
Conor Henry's user avatar
-1 votes
1 answer
2k views

Could someone break down this grouping problem for me?

I am trying to work through this programming problem but I can't progress because I genuinely don't understand what it is that its asking me. New Students are arriving at college. Initially the ...
Levent Ozbek's user avatar
23 votes
10 answers
11k views

Is Group Theory useful in Computer Science in areas other than cryptography?

I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
Dudi Frid's user avatar
  • 201
3 votes
1 answer
25 views

Algorithm to find the size of a quotient of a free group

Are there any algorithms to find the size of an algebraic quotient of a free group? It would take the generators as input and output the size. For example, an input could be something like {a,b: a^8=...
Alex Li's user avatar
  • 143
11 votes
2 answers
734 views

Subset sum problem for permutations

Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, ...
Nastya Koroleva's user avatar
4 votes
1 answer
56 views

Detecting rotational symmetries of spatial structures

I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of ...
Botond's user avatar
  • 143
4 votes
2 answers
336 views

Algorithm for factoring elements of permutation groups?

You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). ...
Display Name's user avatar
1 vote
1 answer
116 views

Is it possible to interpret some Martin-Löf types as abelian monoids in such a way that any abelian monoid can be represented as a type?

For instance, I can interpret the unit type as the trivial monoid with one element. Non-dependent pairs $A \times B$ can be interpreted as the direct sum $A ⊕ B$ when $A$ and $B$ can both be ...
Andrew Cann's user avatar
3 votes
2 answers
261 views

Transforming a byte with a subset of a small, fixed set of values and xor into any other value

If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, ...
Dannie's user avatar
  • 193
4 votes
1 answer
774 views

How to calculate the minimum number of groups, by grouping groups with capacity together?

I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem. If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
Ricardo Jesus's user avatar
3 votes
1 answer
150 views

How to compute quotient subgroup efficiently?

Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group. Model of computation is RAM For all pair of $a$...
sssa's user avatar
  • 424
1 vote
1 answer
142 views

Is finite abelian group isomorphism in Log Space?

Definition : An abelian group is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written Input : Two finite abelian ...
Complexity's user avatar
  • 1,187
3 votes
1 answer
141 views

Representing Integral domains in computer memory?

Earlier I wrote this question about an algorithm computed on an integral domain. However as commented I didn't suggest any particular ways of storing an integral domain in computer memory. I set out ...
Sriotchilism O'Zaic's user avatar
1 vote
0 answers
76 views

Is there an algorithm for determining whether a element is Prime?

Is there an algorithm that can take an element on an arbitrary integral domain, and determine whether or not it is prime on that ring? It is pretty trivial to do so on a finite integral domain, ...
Sriotchilism O'Zaic's user avatar
4 votes
0 answers
214 views

Generating all directed multigraphs

I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow ...
mikebolt's user avatar
  • 176
6 votes
1 answer
549 views

Applications of Graph Automorphisms

I've seen the topic of the automorphism group appear in several introductory graph theory books I've looked at. It always feel oddly disjointed and poorly motivated to me. Is there any practical (or ...
eepperly16's user avatar
3 votes
1 answer
708 views

How to find the symmetry group of a polynomial

Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. ...
davik's user avatar
  • 133
0 votes
1 answer
67 views

Sifting algorithm for group generated by a set

On page 38 of "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2). I have some confusions. Why it is written that an entry $M_{i,j}, j < i$, cannot ...
Michael's user avatar
  • 291
3 votes
1 answer
131 views

What is the name of the word problem for free groups under straight line program encoding?

I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free ...
Thomas Klimpel's user avatar
1 vote
1 answer
26 views

Can you form a group with assembly instructions under the MIPS-32 architecture?

Would it be possible to form such a group using the ADD instruction and the NOT instruction?
CinchBlue's user avatar
  • 594
5 votes
1 answer
200 views

What can be said in general about a homomorphism between two regular languages?

In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can ...
wvxvw's user avatar
  • 1,388
3 votes
1 answer
2k views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream $...
scip's user avatar
  • 131
0 votes
1 answer
112 views

algoritm to convert a monoid into an automaton [closed]

In literature, is there an algoritm to convert a monoid into an atomaton? I am looking for references/applications.
Michela's user avatar
  • 31
13 votes
2 answers
1k views

Group isomorphism to graph ismorphism

In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For ...
Jernej's user avatar
  • 2,460
2 votes
1 answer
285 views

n-Cube as a Cayley Graph

I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how ...
Patrick Collins's user avatar
16 votes
4 answers
1k views

Bridge theorems for group theory and formal languages

Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines? I am looking for references/applications. However note ...
vzn's user avatar
  • 11k
39 votes
6 answers
7k views

What use are groups, monoids, and rings in database computations?

Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird. All I could find is: Implementations of ...
john mangual's user avatar
  • 1,951
4 votes
1 answer
956 views

Visualized definition of cohomology

I cannot imagine how cohomology is related to graph theory, actually I read solid definition from wiki, and to be honest, I cannot understand it. e.g I know what is homotopy (in simple term), group ...
user avatar