The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
92 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
256 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
246 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
188 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
133 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
692 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
220 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 ...
2
votes
0answers
125 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
202 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
120 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
383 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
198 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
167 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
462 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
385 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
236 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
27 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
143 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
286 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
273 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
124 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 ...
4
votes
1answer
108 views

Algorithm to detect if an element of a (commutative) ring is in a subring?

For rings finitely-generated over a field, the theory of Groebner bases gives us quite an efficient algorithm for determining whether an element of the ring is in a given ideal of the ring. Is there ...
7
votes
2answers
336 views

Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the ...
3
votes
0answers
199 views

Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem. Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
1
vote
1answer
87 views

computing $c_5$ in “Primality testing with Gaussian periods”

As far as I know, the April 2011 version of #143 on this page has not been improved upon. On page 10 of that paper, the authors give an algorithm that uses a constant $\:c_{\hspace{.01 in}5}\:$. ...
1
vote
1answer
139 views

What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem? Beltway Reconstruction Problem: Assume there is a set of ...
6
votes
3answers
733 views

Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
2
votes
1answer
162 views

Algorithm to find if an element X can be represented with the sum of one number of each subset in $O(n^2)$?

Here is the problem: I have 3 subsets ( called $S_1$, $S_2$ and $S_3$) that each have $N$ elements (arbitrary elements). So I have one element $X$. I want to know if I can get $X$ making the sum of ...
2
votes
1answer
202 views

Algorithm for representing a polynomial as a composition of lower degree polynomials

Let $q$ be a large prime and $e$ an integer such that $GCD(e,q-1)=1$. Let $p(x)$ be a polynomial of degree $e^n$ with coefficients in $\mathbb Z_q$ such that there exists a progression of polynomials ...
5
votes
1answer
463 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 ...
6
votes
2answers
207 views

Recovering a Weighted Graph from Shortest Path Distances

I am interested in the following problem (A) and its related formulation (B). (A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), ...
14
votes
5answers
569 views

Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics? Can we ...
3
votes
1answer
218 views

Is the prime ideal principal which is in 256-th cyclotomic ring lying over 257?

As we known, the integer ring R of 256-th cyclotomic field is not a Principal Ideal Domain. And rational prime 257 is split completely in R. Suppose prime ideal P of R is an arbitrary ideal lying ...
5
votes
1answer
645 views

Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?

Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points. The $LEC$ problem is stated in this way: find a $LEC$ whose ...
4
votes
1answer
326 views

Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...
4
votes
1answer
210 views

convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...
8
votes
2answers
220 views

Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...
0
votes
1answer
122 views

What is the Bahadur-Anderson Algorithm?

What is the Bahadur-Anderson Algorithm, and which book could one read to learn it?
1
vote
2answers
1k views

Trilateration problem

When trying to develop an algorithm for a program, I got with the following problem: Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...
1
vote
3answers
221 views

Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...
5
votes
2answers
794 views

Solve for $A$ and $B$ in $AXB=Y$

Let $R = \mathbb{Z}[x_{1}, \dots, x_{r}]$. Let $X$ be $n \times n$ matrix with entries in $R$. Let $Y$ be $m \times m$ matrix with entries in $R$ formed from $\mathbb{Z}$-linear or $\mathbb{R}$-linear ...
4
votes
0answers
284 views

Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$. It ...
26
votes
1answer
429 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 ...
7
votes
0answers
141 views

How quickly can we test if a graph is distance-regular?

A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...
3
votes
3answers
799 views

L-systems and Sierpinski Triangle

I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below). I'm interested to know how could one arrange the rules of ...
3
votes
1answer
345 views

Fastest Digit Extraction for Any Irrational Number

I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for ...
0
votes
1answer
221 views

Giving a general term of a recursive function, and upper bound for it

Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$. Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise Let ...
2
votes
3answers
273 views

existence of equivalence checking algorithm

Set D : Set of decision algorithms X∈D if and only if X is an Turing machine algorithm with finite length takes one input i, binary number X(i)=0 or X(i)=1 or X(i) runs ...