The algorithms tag has no wiki summary.

**22**

votes

**0**answers

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

**20**

votes

**0**answers

383 views

### Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them.
Define the set $\mathcal{E}$ of ...

**13**

votes

**0**answers

2k 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?

**12**

votes

**0**answers

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

**11**

votes

**0**answers

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

**9**

votes

**0**answers

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

**8**

votes

**0**answers

131 views

### Complete list of exceptions and efficient algorithm for Waring's problem

2 weeks ago, Samir Siksek http://arxiv.org/abs/1505.00647 proved more than 150-years-old conjecture that every positive integer other than 15, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, 303, ...

**8**

votes

**0**answers

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

**8**

votes

**0**answers

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

**8**

votes

**0**answers

597 views

### Recent Fast Multiplication Algorithms for Large Integers

The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al
http://arxiv.org/abs/0801.1416 shows how to use $p$-adic numbers instead of $\mathbb C$ used in Furer's ...

**8**

votes

**0**answers

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

**7**

votes

**0**answers

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

**7**

votes

**0**answers

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

**7**

votes

**0**answers

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

**6**

votes

**0**answers

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

**6**

votes

**0**answers

600 views

### Is Logical Min-Cut Problem, NP-Complete?

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...

**5**

votes

**0**answers

160 views

### Is there a reasoned derivation of the coherence conditions for symmetric rig categories?

I know what the coherence conditions are, I can look them up in
M. Laplaza, Coherence for distributivity, Lecture Notes in Mathematics 281, Springer Verlag, Berlin, 1972, pp. 29-72.
In theory, ...

**5**

votes

**0**answers

205 views

### When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...

**5**

votes

**0**answers

202 views

### Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty).
For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$.
Given some $1\leq s < d$, consider ...

**5**

votes

**0**answers

212 views

### Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...

**5**

votes

**0**answers

171 views

### Differential operators that preserve real-rootedness

Is there some description of polynomial differential operators, $\mathcal{D}=\sum f_i(x) D_x^i$ such that, if $h$ is a polynomial all of whose roots are in $[0,1]$, then so are all the roots of ...

**5**

votes

**0**answers

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

**4**

votes

**0**answers

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

**4**

votes

**0**answers

167 views

### What is the complexity of intersecting two matrix algebras over a finite field?

The following question arose in a joint project with Arkadius Kalka and Adi Ben-Zvi.
Let $\mathbb{F}$ be a finite field, and $M_n(\mathbb{F})$ be the $n\times n$ matrices over $\mathbb{F}$.
For a ...

**4**

votes

**0**answers

143 views

### What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...

**4**

votes

**0**answers

194 views

### Navigation in a graph

The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...

**4**

votes

**0**answers

123 views

### A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...

**4**

votes

**0**answers

106 views

### Generating random weak k-bounded reverse plane partitions

Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that ...

**4**

votes

**0**answers

178 views

### Comparing different Euclidean algorithms on a Euclidean domain

I have posted this question at stackexchange (502413), without responses until now.
In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About ...

**4**

votes

**0**answers

170 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**4**

votes

**0**answers

306 views

### Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.
It ...

**4**

votes

**0**answers

301 views

### Matching a binary matrix

Given a MxN 0-1 matrix D, with the property that
both M and N are odd numbers
its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).
How do we find M ...

**4**

votes

**0**answers

218 views

### Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...

**4**

votes

**0**answers

306 views

### Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times ...

**3**

votes

**0**answers

225 views

### What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...

**3**

votes

**0**answers

92 views

### Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...

**3**

votes

**0**answers

113 views

### Recognizing Simplicial (Quasi)Fibrations

Let's say we are given two finite simplicial complexes, which I will suggestively call $E$ and $B$. We'd like an algorithm for the following decision problem:
Does there exist a simplicial map ...

**3**

votes

**0**answers

147 views

### Algorithm to compute a common denominator of a finite set of rational numbers

Let $x_1,\dots,x_n \in \mathbb{Q} \cap (0,1)$ be fixed, but unknown, and assume that we know a number $K \in \mathbb{N}$ such that there is a number $N \in \{1,\dots,K\}$ such that $x_1 N,\dots,x_n N ...

**3**

votes

**0**answers

45 views

### Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be ...

**3**

votes

**0**answers

151 views

### What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...

**3**

votes

**0**answers

132 views

### On understanding Discrete-Valued Stochastic Processes( time series, panel data )

It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...

**3**

votes

**0**answers

214 views

### Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...

**3**

votes

**0**answers

234 views

### (Co)limit computations for diagrams of Vector Spaces

Fix a field $K$ and consider a finite directed graph $\Gamma$ where multiple edges between a pair of vertices are allowed so long as the total number of edges is finite. Associate to each vertex $v$ a ...

**3**

votes

**0**answers

270 views

### 3-SAT and a matrix of linear forms representing a non-degenerate matrix

This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.
As before, let $k$ be a field with $p$ elements. Consider the ...

**3**

votes

**0**answers

134 views

### A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello,
What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain
$E = \{1,...,n\}$
and a partial function
$f: E^3 \to \{-1, 0, 1\}$
...

**3**

votes

**0**answers

301 views

### Amortized analysis of data structure via potential function

One common method for proving that a data structure supports an operation in $O(f(n))$ amortized time is to construct a potential function $\Phi: \mathcal S \rightarrow \mathbf R^{+}$, which ...

**3**

votes

**0**answers

227 views

### Implementation for computing Shintani domains

By "Shintani domain", I mean a fundamental domain for the action of the totally positive units of a totally real number field k with $[k \colon \mathbb{Q}]=n$ (or more generally, those congruent to 1 ...

**3**

votes

**0**answers

494 views

### Covering the integers by two kinds of three-element sets (IMO Shortlist 2001 problem C4): extensions and generalizations?

As a straightforward generalization of IMO Shortlist 2001 problem C4, we can show the following fact:
Let $u$ and $v$ be two positive integers. A set of three integers $\left\lbrace ...

**3**

votes

**0**answers

198 views

### Algorithm for testing satisfiable fraction of linear equations mod 2

Hello
Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation ...

**3**

votes

**0**answers

318 views

### example just slightly better than the greedy construction

Roth's theorem provides an estimate for the largest
size of a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ (a set of integers is nonaveraging if it does not contain any nontrivial ...