Questions tagged [algebra]
The algebra tag has no usage guidance.
13 questions
81
votes
14
answers
24k
views
Uses of algebraic structures in theoretical computer science
I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (...
- 913
28
votes
6
answers
3k
views
Alternative proofs of Schwartz–Zippel lemma
I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz.
Are there any other ...
- 3,674
23
votes
4
answers
9k
views
Abstract algebra for Theoretical Computer Scientists
I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ). I think this was partly as I needed to see ...
- 353
18
votes
2
answers
2k
views
Is there a theory that combines category theory/abstract algebra and computational complexity?
Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't ...
- 1,073
17
votes
3
answers
681
views
Formal representation of rings in computations
While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not ...
- 7,668
16
votes
3
answers
745
views
Hardness Guarantees for AES
Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.
I wonder whether such kind of provable security exists for ...
- 16.6k
7
votes
1
answer
658
views
On the relation for the Myhill-Nerode theorem/syntactic monoid of a language
In order to characterize regular languages one finds the following definition useful:
Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and ...
- 1,406
5
votes
2
answers
228
views
Reference request: An algebraic characterisation of LTL[XF]-definable word languages
I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1).
A similar ...
- 1,422
5
votes
1
answer
239
views
Is algebraic dependency decidable?
A set of numbers $S=\{x_1,...,x_n\}$ is said to be algebraically dependent if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a ...
- 5,636
4
votes
1
answer
447
views
The polynomial languages and ordered syntactic monoids
A polynomial language is a languge which could be represented as the finite union of languages of the form:
$$
A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X
$$
Such an ...
- 2,057
4
votes
1
answer
145
views
Solving a system of sums-of-powers polynomials
What is the complexity of calculating the values of the integers $x_i$, where $0 \leq x_1 < x_2 < \dots < x_k < n$, given only the values $s_m = \sum_{i=1}^k x_i^m$? for $1 \leq m \leq k$?
...
- 11.2k
3
votes
3
answers
177
views
Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$
Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The ...
- 2,057
2
votes
0
answers
139
views
Extending the notion of independence
Background
I was looking for a formulation of 'free sets' and 'independent sets' from linear algebra that would extend to groups. This question was considered here but I couldn't find a satisfactory ...
- 1,312