# Tagged Questions

**3**

votes

**0**answers

22 views

### Complexity of OBDD isomorphism (representing same function after permutation of variables)?

According to wikipedia Ordered Binary Decision Diagarams (OBDD) are a data structure that is used to represent a Boolean function.
OBDD is a DAG with two sinks $0,1$.
The size of the BDD is number ...

**11**

votes

**1**answer

686 views

### Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned:
'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...

**2**

votes

**0**answers

60 views

### Blossoms and Colorings

There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...

**3**

votes

**0**answers

83 views

### Algorithm for finding the fewest cartesian products to partition a set of points

The question Algorithm for finding the fewest rectangles to cover a set of rectangles was already answered here and a similar question was answered here. Those questions were about regular geometric ...

**1**

vote

**1**answer

42 views

### Test Instances for Perfect Matchings in Graphs

Are there any graphs with a known set of perfect matchings and other predefined properties, such as vertex connectivity, which can be used for testing the implementation of matching algorithms?
...

**3**

votes

**0**answers

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

**3**

votes

**2**answers

192 views

### Bellman-Ford for Matching Problems?

I am looking for a simple way of calculating minimum-weight perfect matchings in complete graphs with an even number of vertices.
I know that there are implementations that are based on Edmond's ...

**1**

vote

**1**answer

73 views

