The algebra tag has no wiki summary.
-1
votes
2answers
151 views
Matrix Multiplication algorithms for research
I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100. (Or more perhaps later on). I am a little confused about the algorithm I should be using for ...
0
votes
0answers
46 views
Parallelization of an iterative model
What I have:
An iterative process based on the application of a very simple algebra to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th ...
8
votes
2answers
371 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
3answers
239 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 ...
18
votes
2answers
3k 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 ...
15
votes
4answers
2k 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 ...
5
votes
1answer
78 views
Number of operations to compute product of pairwise sums over a commutative semiring
Let $S$ be a commutative semiring and $T\subset S$, how many semiring operations are required to compute the following
$$\prod_{a,b\in T} a+b$$?
This problem can be solved for commutative rings in ...
1
vote
0answers
69 views
Equivalence relations on strongly regular graphs with same parameters
Let $\mathcal{S}$ be the set of all strongly regular graphs with parameter
$(n, k, \lambda, \mu)$. Are there any (interesting) equivalence relations defined on this set?
My motivation is to approach ...
8
votes
1answer
113 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 ...
0
votes
0answers
106 views
count number of i such that ( (a*i+b) mod p) mod k == l
How to determine the number of $i$'s as fast as possible such that
$$1\le i \le L$ and $((ai+b)\mod p) \mod k = l$$
where $p$ is a prime number, $1\lt a, b\lt p-1$, and $l \lt k \lt L \lt p$.
This ...
2
votes
1answer
134 views
How to go about proving the basic operators in relational algebra are independent of each other?
The five basic operator select, project, cross, union and diff in relational algebra are independent of each other. I'm trying to formally prove this statement but can only progress for cross product ...
5
votes
0answers
192 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 ...
12
votes
2answers
210 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 ...
8
votes
2answers
140 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 ...
27
votes
10answers
4k 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 ...
15
votes
0answers
303 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 ...
18
votes
4answers
622 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 ...
7
votes
2answers
230 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$: ...
0
votes
0answers
222 views
Commutation between a permutation matrix and the sum of permutation matrices corresponding to n-cycles
Let $S_n$ be the set of all permutations of $n$ elements. Consider the regular representation of $S_n$ in $GL(\mathbb{R}^{n!})$ by $S_n\ni \pi \rightarrow P_\pi$: $(P_\pi)_{\sigma\tau}=1$ if $\pi ...
4
votes
1answer
241 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 ...
4
votes
1answer
187 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 ...
28
votes
10answers
1k 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 ...
4
votes
1answer
209 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 ...
5
votes
1answer
175 views
Are 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 ...
16
votes
2answers
483 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 ...
15
votes
1answer
806 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 ...
6
votes
3answers
337 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 ...
16
votes
3answers
521 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 ...
3
votes
0answers
487 views
Is Witten's new method of quantization useful for geometric complexity theory? [closed]
The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...
16
votes
4answers
1k 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 ...
6
votes
5answers
254 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 ...
12
votes
3answers
391 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
203 views
Optimizing multiplication in a partly commutative semigroup
Let us say I have a semigroup M and its basis B. I know which elements of B commute.
What is the most efficient way to do multiplication in such a semigroup?
Essentially, this is a question of how ...
4
votes
2answers
419 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?
