The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
436 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
14
votes
9answers
6k views

Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
13
votes
3answers
1k views

When are (finite) simplicial complexes (smooth) manifolds?

Hi, is there an algorithm that determines if a given simplicial complex is a.) a manifold b.) a smooth manifold c.) homotopy equivalent to a manifold d.) a real algebraic variety ?
9
votes
1answer
257 views

Can Tarski decide constructibility in elementary geometry?

Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction? The answer does ...
12
votes
1answer
1k views

Distinct numbers in multiplication table

Consider multiplication table for numbers $1,2,\cdots, n$. How many different numbers are there? That is how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there? I'm interested ...
21
votes
8answers
8k views

Fast Matrix Multiplication

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in ...
18
votes
1answer
200 views

Decidability of equality of expressions built using 1,+,-,*,/,^

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
29
votes
2answers
2k views

Does anyone want a pretty Maass form?

A few months ago, I was curious about some properties of Maass cusp forms, of nonabelian arithmetic origin. As a result, I went through a somewhat predictable process of finding a totally real $A_4$ ...
8
votes
3answers
1k views

Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ? (Main case - complex numbers, comments on other cases are also welcome. "Given" ...
9
votes
2answers
439 views

When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?

To ask this question in a (hopefully) more direct way: Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ ...
12
votes
6answers
4k views

Good algorithm for finding the diameter of a (sparse) graph?

My question on Stack Overflow was recently tagged "math". Despite a bounty, it never received a satisfactory answer, so I thought I would ask it here: I have a large, connected, sparse graph in ...
5
votes
2answers
516 views

Differential ideal membership problem

We know that in the ordinary algebra ideal case, the ideal membership problem can be solved by the Grobner Base theory, then, is there a counterpart theory in the differential ideal case? To be ...
9
votes
1answer
393 views

Stable matchings when switches have costs

The Gale-Shapley algorithm finds a stable matching in the complete bipartite graph, for any preference matrix. It's also well-known that stable matchings don't always exist in the complete graph ...
6
votes
1answer
332 views

Is equality of terms for “real” numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
5
votes
1answer
551 views

Algorithm for embedding a graph with metric constraints

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide if there is an ...
3
votes
0answers
144 views

Comparing different Euclidean algorithms on a Euclidean domain

I have posted this question at stackexchange (502413), without responses until now. In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About ...
27
votes
3answers
1k views

Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$, decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective, respectively, injective? -- And ...
7
votes
1answer
335 views

Building a polyhedron from areas of its faces

Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
1
vote
5answers
1k views

The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure. Thanks
1
vote
1answer
2k views

Detection of Redundant Constraints

Suppose I pose the following query to a constraint logic programming system: ?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3. Are there systems that would recognize the last inequality as ...
12
votes
2answers
375 views

Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...
6
votes
1answer
218 views

Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?

I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in ...
3
votes
2answers
203 views

Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$. Given $g$ and either $$ A = x g^ x$$ or $$ A = x g^{x^2-1}$$ find $x$. What is the complexity of solving this? Is there a reduction to the discrete ...
2
votes
1answer
141 views

algorithmic almost equitable partitioning

Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly ...
1
vote
1answer
152 views

Set of distributions that minimize KL divergence,

Assuming that $p,q$ are probability distributions defined on the same support $\{x_i\}_{0 \leq i \leq n}$, $\epsilon$ a small real number, and $D_{KL}$ the Kullback-Leibler divergence, is there a ...