All Questions
2,073 questions
0
votes
0
answers
5
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 516
2
votes
2
answers
148
views
Algorithms (or packages) to find recurrence relations for given sequence of q-polynomials?
Assume we have sequence of polynomials : $P_i(q)$ - each term is polynomial in $q$. (With integer coefficients, but hopefully it is not important).
We expect that there exists recurrence relation a ...
- 24.8k
1
vote
0
answers
28
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
1
vote
1
answer
170
views
+50
On a probabilistic integer factorization algorithm given bounds for one prime factor
We got a probabilistic integer factorization algorithm and experimental evidence with large
integers given bounds for one factor.
Let $D \ge 2$ be real number and let $p,q$ be primes and $N=pq$.
...
- 25.4k
1
vote
0
answers
29
views
Factoring semiprimes via sum of two squares? [migrated]
The following thoughts came into my head after watching Grant Sanderson's JBPM award lecture here, in which he discusses the fact that we can quickly factor 3599 by noticing it can be written as (60-1)...
- 61
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
0
votes
0
answers
78
views
Factoring totient of a prime
Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem?
What about when $2p+1$ is also a prime?
- 13.9k
1
vote
0
answers
57
views
Step back step forward algorithm for A108442
Let $a(n)$ be A108442. Here generating function is $\frac{1}{1-zA(z)}$ where
$$
A(z) = 1 + z(A(z))^2 + z(A(z))^3.
$$
Also
$$
a(n) = \sum\limits_{k=1}^{n}\frac{k}{2n-k}\sum\limits_{i=0}^{n-k} \binom{2n-...
- 4,928
0
votes
0
answers
24
views
Minimizing intersections between spanning trees of graph embeddings in polynomial time
Assume I have $N$ complete graphs $G_1, G_2,...,G_N$, and consider their embeddings $E_1, E_2,...,E_N$ in $\mathbb{R}^2$. Is there a (potentially stochastic) polynomial time algorithm to construct ...
- 1
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
1
vote
1
answer
217
views
What is the fastest known algorithm for evaluating a homogeneous binary polynomial?
This question was initially posted on math.stackexchange.com, but there is no appropriate answer, hence I have the right to publish it here again.
Let $f(x,y) = \sum_{i = 0}^d f_i x^i y^{d-i}$ be a ...
- 1,833
2
votes
0
answers
182
views
Algorithm for $\frac{1}{1-x} = \sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n}\frac{1-kx}{1+kx}$
Let $a(n)$ be A208832. Here
$$
\frac{1}{1-x} = \sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n}\frac{1-kx}{1+kx}.
$$
Start with vector $\nu$ of fixed length $m$ with elements $\nu_i = 1$ (that ...
- 4,928
1
vote
0
answers
96
views
Determine equivalences in the generated collection of subgroups and quotients
Let $A$ be an abelian group, and $B_1, B_2, \dots, B_m$ be subgroups of $A$. Define the family of subgroups $\mathcal{D}_0 = \{ \{0\}, A, B_1, B_2, \dots, B_m \}$.
Let $\mathcal{C}_1$ be the ...
- 807
0
votes
0
answers
17
views
Faster algorithm for maximum-weighted convolution
I am implementing an algorithm from a paper titled "Adaptive Multi-Trace Carving Based on Dynamic Programming." Specifically, this algorithm requires solving the following:
$$
y[n] = \max_{k ...
- 1
1
vote
0
answers
161
views
Efficient algorithm for A217061
Let $a(n)$ be A217061. Here
$$
a(n) = \sum\limits_{m=1}^{n}\frac{1}{(m-1)!}\sum\limits_{k=0}^{n-m}(n+k-1)!\sum\limits_{j=0}^{k}\frac{1}{(k-j)!}\sum\limits_{\ell=0}^{j}\frac{2^{\ell-j}(-1)^{\ell+j}s(n-...
- 4,928
5
votes
1
answer
264
views
Approximation of Hamiltonian cycles
Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
- 53
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
0
votes
0
answers
44
views
Large Deviation Principle for an adaptive sampling rule for Multi Armed Bandits
Consider the following adaptive strategy for sampling from a Multi Armed Bandit with $K$ arms:
Split the $T$ rounds into $N (\in \mathbb{N})$ disjoint intervals. Each interval is indexed by $i=1,2,\...
- 9
0
votes
0
answers
64
views
Algorithm and equivalent recursion for A258173 (related to Dyck paths)
Let $a(n)$ be A258173 i.e. sum over all Dyck paths of semilength $n$ of products over all peaks $p$ of $y_p$, where $y_p$ is the $y$-coordinate of peak $p$.
A Dyck path of semilength $n$ is a $(x,y)$-...
- 4,928
0
votes
0
answers
60
views
Algorithm for $q$-Bell numbers
Let $T(n,k)$ be A126347 (i.e., triangle, read by rows, with row polynomials $B(n, q)$). Here
$$
B(n, q) = \sum\limits_{k=0}^{n-1}\binom{n-1}{k}B(k, q)q^k, \\
B(0, q) = 1.
$$
Start with vector $\nu$ of ...
- 4,928
3
votes
1
answer
435
views
What is the connection between these three methods of generating this sequence?
I was recently looking at this problem: “There are a number of balls in a jar, some of them red, some of them white. The odds of picking two at random and both balls being red is 1/2. How many of the ...
- 39
1
vote
1
answer
177
views
Algorithm for A127782
Let $a(n)$ be A127782 (i.e., an integer sequence with generating function $A(x)$ such that $A(x)=1+xA(x+x^2)$). Here
$$
a(n) = \sum\limits_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{...
- 4,928
12
votes
0
answers
530
views
Finding the diameter of an unknown tree: Is BFS optimal?
I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the ...
- 63
-1
votes
1
answer
167
views
On an equality obtained from analysis of an algorithm
I came across the following equality $$\Big(\frac{c n^b}{x}\Big)^{dx}=n^{n/x}$$ where $b,c,d\geq0$ are fixed and $n$ increases when I was analyzing an algorithm.
What is a good approximation for $O(n^{...
- 13.9k
2
votes
0
answers
61
views
Algorithm for main diagonal of integer coefficients associated with Schroeder numbers
Let $T_q(n, k)$ be an integer table such that
$$T_q(n, k) = \begin{cases}
1 & \textrm{if } n = 0 \vee k = 0 \\
qT_q(n-1, n-1) + T_q(n, n-1) & \textrm{if } n = k > 0 \\
T_q(n, k-1) + T_q(n-1,...
- 4,928
1
vote
0
answers
47
views
Computing the language of an $S$-adic shift
I have been looking online for how or if one can compute the language of an $S$-adic subshift generated by finitely many substitutions. I know that one can compute the language of a substitution ...
- 633
0
votes
0
answers
65
views
Approximating curves using only line sections and arcs
Given a curve $C$, I need to construct another curve $C'$ approximating $C$ under the following constraints: (1) $C'$ needs to be smooth, (2) $C'$ is composed of only line sections and arcs, (3) $C'$ ...
- 367
2
votes
1
answer
141
views
(Sub)Optimality of random transport
Problem Setup: Consider the intervals $I_R = [a_R, b_R]$ and $I_B = [a_B,b_B]$. Let $F_R$ and $F_B$ denote the CDF of distributions with support on the intervals $I_R$ and $I_B$. I draw $k$ red and ...
- 25
3
votes
1
answer
178
views
Algorithm for the sum with binomial coefficients and Bell numbers
Let $a(n)$ be A000110 (i.e., Bell or exponential numbers: number of ways to partition a set of $n$ labeled elements).
Let $b(n)$ be A355247 (i.e., expansion of exponential generating function $\exp(2(\...
- 4,928
5
votes
1
answer
303
views
Efficiently computing $\prod_{i=1}^{n} A_i$
Let $k$ be a nonnegative integer, how to compute $\prod\limits_{i=1}^{n} A_i$ quickly and accurately, where $$A_i=\begin{bmatrix}
0 & 1\\
i^k & 1
\end{bmatrix}?$$
I know if $k=0$, we can use ...
- 696
2
votes
0
answers
95
views
Why cannot we adapt Barvinok type counting techniques to general convex integer programs?
Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program ...
- 13.9k
4
votes
1
answer
175
views
Looking for J.-C. Deville technical report from 2000
Yves Tillé's book Sampling Algorithms mentions several times a technical report by J.-C. Deville:
J.-C. Deville (2000), Note sur l’algorithme de Chen, Dempster et Liu, Tech.
rept. CREST-ENSAI, Rennes....
- 82.6k
4
votes
1
answer
112
views
On a number of compositions of $n$ into positive triangular numbers
Let $a(n)$ be A023361 (i.e., number of compositions of $n$ into positive triangular numbers). Here
$$
a(n) = \sum\limits_{i \geqslant 1, \frac{i(i+1)}{2}\leqslant n} a(n-\frac{i(i+1)}{2}), \\
a(0) = 1....
- 4,928
1
vote
0
answers
121
views
Simple algorithm for A107670
Let $T(n, k)$ be A107670 (i.e., matrix square of triangle A107667). Here we define the triangular matrix $P$ by $P(n, k) = \frac{(n+1)^{2(n-k)}}{(n-k)!}$ for $0 \leqslant k \leqslant n$ and the ...
- 4,928
8
votes
0
answers
260
views
Efficient listing of ASMs
Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is ...
- 17k
4
votes
1
answer
130
views
Intersecting algorithm for A065601
Let $a(n)$ be A065601 (i.e., number of Dyck paths of length $2n$ with exactly $1$ hill). Here
$$
a(n) = \frac{1}{2(n+1)}((3n-2)a(n-1) + 2(9n-19)a(n-2) + 4(2n-3)a(n-3)), \\
a(0) = a(2) = 0, a(1) = 1.
$$...
- 4,928
0
votes
0
answers
82
views
Which proposal distribution should be used in this particular case of the Metropolis-Hastings algorithm?
As part of my research, I would like to apply the Metropolis-Hastings in order to sample from some posterior distribution. More precisely, the data comes from a multivariate normal distribution in the ...
- 49
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
3
votes
0
answers
165
views
Elegant algorithm for A140717
Let $T(n, k)$ be A140717 (i.e., triangle read by rows: $T(n,k)$ is the number of Dyck paths $d$ of semilength $n$ such that sum of peakheights of $d$ - number of peaks of $d$ equals $k$ ($n \geqslant ...
- 4,928
0
votes
1
answer
235
views
Enumerate spanning trees
I am using Pawel Winter's algorithm to enumerate all spanning trees. What I need to do now is enumerate all spanning trees where one edge say e1 remains in the tree and the edge e2 is in e1's ...
- 1
2
votes
0
answers
64
views
On a $\sum\limits_{n=0}^{\infty}c_n x^n=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x^k)$ (slightly different question)
Please note that this question differs from one of the previous questions of mine.
Let $f(n)$ be an arbitrary function with integer values.
Let $c_n$ be an arbitrary integer sequence.
Let $a(n)$ be ...
- 4,928
9
votes
0
answers
258
views
On a continued fraction and vector $\nu$ of length $n$
Please note that this question has been completely reworked in order not to overload it with unnecessary and useless information.
Let $f(n)$ be an arbitrary function with integer values.
Let $a(n)$ ...
- 4,928
1
vote
0
answers
41
views
Unexpected non-uniformity of results from some implementations of Jacobson-Matthews seem to show a strange sensitivity to isotopy class
Questions
Why do some Jacobson-Matthews (J-M) implementations for generating random latin squares exhibit frequencies inconsistent with an underlying uniform distribution?
Further investigation ...
- 41
5
votes
2
answers
189
views
Bisymmetric Hadamard matrices
Definitions: An $n\times n$ Hadamard matrix is a matrix whose entries are either $1$ or $−1$ and whose rows are mutually orthogonal.
A symmetric matrix is a square matrix that is equal to its own ...
- 696
3
votes
1
answer
117
views
How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'
In this paper:
Michael Ben-Or and Prasoon Tiwari. 1988. A deterministic algorithm for sparse multivariate polynomial interpolation, In: Proceedings of the twentieth annual ACM symposium on Theory of ...
- 31
3
votes
1
answer
315
views
About Shor's quantum algorithm
I know very little about quantum computing, and I've been trying to understand Shor's algorithm for the factorization of an integer $N$. I'm following Computational Complexity — a modern approach by ...
- 2,287
2
votes
1
answer
97
views
Is this a satisfiability problem?
Premise:
There are several balls, and each ball has a color.
Each ball is also labeled with either 0 or 1.
These balls are randomly placed in boxes as follows:
...
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214