# 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.

1,317 questions
Filter by
Sorted by
Tagged with
111 views

53 views

### Primality of $n$ bit integers in depth $n^\alpha$ under standard conjectures?

Denote $\mathsf{NC}(\mathsf{SUBLINDEPTH}(n),f(n))$ to be set of boolean circuits of fan-in $2$ which can be represented by depth $\cap_{\alpha>0}\mathsf{}n^\alpha$ and $f(n)$ sized Boolean circuits....
58 views

### Algorithm for computing group inverse of some matrices

I am interested in algorithms (and implementations) for computing the group inverse of $\rho(A)I - A$ of a non-negative irreducible matrix $A$. In the well-cited reference [1], the author describes in ...
85 views

### String compression algorithms for simplifying an expression by introducing variables

I have a very long algebraic expression computed with Maple, and when I inspect it visually, it is clear that it consists of a set of terms that appear over and over again. For purposes of human ...
34 views

### Relation of 1-trees to optimal tours

Question: given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ ...
56 views

### Maximum weight matching with classes of edges in a multi-edge bipartite graph

Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning ...
53 views

57 views

### Generating triangulations with given topology

I am looking for information about the problem of identifying the heaviest minimal subset $F\subset E$ of the edgeset $E$ of a complete symmetric graph $G(V,E)$ with randomly weighted edges such that ...
52 views

### Why does Y. Moshe Vardi use this specific matrix when estimating source-destination traffic intensities with EM algorithm?

Sorry for the verbose title, but the question is super specific. If you happen to know a site better suited for these types of question, feel free to direct me. The article to which I am referring to ...
157 views

### Sampling method for a specific distribution in high dimensions

We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, where $d\ll n$. Given any point $\mathbf{p}$ on the unit $(d-1)$-sphere $\mathcal{S}$, we define ...
47 views

### Are two degree sequences compatible, for random simple graph generation?

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
231 views

### Verification of a maximal antichain

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the ...
61 views

### What are the complexity classes of these problems about divisibility and coprimality?

The problems 'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?' 'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
191 views

### What is the complexity class of this problem without Cramer's conjecture?

The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...
18 views