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.

Filter by
Sorted by
Tagged with
4 votes
2 answers
315 views

Max weighted matching where edge weight depends on the matching

Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
lchen's user avatar
  • 459
4 votes
0 answers
153 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{...
suitangi's user avatar
  • 333
4 votes
0 answers
188 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 ...
Andrea Prunotto's user avatar
4 votes
0 answers
193 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 $...
ippiki-ookami's user avatar
4 votes
0 answers
118 views

Finding short linear combinations in abelian groups

Let $M$ be a finitely generated abelian group. Assume we are given a presentation of $M$, that is \begin{equation*} M = \frac{\bigoplus_{i=1}^r \mathbf{Z}g_i}{\sum_{j=1}^s \mathbf{Z} r_j} \end{...
François Brunault's user avatar
4 votes
0 answers
274 views

Parity of number of primes

In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of ...
Turbo's user avatar
  • 13.7k
4 votes
0 answers
93 views

Exploiting symmetries to speed up Groebner basis calculation?

Take a collection $F$ of homogeneous polynomials in $\mathbb{C}[x_1,\ldots,x_n]$, along with a finite group $G$ of linear operators over $\mathbb{C}^n$ such that for every $f\in F$ and $g\in G$, we ...
Dustin G. Mixon's user avatar
4 votes
0 answers
87 views

Efficient algorithm to construct path augmented graphs with smallest diameter?

I am interested in special graph constructions that have the smallest diameter. We have a path graph $P_n$ ($N$ is even). We add new set of edges $C$ between path nodes such that set $C$ forms a ...
Mohammad Al-Turkistany's user avatar
4 votes
0 answers
139 views

In what range can we find diophantine approximations using the LLL-algorithm?

Let $\alpha_1, \ldots, \alpha_n$ be $\mathbb{Q}$-linearly independent real numbers. I want to show that for all $x_1, \ldots, x_n\in\mathbb{Z}$, $|x_i|<N$ we have some lower bound for $\left|\sum ...
Jan-Christoph Schlage-Puchta's user avatar
4 votes
0 answers
182 views

Optimal instructions for the modular construction of rectlinear Lego structures

Let $X$ be a compact (or periodic) union of integer translates of unit cubes such that the interior of $X$ is connected. (If it makes any difference, suppose that the dimension $n$ of $X$ is 3.) I am ...
Steve Huntsman's user avatar
4 votes
0 answers
86 views

Efficient CW structures on squarefree semi-algebraic set

General Setup Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which ...
Vidit Nanda's user avatar
  • 15.4k
4 votes
0 answers
123 views

How to enumerate a discrete group of matrices by their Frobenius norm?

Suppose I have a discrete group $G<\mathrm{SL}_2(\mathbb{C})$, and it is finitely generated by some known generators. That is, $G=\langle g_1,\dots,g_n\rangle$. The Frobenius norm of a matrix $m=\...
j0equ1nn's user avatar
  • 2,438
4 votes
0 answers
146 views

What is the influence of unreliable comparisons on the results of sorting

Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...
Jessy's user avatar
  • 41
4 votes
0 answers
248 views

Comparison of Constrained Optimization Methods

I am trying to solve a constrained optimization problem using filter methods and came across two papers on the topic that I am having some problems with. The original filter method paper is the ...
RustyStatistician's user avatar
4 votes
0 answers
2k views

Weighted Median Filtering

Let's begin with a little review of unweighted median filtering. Suppose I have a list of $N$ real-valued numbers, $x=x_1,...,x_N$. Let $m_i$ be the median of $K$ consecutive values: $m_i=$ median$(...
Bill Bradley's user avatar
  • 3,809
4 votes
0 answers
176 views

Computing the density of a set of multiples

Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
Charles's user avatar
  • 8,974
4 votes
0 answers
192 views

What is the complexity of intersecting two matrix algebras over a finite field?

The following question arose in a joint project with Arkadius Kalka and Adi Ben-Zvi. Let $\mathbb{F}$ be a finite field, and $M_n(\mathbb{F})$ be the $n\times n$ matrices over $\mathbb{F}$. For a ...
Boaz Tsaban's user avatar
  • 3,104
4 votes
0 answers
575 views

Minimum number of real multiplications to multiply two quaternions [closed]

Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows: $$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$ We only need the ...
Adhvaitha's user avatar
  • 151
4 votes
0 answers
174 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
Thomas Kalinowski's user avatar
4 votes
0 answers
312 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning? [closed]

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). It seems to me that much ...
Charlie Parker's user avatar
4 votes
0 answers
220 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. Assumptions about the graph: You may ...
real's user avatar
  • 323
4 votes
0 answers
214 views

What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...
a guest's user avatar
  • 41
4 votes
0 answers
130 views

Generating random weak k-bounded reverse plane partitions

Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that $\pi_{ij}...
Alex R.'s user avatar
  • 4,902
4 votes
0 answers
351 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 ...
Torsten Schoeneberg's user avatar
4 votes
0 answers
207 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 ...
Slava Rychkov's user avatar
4 votes
0 answers
171 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 ...
user2551507's user avatar
4 votes
0 answers
634 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 ...
Bart Jansen's user avatar
4 votes
0 answers
754 views

(Co)limit computations for diagrams of Vector Spaces

Fix a field $K$ and consider a finite directed graph $\Gamma$ where multiple edges between a pair of vertices are allowed so long as the total number of edges is finite. Associate to each vertex $v$ a ...
Vidit Nanda's user avatar
  • 15.4k
4 votes
0 answers
391 views

Matching a binary matrix

Given a MxN 0-1 matrix D, with the property that both M and N are odd numbers its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1). How do we find M ...
Chong Luo's user avatar
  • 167
