Questions tagged [algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
76
votes
13answers
21k 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 (...
41
votes
12answers
2k views

Gröbner bases in TCS?

Does anyone know of interesting applications of Gröbner bases to theoretical computer science? Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was ...
33
votes
12answers
6k views

Algebra oriented branch of theoretical computer science

I have a very strong base in algebra, namely commutative algebra, homological algebra, field theory, category theory, and I am currently learning algebraic geometry. I am a math major with an ...
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 ...
27
votes
2answers
4k views

What is the logarithm or root operation in type-space?

I was recently reading The Two Dualities of Computation: Negative and Fractional Types. The paper expands on sum-types and product-types, giving semantics to the types ...
21
votes
4answers
8k 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 ...
20
votes
4answers
3k views

Data Structure isomorphisms

Disclaimer: I am not a CS theorist. Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data ...
18
votes
1answer
3k views

The quad-edge data structure (Delaunay/Voronoi)

2 questions for the computational geometers or algebraists: I am just beginning to dive into computational geometry and I am loving it =) I am attempting to read the famous article by Guibas and ...
18
votes
2answers
1k 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 ...
18
votes
3answers
828 views

Computing sum of sparse polynomials squared in O(n log n) time?

Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient ...
17
votes
3answers
636 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 ...
16
votes
0answers
367 views

Looking for an operator on polynomials

I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc). I wonder ...
14
votes
3answers
2k views

On the realisation of monoids as syntactic monoids of languages

Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as $$ u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L $$ and the quotient ...
14
votes
3answers
647 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 ...
14
votes
2answers
727 views

Are There Highly Symmetric NP- or P-complete Languages?

Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ...
14
votes
2answers
414 views

What's the bias of random polynomials with low degree over GF(2)?

I have a question concerning low-degree polynomials and probability: What is the (assyptotic behavior of the) probability that a random* polynomial, $p$, over GF(2), with degree $\le d$ and n ...
13
votes
4answers
1k views

(N)DFA with same initial/accepting state(s)

