The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
246 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
46 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
141 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
135 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
143 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
516 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
209 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
565 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
225 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
254 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
151 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 ...
1
vote
1answer
165 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
507 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
109 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
216 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
256 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
363 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
139 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
378 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
160 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 ...
10
votes
7answers
3k 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
176 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
313 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
128 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
83 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
128 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
233 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
240 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
185 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
127 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
681 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 ...
3
votes
2answers
217 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
118 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
198 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
119 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
350 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
183 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
163 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
438 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
338 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. ...
4
votes
2answers
230 views

Reference Request: Representing Positive Integers as Differences with Minimal Hamming Weight

Background of my reference request is an observation that I made, while I was still in school: there are two ways to calculate $x*999$: either do it directly, by applying the multiplication algorithm ...
2
votes
0answers
26 views

In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
28
votes
3answers
2k 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 ...
2
votes
3answers
142 views

Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
3
votes
1answer
230 views

Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules. Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...
5
votes
2answers
266 views

Covering convex polygons with inscribed disks

The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around ...
3
votes
0answers
122 views

On understanding Discrete-Valued Stochastic Processes( time series, panel data )

It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...