The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
4answers
248 views

Counting simple 4-cycles in an undirected graph [closed]

I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it ...
3
votes
0answers
147 views

Finding a basis for the (linear combinations) span of a matrix group, efficiently?

I have an algorithm whose bottleneck is the following task: Let $\mathbb{F}$ be a finite field. Given a set of $k$ invertible matrices $g_1,\dots,g_k\in GL_n(\mathbb{F})$, let $G=\langle ...
2
votes
1answer
474 views

Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq ...
10
votes
1answer
358 views

Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product $$ p=b_1 b_2 \cdots b_n$$ where each $b_i\in A$. Clearly $n-1$ multiplications suffice to compute $p$; ...
3
votes
2answers
184 views

Equipartition of the circle [closed]

Browsing an old technical studies pupil's school book, I have found the description of a method to place at equal distance $N$ points on the circumference of a circle. I am looking for a proof of this ...
3
votes
2answers
193 views

Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances. The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
2
votes
1answer
226 views

efficient arithmetic with (short) Conway games?

We consider "games" in the sense of ONAG. Conway's definition of a game $G$ as a pair $G = \{L \mid R \}$ of sets of games, together with the definitions of inequality and the arithmetic operations ...
1
vote
0answers
52 views

Finding special vectors generated by a matrix

Let $G\in \Bbb Z^{n\times n}$ be a unimodular matrix. Are there any efficient algorithms to find the maximum norm of a vector $v$ that satisfies $\langle\Delta(v),v\rangle=0$ over all vectors $v\in ...
1
vote
0answers
44 views

Covering a set of points by bounded geometric object/objects

1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$. 2) Also, in general setting, the problem is to ...
6
votes
0answers
139 views

Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout. How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...
2
votes
1answer
124 views

Finding particular reduced words for Weyl group elements

I am studying cluster algebra structures on the coordinate rings of partial flag varieties, as defined in the paper Partial flag varieties and preprojective algebras by Geiss, Leclerc and Schröer. One ...
2
votes
1answer
129 views

Are there any good techniques for calculating Hausdorff measure?

I'm aware that many techniques have been developed for the purpose of calculating Hausdorff dimension (although I'm fairly unfamiliar with them), but my question is whether or not we have any good ...
12
votes
1answer
509 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 ...
1
vote
1answer
200 views

Does this algorithm terminate in all scenarios?

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in ...
8
votes
1answer
502 views

How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that $n = \sum_{i=1}^k a_i m_i$? ...
-2
votes
1answer
218 views

Polygon Problem [closed]

There are $N$ regions which are numbered from $1$ to $N$. Each region is represented by a single simple polygon on the 2D plane. Simple polygon means the boundary of the polygon does not cross itself. ...
7
votes
2answers
223 views

How do I efficiently find a sequence of Reidemeister moves between equivalent link diagrams?

In knot theory, two link diagrams are equivalent if and only if they can be related by performing a finite number of Reidemeister moves. But sometimes it is so confusing that I don't know which type ...
0
votes
1answer
131 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
0
votes
0answers
68 views

Minimum cut in near complete graph

I have a problem with an algorithm that i don't quite understand. The mathematics are not the problem, but I don't understand how it can work in practice. The problem is in the paper ...
1
vote
1answer
160 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 ...
6
votes
4answers
489 views

How long does it take to compute a class number?

I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the ...
20
votes
4answers
1k views

Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an information-greedy secret service which has backdoors to all internet nodes throughout the world which permit him to observe all exchanged data ...
1
vote
2answers
107 views

Draws from multiple non-disjoint urns

Let $C = \{1,...,n\}$ be a set of $n$ colors. Let $S_1,...,S_k$ be non-empty subsets of $C$, that is, $S_i \subseteq C$ for all $i \in \{1,...,k\}$. It is helpful to think of the $S_i$ as urns with ...
3
votes
2answers
208 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
255 views

(efficient) method to test $\{n\alpha\}\not\in [A, B]\subset [0,1]$