What is known about the class of languages recognized by finite automata having the same initial and accepting state? This is a proper subset of the regular languages (since every such language ...
12
votes
2answers
1k views

List of number theoretic or algebraic problems in various complexity classes

I am looking for a list about the known or unknown complexity of various number theoretic /algebraic problems. For example, GCD in $NC^1$ is open, factoring in $P$ is open, computing sheaf ...
11
votes
1answer
996 views

Complexity of convolution in the max/plus ring

We can do convolution in $O(n\log n)$ for plus/multiply polynomials with FFT. However, the approach doesn't seem very generalisable to rings in general. Has there been any progress over the naive $O(...
11
votes
0answers
127 views

Are there cascade decompositions of machines that are more general than finite automata?

The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
10
votes
2answers
578 views

Complexity of computing the order of a permutation group

Given two permutations $g$ and $h$ over $n$ elements (i.e., members of $S_n$), what is the complexity of computing the order of the subgroup generated by $g,h$? Or just of deciding whether the ...
9
votes
2answers
808 views

Formal representation of an abstraction hierarchy

Introduction I'm writing my PhD thesis on Abstract Delta Modeling (ADM), an abstract algebraic description of modifications (known as deltas) able to act on products (as in 'software products'). This ...
9
votes
2answers
652 views

Applications of algebraic geometry in type theory/programming language theory

Lately, I have become interested in algebraic geometry and have started reading on it. I still know very little about this field, but I do want to know if it has any connection with my main field, ...
9
votes
1answer
423 views

Chomsky Schützenberger enumeration theorem

In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some ...
9
votes
1answer
327 views

Turing Machines as Coalgebras

I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations ...
9
votes
2answers
335 views

Are there any 'graphical' algebras that can describe the 'shape' of graphs?

One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a ...
9
votes
1answer
171 views

Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
9
votes
3answers
596 views

Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a ...
9
votes
0answers
292 views

What does a private coin $\mathsf{IP}$ protocol for Hilbert's Nullstellensatz look like?

$\mathsf{GNI}$ Private Coin In [GMW85], the authors provided the famous interactive proof $\mathsf{IP}$ of Graph Non Isomorphism $\mathsf{GNI}$. The $\mathsf{GNI}$ protocol entails a verifier ...
8
votes
2answers
315 views

Sufficient conditions to guarantee unique fixpoint (not unique least/greatest fixpoint) for monotone functions on complete lattice

Tarski's fixpoint theorem states, that the fixpoints of a monotone operator on a complete lattice is a complete lattice. By consequence, we have a unique greatest fixpoint and unique least fixpoint ...
8
votes
2answers
1k views

What kind of theoretical object corresponds to a C++ concept?

I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ concepts corresponds to. Basically, C++ concepts allow to define ...
8
votes
1answer
289 views

Factoring low-degree polynomials

What is the fastest algorithm known for factoring polynomials with $n$ variables and total degree $\leq d$? Here, $n$ is growing and $d$ is fixed. Most work seem to consider the case when $d$ is ...
8
votes
1answer
235 views

Algebraic (or numeric) invariants of complexity classes

I hope this question isn't too naive for this site. In mathematics (topology, geometry, algebra) it is common for one to distinguish between two objects by coming up with an algebraic or numerical ...
8
votes
2answers
344 views

Bivariate low-degree polynomial testing of Polishchuk-Spielman

In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate ...
8
votes
1answer
204 views

Complete axiomatization of relation algebras without ${}^-$ and $\top$

I'm working on a more thorough algebraic treatment of delta modeling. Briefly, deltas are syntactic entities that can modify products (as in 'software products'). They actually represent relations on ...
7
votes
3answers
440 views

Field extensions in CS

A field is a set with two binary operations called addition and multiplication satisfying various axioms. Wikipedia article: Field_(mathematics) A field extension is when you add a new element and ...
7
votes
2answers
306 views

Smallest representatives of a quotient by an equivalence relation

Background Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for a regular language $L$ such that $|Q|=n$, and let $\equiv_L$ be the relation given by $$x\equiv_Ly\text{ iff for all $u$: }xu\...
7
votes
1answer
560 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 ...
7
votes
1answer
276 views

Kleene Algebra for star-free regular expressions

TLDR: Is there a notion of Kleene Algebra for star-free regular expressions? Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent ...
7
votes
1answer
340 views

Technical lemma about curves used in original proof of PCP theorem

I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn'...
7
votes
0answers
56 views

Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem: Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
6
votes
2answers
630 views

Proof of a unique homomorphism from an initial object

What is the proof that there is only one homomorphism from an initial object to another object?
6
votes
1answer
379 views

What is an unambiguous language in the sense of Schützenberger?

I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic. In Theorem 6 (by Kamp), the fragment $\mathrm{TL}[\mathsf{F},\...
6
votes
1answer
157 views

Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?

If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether ...
6
votes
5answers
284 views

What is/are the lower bounds for finding a something akin to complex residue?

Given a function $\sum_{i=-N}^N{c_i x^i}$: $f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$. The constant $c_0$ is desired, and we start with only $f(x)...
6
votes
2answers
540 views

What category are Tagless Final Algebras final In?

The Haskell and Scala community have been very enamored recently with what they call tagless final 'pattern' of programming. These are referenced as dual to initial free algebras, so I was wondering ...
6
votes
1answer
345 views

Algebra and algebraic data types

Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)? Presumably a free monoid can be considered to be isomorphic to the ...
5
votes
1answer
178 views

Why is it difficult to develop a subexponential functoral approach to discrete log

Call a discrete logarithm algorithm functoral if the commutative algebraic object that the algorithm acts on can be changed with another commutative object in the same category and the algorithm does ...
5
votes
1answer
234 views

Terminology about computation and Finite algebra

I am looking for the name of something that may have one. A finite algebra $\mathcal{A} = (E, \{f_1, f_2, \ldots, f_k\})$ is a non-empty set $E$ together with some functions $f_i$ from $E^{r_i} \to E$...
5
votes
1answer
120 views

Commutative operation benefits

With an associative operation I can rewrite a computation tree + / \ + 4 / \ + 3 / \ + 2 / \ 0 1 to be more efficient ...