We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
67
votes
13answers
19k 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 (...
28
votes
6answers
2k 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 ...
18
votes
2answers
846 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 ...
17
votes
3answers
599 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
votes
1answer
479 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 ...
14
votes
3answers
565 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 ...
4
votes
1answer
137 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$? ...
4
votes
1answer
233 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 ...
5
votes
1answer
185 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 ...
2
votes
0answers
136 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 ...