Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithms]

Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.

0
votes
0answers
39 views

Does there exist a primitive recursive algorithm whose execution result can be verified non-recursively?

Does there exist a primitive recursive algorithm whose execution result on arbitrary input can be verified without re-executing the algorithm itself, or with a computational complexity that is lower ...
0
votes
1answer
39 views

Sparse dense matrix versus Non-sparse dense matrix in eigenvalue computation

I have a matrix in the form of $2n\times 2n$ block matrix $$ A = \begin{pmatrix}O& W\\ J& D\end{pmatrix} $$ where, $O$ is an $n\times n$ zero-matrix; $W$ is a n-by-n diagonal matrix, $W = ...
5
votes
1answer
76 views

On the convergence of MIller's Algorithm for special function evaluation (hypergeometric 1F1)

This is going to a longish question, so the short version first: Is there a way to sanity-check which solution to the 3-term recurrence relation an application of Miller's algorithm has converged on? ...
1
vote
0answers
35 views

Primary decomposition with parameters

$\newcommand\QQ{\mathbb{Q}}$ Considering the polynomial $$f = x^2 - a y$$ one notes, that it is irreducible in $\QQ[x,y]$ for all $a \neq 0 \in \QQ$ and factors for $a = 0$. More generally, let $A=...
2
votes
0answers
80 views

Variety Isomorphism Problem for Abelian Surfaces

This is a special case of this question, where it is asked whether there exists an algorithm to determine whether two varieties are isomorphic. There, an answer by Bjorn Poonen explains how to solve ...
5
votes
1answer
159 views

Relevance of Landau's Algorithm for Denesting Radicals

I just came across a Wikipedia article Nested Radicals that mentions Landau's Algorithm for deciding, whether a nested radical can be denested, but that Wikipedia article is just a stub. Googling "...
0
votes
0answers
54 views

What's equal the below power nested radical?

