The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
88 views

Computability of infinite-dimensional vector space

So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be ...
1
vote
1answer
84 views

What is necessary and/or sufficient requirement for a subring of a field to be computable?

As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring? Conditions on either field or subring are fine.
1
vote
0answers
25 views

Decoding of Gabidulin codes

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
1
vote
0answers
83 views

Restoring symmetry in certain combinatorial bijections?

I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an ...
0
votes
1answer
190 views

Classifying noetherian simple groups by order type?

A (possibly infinite) group $G$ is noetherian if it satisfies the following equivalent conditions: (1) every subgroup of $G$ is finitely generated, (2) there is no infinite strict ascending chain of ...
0
votes
0answers
83 views

A 'Fourier-like transform' for quaternions

The following question may be of interest to the engineering/computer graphics audience. Consider the non-commutative field $\mathbb{H}$ of quaternions, named after W. Hamilton. The units of ...
1
vote
0answers
113 views

Spectrum of a variety: a possible connection btw ordinals and structures?

Consider a variety of algebras $\mathbb{V} = \mathbb{V}(\sigma,\tau)$ which consists of the set of algebras defined over a fixed signature $\sigma$ and satisfying a set of identities $\tau$. We may ...
2
votes
0answers
104 views

Possible generalizations of associativity?

The well-known notion of associativity in algebra leads to structures with interesting properties, such as groups or semigroups. According to a paper by John Rhodes, some researchers in algebra and ...
1
vote
0answers
68 views

Composition series and isogeny

I'm not sure this question is appropriate for this site, but it might have some connections with computational algebra. Consider a fixed "category" $\sf{Cat}$ (in the sense of category theory, but ...
2
votes
0answers
114 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 ...
0
votes
1answer
209 views

Extending semigroup theory?

In an earlier question I proposed a definition of associativity for ternary relations generalizing the usual notion for composition laws. I'm still not sure whether this definition makes sense, but if ...
5
votes
1answer
71 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 ...
4
votes
1answer
62 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
147 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 ...
8
votes
1answer
200 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 ...
6
votes
1answer
113 views

Complexity of convolution in the max/plus ring

We can do convolution in $O(nlgn)$ 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 ...
0
votes
1answer
59 views

Is there a 'process algebra' to describe ACID transactions on a database?

There appears to be this beautiful algebra to help you think through the implications of Communicating Sequential Processes by Hoare. What I'm wondering, is there an equivalent algebra that helps ...
4
votes
0answers
64 views

Residual for transitive hull

I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. ...
2
votes
0answers
63 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 ...
9
votes
3answers
275 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 ...
7
votes
0answers
152 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 ...
-1
votes
2answers
271 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 ...
9
votes
2answers
573 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
380 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 ...
22
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 ...
17
votes
4answers
3k 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
90 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
89 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
167 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
112 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
278 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
247 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
273 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
191 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 ...
37
votes
10answers
8k 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
320 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
892 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
243 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
269 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
303 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
205 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 ...
34
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
220 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
193 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
568 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 ...
16
votes
1answer
1k 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
368 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 ...
17
votes
3answers
546 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 ...
4
votes
0answers
544 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 ...
17
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 ...