Suppose $\alpha$ is a fixed given irrational number with $\alpha\in [A, B]\subset [0,1]$, are there any (efficient) methods to compute the least integer $n$ such that the decimal part of $n\alpha$ ...
19
votes
0answers
339 views

Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them. Define the set $\mathcal{E}$ of ...
3
votes
1answer
125 views

Is there an algorithm to compute group presentations of or find generators for the centralizer of a matrix in $GL(n, \mathbb{Z})$?

Let $M \in H \leq GL(n, \mathbb{Z})$. Is there an algorithm that computes either matrix generators or even a group presentation for $C_H(M)$ given generators or a presentation of $H$? Also is ...
5
votes
5answers
285 views

Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...
3
votes
0answers
155 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 ...
9
votes
7answers
2k views

Is there an algorithm to solve quadratic Diophantine equations?

I was asked two questions related to Diophantine equations. Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all ...
1
vote
1answer
171 views

Finding automorphism groups of simplicial complexes

Question: Given a finite simplicial complex $K$, what general techniques allow one to efficiently compute (a presentation of) the group $\text{Aut}(K)$ of $K$'s automorphisms? Since this is ...
9
votes
1answer
281 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 ...
20
votes
3answers
1k views

Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
8
votes
0answers
126 views

Naive Reidemeister-Schreier for $\mathbb Z$ quotients

I have a question about a "standard" variant of the Reidemeister-Schreier algorithm used by topologists when manipulating manifolds they either know or suspect are fibre-bundles over $S^1$. Say you ...
1
vote
0answers
74 views

Testing functional equivalence

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
2
votes
1answer
123 views

Complexity of numerically solving systems over the reals

Basically I am interested in What is the complexity of numerically solving systems over $\mathbb{R}$? By solving I mean finding at least one numeric solution with given precision. Probably the ...
0
votes
1answer
212 views

Algorithm to efficiently sum N boolean numbers. [closed]

I am looking for a fast algorithm to do the following task: Given $N$ numbers $a_i, i=1,..., N$, where $a_i$ can be equal to $0$ or $1$, compute the number $s \equiv \sum_{i=1}^N a_i$ in base 2. ...
7
votes
1answer
232 views

Main problems on lattice-basis reduction algorithms (such as LLL)?

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions: (a) their solution would likely be of some ...
2
votes
1answer
182 views

RefReq: Algorithms for standard operations in Algebraic Number theory

Given an algebraic number field $F$ (I actually don't have an idea how to implement this data already, except for splitting fields of polynomials, but there is something in SAGE) is there free code ...
1
vote
1answer
120 views

Generating k-partite graphs

Does there exist an efficient algorithm for generating all non-isomorphic k-partite graphs up to a certain order $n$? I've read through the nauty tutorial, but it doesn't look like anything beyond ...
7
votes
3answers
657 views

smooth manifolds as real algebraic set (continued)

There are several ways of producing manifolds,say: 1.orbits space of group action 2.connected sum of manifolds 3.underlying topological space of nonsingular algebraic set .... here,i am ...
2
votes
2answers
206 views

Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible

According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine ...
1
vote
0answers
104 views

Row subset selection of matrix to optimize condition number

Given a matrix $\mathbf{A} \in \mathbb{C}^{N\times M}$ with $N \gg M$. This matrix results from a linear equation system and has a certain structure (however, I do not think that details provide any ...
1
vote
3answers
184 views

Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists. Can someone please tell me how do I ...
1
vote
1answer
114 views

Do there exist a way to solve inhomogeneous matrix equations Ax = b for only selected rows?

The inhomogeneous matrix equation $\mathbf{A} x = b$ can be solve in many ways, but in this particular case, I am looking for a solution to this problem on a set of constraints. The matrix $A$ is ...
2
votes
1answer
284 views

Finding integer points inside of a parallelogram

Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
4
votes
2answers
162 views

Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is: ...
4
votes
0answers
160 views

Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$. The graphs have a significant automorphism group (these are disconnected ...
3
votes
2answers
365 views

Hyperrectangle partition of set of overlapping hyperrectangles

I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...
2
votes
1answer
241 views

Finding the vertices of a convex polyhedron from a set of planes

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution. ...