The same copy of this question is montioned here in SE with no convinced Answer , I want to know what MO will say about the below nested radical as a power form it is well known that $$\frac{2}{\...
14
votes
1answer
555 views

“Gauss trick” vs Karatsuba multiplication

This question is inspired by article Alexander Shen "Gauss multiplication trick?" (submitted to "Mathematical Enlightenment"). Dasgupta, Papadimitriou, Vazirani, Algorithms (2008) Ch. 2: The ...
2
votes
1answer
97 views

Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time?

In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also ...
0
votes
0answers
41 views

Computing derivative of certain path integrals

Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
0
votes
3answers
97 views

Clustering on tree

I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...
8
votes
2answers
286 views

Domination problem with sets

For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond. Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets ...
3
votes
1answer
86 views

Is coprimality in $NC$?

Following reference https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf claims integer coprimality is in $NC$ and it also has one citation. Is this claim valid?
31
votes
1answer
3k views

Does the algorithm of the Greeks produce all prime numbers?

Let ${\cal P}$ be the set of prime numbers. Define a subset ${\cal P}'=\{p_1,p_2,p_3,\cdots\}$ of ${\cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${\cal P}$ ...
4
votes
1answer
75 views

Separate the trivial partition by a linear hyperspace

Let $e=[1,1,\ldots,1]\in\mathbb{Z}^n$. I am looking for a way to find a vector $a\in\mathbb{Z}^n$ such that: $\langle a,e\rangle=0$ and for every nonnegative $v\in\mathbb{Z}^n$ such that $\langle e,v\...
4
votes
0answers
112 views

Subgroup membership problem for Noetherian groups

I am interested in the status of the subgroup membership problem (MP) for finitely presented Noetherian groups. That is, given a finite presentation $\langle X,R\rangle$ for a Noetherian group, \begin{...
2
votes
1answer
86 views

The complexity of sorting a list having one free cell

Making a standard bureocracy (using Word tables), I arrived to the following Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say ...
1
vote
0answers
149 views

Skew-symmetric multi-derivations of $k[x_1,…,x_n]/I$

Let $I = \langle f_1, \ldots f_r \rangle$ be an ideal in $R=k[x_1,\ldots,x_n]$ where $k$ is a field, and put $A = R/I$. (If $I$ is prime then $A$ is the coordinate ring of an irreducible affine ...
3
votes
0answers
43 views

Karp hardness of two cycles which lengths differ by one

Our problem is as follows: NEARLY-EQUAL-CYCLE-PAIR Input: An undirected graph $G(V,E)$ Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO Is ...
6
votes
1answer
69 views

What is the complexity of counting Hamiltonian cycles of a graph?

Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard. Is it also $PP$-hard in the sense ...
2
votes
2answers
126 views

In practice, what's the fastest method to find a least square solution rather than using SVD decompostion?

I'm working on a real-time implementation of Lucas-Kanade for optical flow. However, the SVD decomposition to do achieve the least square method to reduce the error seems to take too much time. A ...
1
vote
1answer
63 views

Algorithm for cliques in weighted graph

Is there a known algorithm (besides brute force) for the following problem: We have given an edge-weighted complete graph $G$ and a finite set of natural numbers $A = \lbrace n_1,\ldots,n_k \rbrace$ (...
7
votes
1answer
173 views

Counting spanning trees of a planar graph

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...
2
votes
1answer
137 views

Decide if a system of arithmetic sequences is an $m$-cover of $\mathbb{N}$

Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences. For a positive integer $m$...
1
vote
1answer
142 views

Shortest bisecting line [closed]

I have troubles finding this:     I don't know how to find this or even write algorithm to do this. Can you help me? Thanks in advance
1
vote
0answers
60 views

Walk in the graph induced by a group action

Suppose that graph $G$ is induced by a group $⟨α_1,...,α_r⟩$ acting on a large finite set $X$ for small $r$. To be precise, we have the vertex set $V(G):=X$, and $x_1x_2\in E(G)$ whenever for some $\...
1
vote
1answer
81 views

How many iterations the best biprime factoring method has to factor a number [closed]

I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...
9
votes
1answer
276 views

Are finite presentations of arithmetic groups computable?

In this famous paper by Borel and Harish-Chandra, Arithmetic Subgroups of Algebraic Groups, it is proved that, in characterisitic zero, arithmetic groups are finitely presented. I have an extremely ...
0
votes
0answers
18 views

When is the first blocking flow created in Dinic's algorithm a max flow?

When is the first blocking flow created in Dinic's algorithm a max flow? I understand that this is usually an iterated algorithm where one creates level graphs and augments the existing blocking flow ...
12
votes
1answer
187 views

Factoring polynomials over the abelian closure of the rationals

What algorithms are known to perform the following task? Input: a univariate polynomial over the rationals $f \in \mathbb{Q}[t]$. Output: the factorization of $f$ into irreducible factors over the ...
9
votes
1answer
342 views

Fast convolution of sparse functions

Let $F:\mathbb{R}\to \mathbb{Z}$ be a step function with at most $k$ discontinuities, at given rationals $a_1<a_2<\dotsc<a_k$. Let $g:\mathbb{R}\to \mathbb{Z}$ be given as a linear ...
3
votes
0answers
95 views

Generating a Penrose tessellation around a given tile

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it. The following picture illustrates the request: In this example, the starting tile is a "thin rhombus" (the pink ...
4
votes
2answers
246 views

Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
3
votes
1answer
98 views

Matching two sequences between each other

Given the sequence of symbols $A$ (contains ~10,000 symbols) and sequence of blocks $B$ (contains ~3,000 blocks, ~30 symbols inside each block) I need to exclude some blocks from sequence $B$ so that ...
2
votes
0answers
60 views

Computational complexity for spectral radius of symmetric matrix

What is the best known algorithmic complexity for computing the spectral radius (largest eigenvalue in magnitude, possibly with respect to some precision and confidence) of a symmetric matrix of size $...
3
votes
0answers
98 views

Algorithm detecting all distinct k-th powers in a string for all k ≥ 3

In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$. The ...
0
votes
0answers
38 views

A name for algorithms that perform well in an asymptotic sense, when inputs are random

Is there a term for an algorithm that performs "well" (say, within a constant factor of optimality) in an asymptotic sense when a large number of random inputs are provided? For example, say I had an ...
0
votes
1answer
91 views

Sampling a uniformly distributed point INSIDE a hypersphere?

There is a simple algorithm to pick a random point ON an $n$-dimensional hypersphere. Is there one to sample a point from inside it? (Sampling points from a hypercube and rejecting them if they are ...
2
votes
0answers
56 views

Recovering a rank-one matrix from its eigendecomposition after randomized rounding

Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting $$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
38
votes
1answer
766 views

How to be rigorous about combinatorial algorithms?

1. The question This may be the worst question I've ever posed on MathOverflow: broad, open-ended and likely to produce heat. Yet, I think any progress that will be made here will be extremely useful ...
5
votes
3answers
196 views

Algorithm to decide if the union of a set system covers the power set

Assume that we have a set system $\mathfrak T = \{\mathcal T_1, \mathcal T_2, \dots, \mathcal T_N \}$ where each $\mathcal T_k$ is a collection of subsets of $[n] := \{1,\dots,n\}$ of the form $$ \...
2
votes
1answer
186 views

Name and Algorithms for a Sparsest Circle Packing

The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...
2
votes
0answers
86 views

Loopless algorithm for generating permutations (Steinhaus-Johnson-Trotter)

The following is a description of the well-known Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element ground set using adjacent transpositions. In fact, it is a loopless ...
1
vote
1answer
94 views

An variation of an assignment problem in combinatorics: assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. ...
0
votes
0answers
32 views

Edgebreaker algorithm over 2-manifolds

Suppose I triangulate a 2-manifold and make a dual pseudograph over it. If I do the Edgebreaker compression algorithm over this graph to generate a spanning tree, can exist an edge with three or more ...
6
votes
0answers
59 views

Deciding positivity of real cyclotomic numbers efficiently

Consider a cyclotomic field $\mathbb{Q}[\zeta_n]$ for fixed $n$ and assume that an embedding $\mathbb{Q}[\zeta_n] \hookrightarrow \mathbb{C}$ has been chosen, say by fixing once and for all $\zeta_n=\...
1
vote
0answers
27 views

How to express free Lie algebra elements in terms of the right-normed basis?

Article A right normed basis for free Lie algebras and Lyndon–Shirshov words shows that it is possible to build right-normed (right-nested) basis of a free Lie algebra. I am looking for references (...
4
votes
2answers
181 views

Example of concrete statement which requires probabilistic algorithm

In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks ...
1
vote
0answers
65 views

Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
11
votes
0answers
175 views

Fast computation of matrix product $AXA^T$ with fixed $A$?

Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...