### What is the relation between size of maximum clique and branchwidth?

Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds:
$$
\omega(G)\leq bw(G)
$$
Intuition: Assume (in reverse of ...

**9**

votes

**1**answer

669 views

### Some Questions on the Collatz conjecture

The set of all positive whole numbers is denoted by $\mathbb{N}_+$.
Let $f\colon\ \mathbb{N}_+\to\mathbb{N}_+:n\mapsto
\begin{cases}\frac{n}{2}&\text{$n$ even}\\3n+1&\text{$n$ ...

**1**

vote

**0**answers

63 views

### Does Coppersmith's method always finds non-trivial factor of integers of the form $n=a(2^k b+1)$ assuming $1 < a<2^k b +1$ and $b < n^{1/4-0.05}$?

Got an argument and numeric evidence that pari's implementation
of Coppersmith's method finds non trivial factor of integers
of certain form under some assumptions very efficiently.
Three $5000$ bit ...

**1**

vote

**0**answers

73 views

### Grobner basis for a general algebra

Let $R$ be a quotient of the polynomial ring $\mathbb{C}[x_1,\dots , x_n]$. We fix a $\mathbb{C}^*$ action on $R$ which preserve homogenous components and the multiplication. (The geometric analogue ...

**6**

votes

**1**answer

117 views

### Algorithm that solves every Mixed Integer Linear Program (to optimality)?

Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?
I know that you usually ...

**6**

votes

**0**answers

73 views

### Correlation of Class Functions

Let $G$ be a finite group, and let $f_1,f_2$ be two real-valued class functions of $G$. Assume that multiplying elements of $G$ takes $O(1)$-time.
Let $s:G\to \mathbb{R}$ be defined by ...

**0**

votes

**0**answers

25 views

### Monotonicity per dimension of multivariate scattered data

For my thesis, I am working on interpolation using the RBF method (Radial Basis Functions). Before interpolating, I want some a priori insight into the data, for example check in which dimensions it ...

**4**

votes

**2**answers

161 views

### Extraction of Coefficients in the Exponential Function of a Series

Question: Let $f(x) \in x\mathbb{C}[[x]]$. What is the (asymptotically) fastest algorithm for calculating the coefficient of $x^n$ in $e^{f(x)}$?
Naive Solution 1: Using fast polynomial ...

**6**

votes

**1**answer

267 views

### G-Correlation of Vectors

Let $\vec{a},\vec{b} \in \mathbb{R}^{n}$. Consider the function $f: S_n \to \mathbb{R}$ given by $f(\sigma):= \sum_{i=1}^{n} a_i b_{\sigma(i)}$. Let $G$ be a subgroup of $S_n$, given by $O(\log n)$ ...

**3**

votes

**1**answer

212 views

### Algorithm to count the number of perfect matchings in non planar graph

I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...

**4**

votes

**0**answers

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

**-1**

votes

**1**answer

86 views

### Is there an algorithm to find a linear dependence between points on elliptic curves?

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_p$ of characteristic $p$. Let $P,Q\in E(\mathbb{F}_q)$, such that $Q=mP+n\tau(P)$, where $\tau$ is the p-th power of frobenious map and $m$ ...

**2**

votes

**1**answer

78 views

### Seeking for abelian subalgebra of fixed dimension in finite Lie algebra

The problem is: I want to know if there is abelian subalgebra of dimension $k$ in Lie algebra of dimension $n$. My Lie algebra is given by its structure constant table. There are some algorithms ...

**1**

vote

**2**answers

107 views

### The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...

**11**

votes

**1**answer

305 views

### Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?

This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route ...

**1**

vote

**0**answers

23 views

### Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph.
I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...

**2**

votes

**2**answers

208 views

### $k$-th subset in order of increasing sum

I have an array of integers T[N] indexed from 1. For example T[1] = 1, T[2] = 4, T[3] = 5, T[4] = 9. Let's enumerate all subsets of this set in a certain order: increasing sum of the elements. In case ...

**3**

votes

**2**answers

114 views

### Computing digits of irrational exponentiation

Let us have positive irrational numbers $a$ and $b$ represented by functions $f_a,f_b\colon\mathbb{N}\to\mathbb{N}$ respectively such that $f_a(0)=\left \lfloor{a}\right \rfloor$ and $f_a(i)$, ...

**1**

vote

**0**answers

72 views

### Algorithm to generate hyperbolic metric on a compact surface

Let $F$ be a compact surface of genus $g$ with generators $a_1,b_1,\ldots ,a_g,b_g$ with relation $[a_1,b_1]\cdots [a_g,b_g]=1$. We can also consider surfaces with boundary in which case the ...

**1**

vote

**3**answers

265 views

### Finding integer representation as difference of two triangular numbers

Since $n = \frac{n(n+1)}{2}-\frac{n(n-1)}{2}$, every natural number can be represented as the difference of two triangular numbers:
$ n = \frac{a(a+1)}{2}-\frac{b(b-1)}{2}$. Finding such a ...

**4**

votes

**0**answers

370 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=$ ...

**5**

votes

**1**answer

56 views

### Two fold optimization: is there an established approach for this kind of problem?

I have a list of thousands of linear expressions, with less than 100 total variables. Each expression is associated with a positive point value. I want to make as many of the expressions greater than ...

**5**

votes

**1**answer

172 views

### Is this subset-sum-type problem discussed in the literature?

Let $y \in \mathbb{Z}_+^n$, with $y_1 < \dots < y_n$. I am interested in finding a 0-1 matrix $A$ and $x \in \mathbb{Z}_+^m$ s.t. $m$ is minimal and $Ax = y$, where I am guaranteed that at least ...

**3**

votes

**2**answers

73 views

### Is there an algorithm for generating sets of routes that satisfy edge volume constraints?

I have reduced a problem I'm working on to something resembling a graph theory problem, and my limited intuition tells me that it's not so esoteric that only I could have ever considered it. I'm ...

**2**

votes

**0**answers

203 views

### Avoiding Chinese Remainder Theorem

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...

**7**

votes

**1**answer

264 views

### State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are ...

**1**

vote

**2**answers

65 views

### Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...

**8**

votes

**1**answer

694 views

### Doob Martingale: Where is the catch?

I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support.
I am attempting to use the method of bounded ...

**2**

votes

**1**answer

100 views

### Parallel algorithm for modular multiplication of polynomials over Z/nZ

Is there a parallel algorithm for doing modular multiplication of polynomials over Z/nZ? n is a very large number (for hundreds and thousands of bits).
Normally, the method used is binary ...

**0**

votes

**0**answers

107 views

### Systems of linear modular equations with unknowns in the moduli

I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be:
$A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$
where A ...

**4**

votes

**1**answer

266 views

### Listing all solutions to $n = x^2 + y^2 + z^2 $ with integers

I would like to list all ways of writing $n$ as the sum of 3 squares. This is slightly different from finding just one:
Is there an algorithm for writing a number as a sum of three squares?
...

**2**

votes

**1**answer

97 views

### Asymptotic upper bound for recursive function $f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$

I'm looking for an asymptotic upper bound for the function f(x), which is recursively defined as follows: $$f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$$
with $f(1)=1$. I am pretty ...

**3**

votes

**1**answer

115 views

### Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...

**7**

votes

**3**answers

242 views

### Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**2**

votes

**0**answers

81 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$ ...

**9**

votes

**3**answers

500 views

### Is the Number of Carries in Integer-Addition Associative?

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions ...

**2**

votes

**0**answers

92 views

### Worst case performance of a simple averaging algorithm

Let $u_1,\ldots,u_n$ be a sequence of rationals with finite binary expansion.
Consider the following simple averaging algorithm:
while the sequence is not monotone increasing, pick $i$ with ...

**0**

votes

**0**answers

48 views

### Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include:
All vectors in $S$
All vectors in $T$
All vectors that can be ...

**7**

votes

**2**answers

454 views

### What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in ...

**1**

vote

**0**answers

235 views

### Reduction to some physical interpretation of this formula

Problem Given N 3-dimensional points which are {$p_1,p_2,..,p_n$} where $p_i = (x_i,y_i,z_i) $ . I have to find the value of the formula
$$ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n \frac{ \mid ...

**2**

votes

**0**answers

38 views

### Algorithm to get lower peak of bimodal histogram [closed]

I have a set of data, when tabulated in histogram, it looks like bimodal histogram.
With naked eyes, we can see the value for lower peak is about -1.35, however, what algorithm I can use to ...

**3**

votes

**3**answers

136 views

### Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...

**2**

votes

**1**answer

109 views

### Mestre-type algorithm for higher-genus curves?

Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...