Questions tagged [algebra]
The algebra tag has no usage guidance.
105 questions
2
votes
0
answers
89
views
Multipoint evaluation in Lagrange basis
Setup. Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e_1, \dots, e_k\}$ of order $k$. Given a list $y = y_1, \dots, y_k\in \mathbb{F}$ let $p$ be the unique polynomial of ...
3
votes
0
answers
57
views
Complexity of minimizing the index of a subgroup of the free group
Let $\Sigma$ be a finite alphabet and $G$ the free group generated by $\Sigma$. Let $W$ be a finite subset of $G$. (Represented as a list of formal expressions of the form $a_1^{\pm 1}\ldots a_n^{\pm ...
- 2,181
4
votes
1
answer
86
views
Reference request: finite field computation over the Word-RAM model
Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$.
Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
- 696
-1
votes
1
answer
151
views
What theorems are interesting in a monad?
In a monad, one can prove that the Kleisli composition is associative, and eta is its right and left unit, this is the famous monoid in the endofunctor category:
...
- 599
4
votes
1
answer
114
views
Power of non-implicationally-complete Frege systems and Boolean equational calculus
We know that Frege systems are required to be implicationally complete -- namely, if a set of formulas $B_1,B_2,\cdots,B_t$ imply formula $C$, then this implication can be proven in the system. I'm ...
- 18.6k
0
votes
0
answers
58
views
Product types: algebraic structure for modeling product types with commutative and associative product operation
Is there a known algebraic structure over set of Types (however they are defined) which is equipped with:
commutative and associative product operation for building product types from simpler types, ...
3
votes
1
answer
131
views
Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?
Given a polynomial functor $F$, its initial algebra is denoted by $\mu X.F(X)$.
Now, if $F$ is a 2-variable polynomial functor, $Y \mapsto \mu X.F(X,Y)$ turns out to be functorial and we can, again, (...
- 509
0
votes
1
answer
312
views
Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?
I am a mathematician and I am very new to theoretical computer science.
The definition of P/NP problem I found in wiki is that:
P is the set of decision problems solvable in polynomial time by a ...
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 (...
- 599
0
votes
0
answers
75
views
Polynomial GCD exact complexity in terms of degree and number of variables
https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
- 13.3k
8
votes
1
answer
459
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},\...
- 359
41
votes
12
answers
3k
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 ...
- 135
2
votes
1
answer
201
views
Complexity of finding approximate solutions for systems of polynomial equations
Consider the following problem:
Input: $(p_1,...,p_n, \epsilon)$ where each $p_i$ is a polynomial in $m$ variables with integer coefficients and $\epsilon>0$.
Output: If there is $(r_1,...,r_m) \in ...
- 141
6
votes
0
answers
240
views
Satisfiability and a Galois Theory Analog
Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows:
$$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$
where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
- 541
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
138
views
Commutative operation benefits
With an associative operation I can rewrite a computation tree
+
/ \
+ 4
/ \
+ 3
/ \
+ 2
/ \
0 1
to be more efficient ...
- 903
12
votes
1
answer
2k
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(...
- 958
8
votes
1
answer
211
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 ...
- 161
10
votes
1
answer
571
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 ...
- 41
7
votes
1
answer
417
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 ...
- 9,018
2
votes
0
answers
123
views
Relation between automorphism group of a linear code and its dual code
Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc.
In ...
- 387
7
votes
1
answer
363
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'...
- 397
8
votes
2
answers
539
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 ...
- 101
8
votes
2
answers
923
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 ...
- 1,011
20
votes
3
answers
889
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 ...
- 958
6
votes
1
answer
418
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 ...
- 454
12
votes
2
answers
1k
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, ...
- 32.9k
9
votes
1
answer
459
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 ...
- 326
5
votes
1
answer
473
views
Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?
A Turing machine is defined as a structure $ TM(L,Q,T) $, where $L,Q$ are sets of symbols and internal states of TM respectively, and T is a transition relation:
$T: L \times Q \to L \times Q $
for ...
- 4,495
1
vote
0
answers
27
views
Worst case polynomial in elimination theory under rank conditions?
Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
- 13.3k
11
votes
0
answers
200
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 ...
- 361
7
votes
0
answers
68
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,...
CommunityBot
- 1
1
vote
0
answers
67
views
Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part
Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
- 2,057
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 ...
- 5,111
9
votes
1
answer
319
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,838
2
votes
1
answer
90
views
Does an initial algebra for a class have to belong to the class itself?
In the context of algebraic data types, a concept of initial algebras is usually defined, e.g., in the following way:
An algebra $S$ is initial in a class $C$ of algebras iff for every $A\in C$ ...
- 29.5k
4
votes
1
answer
391
views
If a root||nonce Proof-of-Work certificate is prime, can it be used in any other interesting proofs?
Because Bitcoin and many other cryptocurrency mining certificates are "rare" in that their respective hash is less than a very small number, can we leverage their rarity in probabilistic proofs of ...
- 1,145
3
votes
1
answer
59
views
Relation between OSAs and grammars
Are there any relation between order-sorted algebra (OSA) and grammars (context-free grammar in particular)?
If I'm not mistaken, according to [1], there is an equivalence between order-sorted and ...
CommunityBot
- 1
12
votes
2
answers
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 ...
- 38.5k
33
votes
12
answers
7k
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 ...
- 2,057
3
votes
1
answer
173
views
Connection between algebraic logic and computational complexity of logics?
I'm learning a bit about algebraic logic and I was wondering how knowing the algebraic semantics of a given logic might help the study of the logic itself from a computational point of view.
In ...
- 4,495
11
votes
2
answers
361
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 ...
- 1,698
5
votes
1
answer
238
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$...
- 18.6k
2
votes
0
answers
136
views
On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits
As I understand from the survey "Progress on Polynomial Identity Testing - II"
a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown.
However, there exists paper ...
- 2,023
9
votes
0
answers
304
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 ...
- 1,145
0
votes
1
answer
153
views
Is the relation decidable?
Given an ideal $I$ over $\mathbb{C}$ and P, a polynomial, is it decidable whether $P\in I$?
- 4,495
10
votes
2
answers
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 ...
- 16.7k
2
votes
0
answers
72
views
Standard basis for recurrence relations
In polynomial algebra there is a powerful tool for treating system of polynomial equations. It is standard or Groebner Bases. It allows to verify if system is consistent, eliminate variables, reduce ...
CommunityBot
- 1
14
votes
2
answers
751
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 ...
- 51.2k
2
votes
1
answer
102
views
the number of rational points of a curve modulo 2
Consider the language $L=\{f, q\}$ - the number of solutions of equations $f(x,y)=0$ in $\mathbb{F}_q^2$ is equal to zero modulo $2$, where $q = 2^m$. Does $L$ belong to $P$? to $NP$? ($f$ is written ...
- 2,023