4 votes
0 answers
241 views

Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions. Call a lattice ...
Dave Pritchard's user avatar
4 votes
0 answers
267 views

Finding generalised Lyndon words

Let $\Sigma = \lbrace a_1, \ldots, a_n, A_1, \ldots A_n \rbrace$ (where $A_i = a_i^{-1}$) and $\prec$ be a total ordering on $\Sigma$. Let $\Sigma^*$ be the set of all words (generated by the ...
Mark Bell's user avatar
  • 3,125
4 votes
0 answers
338 views

Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times n-$...
Hari's user avatar
  • 313
4 votes
0 answers
164 views

The mathematics of Schellings segregation model

For those who don't know the model. You can read this pdf. I want to find what is the probability that 2 nodes are each others neighbors when the algorithm converges (i.e. when all nodes are happy). ...
Bruce's user avatar
  • 41
3 votes
4 answers
1k views

Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?

There is a claim on https://en.wikipedia.org/wiki/Super-recursive_algorithm#Inductive_Turing_machines that 'Simple inductive Turing machines are equivalent to other models of computation such as ...
Turbo's user avatar
  • 13.7k
3 votes
2 answers
2k views

The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function. Preliminary: Mertens function and the ...
Nathan McKenzie's user avatar
3 votes
3 answers
2k views

Is there a simple criterion to determine if two parallelograms intersect?

Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty? Note that I do not need to actually find the intersection.
Philipp's user avatar
  • 969
3 votes
5 answers
4k views

Algorithm to find all the cycle bases in a graph

I am given a graph defined by vertexes and edges. I have to obtain all the cycle bases in a network. No coordinates will be given for the nodes. Here's a sketch that illustrates my point. Note that ...
Graviton's user avatar
  • 381
3 votes
3 answers
4k 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 ...
Behzad's user avatar
  • 87
3 votes
4 answers
3k views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
alezok's user avatar
  • 418
3 votes
2 answers
554 views

How to tell if two or more knots are linked

Given a number of knots, I would like to know if they are linked. I know that the linking number can tell if two knots are linked. There is any method that completely solves this problem?
teide4's user avatar
  • 31
3 votes
3 answers
210 views

Rank(A) and other algorithms as a polynomial

If $A = (\alpha_{ij}) \in \mathbb{C}^{nxm}$ we have simple algorithms by which to determine $\mathrm{rank}(A)$. However, is there a polynomial $f \in \mathbb{C}[\alpha_{ij}]$ where $f \colon \mathbb{C}...
Mark Bell's user avatar
  • 3,125
3 votes
1 answer
216 views

Computabillity of packing of spheres with different radii

This is a conceptually easier version of a box packing problem I stated earlier. Let $n$ be a positive integer and let $r_1, \ldots, r_n$ be positive integers. We take $r_i$ to be the radius of a ...
Dominic van der Zypen's user avatar
3 votes
2 answers
1k views

Enclosing a set of ellipses within one ellipse

Is there an algorithm that takes in a set of ellipses and gives back an ellipse that encloses the original set of ellipses?
lts's user avatar
  • 147
3 votes
1 answer
354 views

$\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)$ Double Summing a (Not Completely) Multiplicative Function

Let $f(n)$ be a multiplicative function that is not completely multiplicative, i.e $f(m)\cdot f(n)= f(m\cdot n)$ only if $gcd(m,n)=1$. Let $S(x)$ be the double sum over $f$, that is: $$S(x)=\sum_{i=1}...
MC From Scratch's user avatar
3 votes
2 answers
557 views

Complexity of establishing finite groups (non)-isomorphism ?

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N ...
Alexander Chervov's user avatar
3 votes
4 answers
2k views

Enumerative algorithm through inclusion-exclusion

Hello everybody ! I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. ...
Nathann Cohen's user avatar
3 votes
2 answers
313 views

Is this BBP-type formula for $\ln 31$, $\ln 127$, and other Mersenne numbers also true?

In this post, a binary BBP-type formula for Fermat numbers $F_m$ was discussed as (with a small tweak), $$\ln(2^b+1) = \frac{b}{2^{a-1}}\sum_{n=0}^\infty\frac{1}{(2^a)^n}\left(\sum_{j=1}^{a-1}\frac{...
Tito Piezas III's user avatar
3 votes
2 answers
984 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$?
Minnie's user avatar
  • 41
3 votes
1 answer
443 views

Does a product of matrices have eigenvalue 1

Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$. For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an ...
Mark Bell's user avatar
  • 3,125
3 votes
1 answer
433 views

Find the least prime $p$ such that $mn$ divides $p-1$

My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice. Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ ...
Aaron Sterling's user avatar

1
11 12
13
14 15
32