All Questions
637 questions with no upvoted or accepted answers
28
votes
0
answers
907
views
On certain representations of algebraic numbers in terms of trigonometric functions
Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...
- 6,819
18
votes
0
answers
579
views
What is the geometric intuition behind Wilf-Zeilberger theory?
This problem is somehow inspired by a bunch of impressive posts of combinatorial identities by T. Amdeberhan. Earlier this month I learnt from computer scientists that they have a generic algorithmic ...
- 8,071
15
votes
0
answers
448
views
Best known constant for parallel sorting
I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because ...
- 29k
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
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
12
votes
0
answers
167
views
Are there efficient algorithms to factorise in $\mathbb{N}[X]$?
One way to do factorisation in $\mathbb{N}[X]$ is to use an algorithm to factorise in $\mathbb{Z}[X]$ and then to combine some factor to find a factorisation in $\mathbb{N}[X]$. Note that the ...
- 329
12
votes
0
answers
1k
views
Shortest path in Cayley graphs
The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...
- 121
12
votes
0
answers
349
views
Matroids with prescribed independent sets
Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
- 1,791
11
votes
0
answers
764
views
Fast computation of matrix product $AXA^T$ with fixed $A$?
Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...
- 75
10
votes
0
answers
453
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
- 1,677
10
votes
0
answers
722
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
- 109k
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
9
votes
0
answers
381
views
Explicit construction of the Jacobian of a curve
Let $k$ be an algebraically closed field (of arbitrary characteristic), and $C$ a smooth projective curve over $k$, given by defining equations in projective space. I am looking for an algorithmic ...
- 91
9
votes
0
answers
534
views
Generating $S_n$ with a fundamental transposition and a big cycle
I apologize in advance if this is too amateur, this is not really my area, but I'm very curious.
We have a permutation $\pi \in S_n$ and we want to represent it as a product of $\sigma = (1\;2)$ and $...
- 231
9
votes
0
answers
275
views
Complete list of exceptions and efficient algorithm for Waring's problem
2 weeks ago, Samir Siksek https://arxiv.org/abs/1505.00647 proved the more than 150-years-old conjecture that every positive integer other than 15, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, ...
- 91
9
votes
0
answers
339
views
Is it decidable whether a finite type scheme is proper?
Let $k$ be a field and let $X$ be a finite type scheme over $k$, explicitly given by finitely many affine patches which are $\mathrm{Spec}$ of finitely generated $k$-algebras, glued along other affine ...
- 156k
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
8
votes
0
answers
178
views
Usable Implementations to decide the existential theory of the reals
I guess many have heard of the existential theory of the reals:
https://en.wikipedia.org/wiki/Existential_theory_of_the_reals
I have read in various papers that the problem lies in PSPACE. I have ...
- 479
8
votes
0
answers
239
views
Computing the Moebius function $\mu$
Is it known whether computing $\mu(n)$ for a given integer $n$ is as hard as factorization?
- 20.2k
8
votes
0
answers
225
views
Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?
Landau's function
$g(n)$ is the largest order of an element of the symmetric group $S_n$.
Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$.
In general $g(n)$ is ...
- 25.4k
8
votes
0
answers
178
views
Naive Reidemeister-Schreier for $\mathbb Z$ quotients
I have a question about a "standard" variant of the Reidemeister-Schreier algorithm used by topologists when manipulating manifolds they either know or suspect are fibre-bundles over $S^1$.
Say you ...
- 44.3k
8
votes
0
answers
1k
views
Infinite Linear Programming
I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
- 133
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k
7
votes
0
answers
226
views
Could a quantum computer factor $N=p\times q$ using Hadamard transforms on $x^2\bmod N$ (instead of Fourier transforms on $a^x\bmod N$)?
In Classically verifiable quantum advantage from a computational Bell test, Kahanamoku-Meyer, Choi, Vazirani, and Yao propose using $x^2 \bmod N$ in an interactive proof-of-quantumness. This is a two-...
- 2,185
7
votes
0
answers
161
views
Is there an algorithm to determine if there exists a dominant map between two curves?
Suppose I am given two smooth projective curves $C_1$ and $C_2$ over a field $k$ I want to know if there is an algorithm to decide whether there exists a nonconstant (and thus dominant) map $f : C_1 \...
- 3,625
7
votes
0
answers
372
views
"Factorisation" in special linear groups over rings of integers
It is known that for any number field $F$ with infinitely many units (i.e. $F$ is not $\mathbb Q$ or an imaginary quadratic field) with ring of integers $O$ the special linear group $\mathrm{SL}_2(O)$ ...
- 3,399
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
7
votes
0
answers
186
views
How quickly can we test if a graph is distance-regular?
A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...
- 37.7k
6
votes
0
answers
65
views
Vertex cover in bipartite graphs with bounds on cost and size
Suppose we have a bipartite graph $G$ with non-negative integer vertex costs. We would like to find a vertex cover of cost at most $C$ and size (number of vertices) at most $S$, where $C$ and $S$ are ...
- 96
6
votes
0
answers
197
views
Where to cut off a double sum?
I have to compute a double infinite sum to within a given accuracy $\epsilon$. Let us say the sum is of the form
$$\sum_{m\geq 1} \sum_{n\geq 1} \frac{a_{m,n}}{m^2 n^2 \max(m,n)},$$
where $|a_{m,n}|\...
- 20.2k
6
votes
0
answers
105
views
Computing the zeta transform of a Boolean function: Space-time tradeoff
Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by
$$\zeta_f(y) :...
- 71
6
votes
0
answers
618
views
Detect cycle in graph in logspace and linear time?
Let's consider graphs of bounded degree.
I know that it's possible to detect cycles in a graph in linear time -- essentially do a depth-first search, depositing a trail along the path you're currently ...
- 2,519
6
votes
1
answer
534
views
How to find the Eulerian circuit with the minimum accumulative angular distance within an Eulerian graph?
Note: I originally posed this question to Mathematics, but it was recommended that I try here as well.
Context
For context, this problem is part of my attempt to determine the path of least inertia ...
- 161
6
votes
0
answers
206
views
Longest string with all unique substrings
All substrings of length 2 of the binary string $1011$ are unique, as well as all 2-substrings of $10011$. 5 seems to be the longest possible string with all unique 2-substring.
$000101100$ is a ...
- 343
6
votes
0
answers
180
views
Shortest vector problem with a null vector constraint
Take $\mathbb{Z}^n$ equipped with two symmetric bilinear forms, one positive-definite $(\cdot,\cdot)_A : \mathbb{Z}^n \times \mathbb{Z}^n \to \mathbb{R}$ and one indefinite $(\cdot,\cdot)_J : \mathbb{...
- 271
6
votes
0
answers
212
views
Solving polynomial equations modulo $1$
Let $P\in \mathbb{R}\lbrack x\rbrack$ be given. (In practice, the coefficients could be given as, say, decimals to sufficient precision.) Let $M\geq 1$, and let $I$ be an interval in $\mathbb{R}/\...
- 20.2k
6
votes
0
answers
91
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 $$s(g):=\sum_{...
- 14.6k
6
votes
0
answers
434
views
Algorithm to express a point from a H-polyhedron as convex combination of extreme points
Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is,
$$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$
Let $\boldsymbol{x} \in P$. We ...
- 617
6
votes
0
answers
69
views
Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time
A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...
- 37.7k
6
votes
0
answers
97
views
Finding the optimal mixture of two convex functions
I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
6
votes
0
answers
315
views
Algorithms for computing the Resilience of Graphs
The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...
- 903
6
votes
0
answers
172
views
Uniformly sampling from the set of all simplicial maps
Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial maps ...
- 15.5k
6
votes
0
answers
317
views
Variant of orthogonal Procrustes problem
The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
- 61
6
votes
0
answers
316
views
Testing isomorphism of finitely generated algebras
Let $A=\mathbf{Q}[x_1,\ldots,x_n]$ be the polynomial ring in $n$ variables over the rational numbers. Let $B=\mathbf{Q}[f_1,\ldots,f_r]$ and
$C=\mathbf{Q}[g_1,\ldots,g_s]$ be two finitely generated $\...
- 7,609
5
votes
0
answers
121
views
Recovering a binary function on a lattice by studying its sum along closed walks
I recently posted this question on MSE. While it attracted interest, no answers were submitted, so I thought to try and post it here.
I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While ...
- 251
5
votes
0
answers
155
views
A non-trivial (not a concatenation of de Bruijn sequences) infinite binary sequence whose initial $2^{n+1}$ bits contain all $n$-bit words for any $n$
Does there exist an infinite binary sequence $B$ that satisfies all of the following three properties?
It is possible to prove that for any integer $n$ the initial $2^{n+1}$ bits of $B$ contain all $...
- 959
5
votes
0
answers
129
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,833
5
votes
0
answers
167
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 ...
- 20.2k
5
votes
0
answers
215
views
Integer points of rational function in 2 variables
Is there an algorithm that, given polynomials $P(x)$ and $Q(y)$ with integer coefficients, decides whether there exists integers $x$ and $y$ such that $\frac{P(x)}{Q(y)}$ is an integer?
This is a ...
- 7,182
5
votes
0
answers
107
views
Heuristics for the word problem for monoids
The question is about a purely practical problem:
Given is a list of identities, as in http://www.findstat.org/MapsDatabase/Mp00069:
...
- 5,822