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,498
questions
2
votes
0
answers
119
views
Ramanujan graphs in Polynomial time
I am a research scholar with a computer science background, currently working on graph theory. I am working on a reduction to prove that a problem is NP-complete. I need to include the Ramanujan graph ...
2
votes
1
answer
136
views
Is there an algorithm to generate non-isomorphic Halin graphs?
A Halin graph is a graph constructed by embedding a tree with no vertex of degree
two in the plane and then adding a cycle to join the tree’s leaves.
We found a list of the number of Halin graphs ...
- 1,209
1
vote
0
answers
103
views
Quadratic equations over Gaussian integers
Given an equation $x^2\equiv(a+ib)\bmod(c+id)$ where $a,b,c,d\in\mathbb Z$ holds, how to test if the equation has solutions and how to find the solutions in polynomial in $\log(|abcd|)$ time if $c+id$ ...
- 13.2k
1
vote
0
answers
51
views
Some question on Lovett-Meka Discrepancy Minimisation Algorithm
I am reading the paper Constructive Discrepancy Minimization by Walking on The Edges
which finds the discrepancy of a set system matching Spencer's bound, in randomised polynomial time. In short, ...
- 150
5
votes
2
answers
191
views
Intersecting permutations
Given a subset $P\subset\mathcal{P}_n$ of the permutations of $1,\dots,n$
Question:
how can a maximal subset $p\subseteq\lbrace1,\dots,n\rbrace$ be determined, whose elements appear in the same ...
- 11.9k
1
vote
0
answers
99
views
Value of $\pi$ and algorithm for Bernoulli numbers
Chowla and Hartung provide an "algorithm" for computing Bernoulli numbers in this paper.
In particular, if the Bernoulli numbers are defined by
$$\frac{x}{e^x-1}=1-\frac{x}{2}+\sum_{n=1}^\...
- 31
0
votes
0
answers
90
views
Computing linear components of a reducible variety
For $i=1,\dotsc,m$ let $f_i$ be polynomials in $k[x_1,\dotsc,x_n]$, where $k$ is some field.
Consider the affine variety $V = V(f_1, \dotsc, f_n)$, i.e. the set of points $x$ such that $f_i(x) = 0$.
$...
- 1,305
0
votes
1
answer
93
views
A variation of Set Cover
Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...
- 1
3
votes
1
answer
162
views
Resultants and elimination theory
Consider an ideal $I = \langle f_1,\dotsc,f_n\rangle$ in the ring $k[x_1,\dotsc,x_m]$.
Define the $i$-th elimination ideal to be $I_i = I \cap k[x_{i+1},\dotsc,x_m]$.
For any two polynomials $f$ and $...
- 1,305
1
vote
0
answers
49
views
Is there any lower bound for basis computation in finite Abelian groups?
Victor Shoup in this paper has given a lower bound for discrete logarithm. The algorithms that I have come across use discrete logarithms (extended discrete logarithms) to compute a basis for a finite ...
- 11
30
votes
3
answers
2k
views
Quickly determining if a matrix has any PSD completion
Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?
Slightly more precisely: for simplicity let's assume ...
- 727
0
votes
0
answers
116
views
A question about Jacob Fox's graph removal lemma
I have a question about the paper "A new proof of the graph removal lemma" by Jacob Fox.
I will preface this by saying I've looked around in papers citing this paper and couldn't find an ...
2
votes
0
answers
60
views
Is 'weak' Strassen Conjecture true?
$\newcommand{\rank}{\mathop{\mathrm{rank}}}$Strassen conjectured for two tensors $T_{1}$ and $T_{2}$, $\rank(T_{1}\oplus T_{2})=\rank(T_{1})+\rank(T_{2})$. This is not generally true according to ...
- 21
5
votes
0
answers
104
views
Finding an $\mathbb{F}_q$-point on one specific intersection of quadrics
Let $\mathbb{F}_q$ be a finite field of large characteristic and $a_1, a_2, \cdots, a_n \in \mathbb{F}_q$ be some pairwise different elements. I assume that $\sqrt{-1} \in \mathbb{F}_q$. Consider the ...
- 1,699
1
vote
1
answer
39
views
Algorithmic complexity of calculating maximum weight $k$-regular subgraphs
Question:
what is known about the complexity of calculating the heaviest $k$-regular subgraph of a weighted symmetric graph if edge-weights can also be negative?
Please note that in contrast to $k$-...
- 11.9k
3
votes
1
answer
134
views
Fastest algorithm for calculating optimal tours in weighted $K_5$
Weighted $K_5$ have the unique property that their edge set can be interpreted as the disjoint union of their shortest and their longest Hamilton cycle.
That makes $K_5$ attractive for designing new ...
- 11.9k
0
votes
0
answers
39
views
Ride sharing problem in GAMS
In this problem, we have a weighted and directed graph, where each node represents a certain place to determine the origin of the driver and the origin and destination of the passengers. In the real ...
0
votes
0
answers
63
views
Decompose directed graph into many cycles
Given is a directed graph $G$, possibly with self-loops or parallel edges, such that each vertex has the same in-degree as out-degree. I would like to decompose it into as many directed cycles as ...
- 143
0
votes
0
answers
77
views
Finding the representative of an element inside a subfield
I'm looking for an efficient algorithm to find the representative of an element inside a subfield that's isomorphic to its multiplicative group. I have a finite field $F_{p^{nm}}$ with an element $g$ ...
- 1
2
votes
2
answers
806
views
Using Kolmogorov complexity to measure difficulty of problems?
We call the natural number $n$ a partition number $\iff$
$$\exists d | n: \gcd(d,\frac{n}{d})=1 \text{ and } \Omega(d) = \Omega(\frac{n}{d})$$,
where $\Omega$ counts the prime divisors with ...
- 1,819
0
votes
0
answers
25
views
Approximation algorithm for non-infinite diameter of sparse directed graph
There are some good approximation algorithms that compute the diameter of a sparse directed graph, for example, this one.
Consider a little variation of the definition of diameter: we rule out ...
1
vote
1
answer
51
views
Computing admissible patches of a substitution
I have been recently trying to look at substitution tilings with finite local complexity by examining their admissible patch\pattern atlas, which is sometimes called their language. I have also seen ...
- 357
1
vote
0
answers
75
views
Convex optimization with one-point feedback
In an adversarial bandit setting, we want to minimize $\sum_{1}^{T}l_t$(not exactly this but the corresponding regret), where $l_t$ is the loss function in the $t-$th round. Each round we can specify ...
- 21
0
votes
0
answers
33
views
Large sum of determinants of Hadamard products
We have $n$ by $n$ matrices $A$, $C$ and $S$ over a finite field $\mathbb{F}_q$. The $C$ is invertible of order $m$ as an element of $GL(\mathbb{F}_q,n)$.
Is there an algorithm, polynomial in $n$, ...
- 3,011
2
votes
1
answer
152
views
Is there an efficient algorithm that allows to construct a binary word with particular properties related to its horizontal and vertical “subwords”?
Let $w$ denote an $mn$-bit word (i.e. a binary word of length $mn$). Assuming that $b_{i,j}$ denote individual bits, we can represent $w$ in the “rectangular” form as follows:
$$\begin{array}{l}
b_{1....
- 899
0
votes
0
answers
156
views
The meaning of random number generator test failing
I have a random number generator (number theoretic) that passes all of the NIST tests except the random excursions test. Is there any deep dark meaning to this? To amplify "deep dark meaning"...
- 94.7k
1
vote
1
answer
94
views
Algorithm for finding integers in a range with multiples in a short interval
Is there a quick way to determine which integers $D < d\leqslant 2D$ are such that $d$ has a multiple in $[X, X + H]$? Here, $H$ should be thought of as much smaller than $D$, and $X$ larger than $...
- 1,759
2
votes
1
answer
55
views
Generating a random matrix with large spark (i.e., each $k$-tuple of columns is linearly independent)
Let $F$ be a field, and let $m, n, k$ be positive integers. Is there an efficient algorithm to compute a uniformly random $m \times n$ matrix $A$ over $k$ such that each $k$-tuple of columns of $A$ is ...
- 21
3
votes
0
answers
59
views
Does this information theoretical thought experiment have a name or corresponding area of research?
I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
- 479
5
votes
1
answer
239
views
Counting points above lines
Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...
- 18.6k
5
votes
0
answers
156
views
Computing sums with linear conditions quickly
Let $f:\{1,\dotsc,N\}\to \mathbb{C}$, $\beta:\{1,\dotsc,N\}\to [0,1]$ be given by tables (or, what is basically the same, assume their values can be computed in constant time). For $0\leq \gamma_0\leq ...
- 18.6k
0
votes
0
answers
28
views
vertices with least distance to subset of other vertices - Undirected Graph
Given an undirected graph $G=(V,E)$ where $V=\{v_1,v_2,...,v_n\}$ denotes the vertices and $E=\{e_1,e_2,...,e_m\}$ denotes edges. Moreover, there exists a nonnegative weight associated with each edge.
...
- 1
1
vote
0
answers
30
views
Convergent gradient-type scheme for solving smooth nonconvex constrained optimization problem
Let $x_1,\ldots,x_n \in \mathbb R^d$ and $y_1,\ldots,y_n \in \{\pm 1\}$, and $\epsilon, h \gt 0$. Define $\theta(t) := Q((t-\epsilon)/h)$, where $Q(z) := \int_{z}^\infty \phi (z)\mathrm{d}z$ is the ...
- 6,338
0
votes
0
answers
92
views
An unnamed (perhaps?) graph theory problem
We create a graph weighted $G_0$ given a set of nodes and a function $f(v_x, v_y, G_i) $ that calculates the edge weight between the nodes within $G_0$ that's dependent on the global graph structure. ...
0
votes
0
answers
119
views
Difference set of difference set II (special Golomb rulers)
In
Difference set of difference set
I asked if a certain set is possible. And if O(n²) as the maximum integer-value in the set would be possible. User Emil Jeřábek (sorry dont know how to put a user-...
- 63
0
votes
2
answers
99
views
Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)
Given a weighted directed acyclic graph (DAG) $G=(V,E)$ with each edge $e\in E$ has a non-negative weight $w(e)$. For a path $p=(e_1,e_2,\dotsc,e_n)$ in $G$, define the path weight as : $w(p)=\sum_{i=...
- 143
7
votes
1
answer
247
views
Alternate algorithms for Chinese remainder theorem
I was teaching Discrete this semester and set the students loose on a system of linear congruences. One of them came up with this solution. Say $$ x \equiv 1 \textrm{ mod } 3 $$ $$ x \equiv 3 \textrm{ ...
- 455
0
votes
0
answers
136
views
Impact of the global cost function (weighting) to Betweenness Centrality distribution
I have a graph whose edges have all a weight of 1. In my particular case computing the Betweenness centrality by counting shortest paths between all pairs results ...
- 419
2
votes
0
answers
78
views
Solving efficiently a quadratic equation in a large finite field of characteristic two
I'm trying to solve efficiently a quadratic equation in the finite field $\text{GF}(2^{128})$ represented as $(\mathbb{Z}/2\mathbb{Z})[x] / (x^{128} + x^7 + x^2 + x + 1)$.
Until now, I came across ...
- 21
1
vote
1
answer
82
views
Finding $k$ active elements by evaluating the "any-operator" of subsets of variables
Assume a set $S$ of elements $\{s_1,\dots,s_n\}$, each which has a hidden label 'active' or 'inactive'. Assume there are $m\ll n$ active elements in total. You are allowed to iteratively perform a ...
0
votes
1
answer
26
views
Edge-length constraints from greedy matching
The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices.
The objective is to ...
- 11.9k
3
votes
1
answer
245
views
How to find the maximum of a sum of squares of sums?
Is there any better than a brute force method for finding the maximum
$$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...
user494931
3
votes
0
answers
322
views
Is this FFT algorithm known?
Recently I've been thinking about alternatives to the usual Cooley-Tukey FFT for multiplying polynomials. I think I've come up with a pretty nifty algorithm for multiplying polynomials. So my question ...
- 31
1
vote
2
answers
188
views
Do all graphs with $n$ vertices and $m$ edges have a special property?
Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.
For which values of $n$ and $m$ does the following requirement hold:
$\forall G \in \...
- 234
2
votes
1
answer
99
views
Algorithm for finding a minimum weight circuit in a weighted binary matroid
For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...
- 23
1
vote
2
answers
213
views
Method to solve system of exponential sums of the form $a^x+b^x=c$ given more equations than variables [closed]
Cross post with mse
For example, let's say I have the following equations.
\begin{gather*}
a^{x-1}+b^{x-1}=337 \\
a^{x}+b^{x}=1267 \\
a^{x+1}+b^{x+1}=4825 \\
a^{x+2}+b^{x+2}=18751.
\end{gather*}
What ...
- 13
3
votes
0
answers
80
views
Checking the generic rank of a matrix
Suppose that $A,B\in M_{p,q}(\mathbb{Z})$ are two rectangular integer matrices of the same size. Suppose that one has a conjecture stating that the rank of the matrix $A+tB$ for Zariski generic values ...
- 15.7k
0
votes
0
answers
44
views
State-of-the-art for approximating the Cheeger constant (for graphs)
What is the state-of-the-art algorithm for approximating the Cheeger constant, given a regular graph? Ideally, such an algorithm would run in polynomial time (in the size of the graph, and could be ...
- 455
2
votes
0
answers
126
views
On GCD and lattice reduction
$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$.
Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector.
If $GCD$ is in $NC$ and in ...
- 13.2k
4
votes
0
answers
89
views
Lattice reduction of basis with non-integer coefficients
Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$.
I would like to perform lattice ...
- 554