The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
20 views

Minimal rectangular confidence regions

For a given multivariate pdf $f$ (mainly the gaussian one) I'm looking to compute a minimal rectangular confidence region for a given level $\alpha$. For example, I would like to solve problems of the ...
1
vote
0answers
147 views

Is finding a single vector in the null space as difficult as discovering the whole null space?

Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is: Is the ...
7
votes
1answer
594 views

Can the Legendre symbol be calculated in polynomial time?

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...
6
votes
1answer
240 views

Shortcut from discrete Fourier transform F{x} to zero-padded F{x:0…0}

Summary: Given $X$ (the discrete Fourier transform of some unknown vector $x$ of length $N$), is there any shortcut to computing $X'$ (the Fourier transform of $x$ after padding it with $N$ zeros)? ...
2
votes
2answers
92 views

Sampling from maximally skewed stable distribution

I am reading a paper which refers to a maximally skewed stable distribution $F(x;1,-1,\pi/2,0)$ . Is there an efficient way to sample from this distribution? If $X$ has distribution ...
1
vote
1answer
35 views

How to select a subset of points from a universal to minimize the distance from outside to inside?

Here is the detailed problem. I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as $$ ...
6
votes
1answer
238 views

Fast construction of straight line programs?

Given a group $G$ and a set of generators $A$, we can ask ourselves (and do ask ourselves all the time) to bound the diameter of $G$ with respect to $A$. The diameter, let us recall, is defined to be ...
17
votes
0answers
157 views

A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph? I'd like to avoid exhaustive ...
1
vote
1answer
48 views

Heuristic for choosing n-vectors from n-sets

my given problem is: choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
4
votes
0answers
96 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 ...
10
votes
1answer
299 views

Explicit algorithm for composing permutations in factorial notation

Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line ...
2
votes
1answer
121 views

Galois Connections: algorithmic generation

Given two finite posets $P,Q$, is it known any algorithm to count and/or generate every Galois Connection between $P$ and $Q$ ? I'm looking for references about this problem.
3
votes
2answers
130 views

All Integers from the Smallest Digit Stream with a Window Filter

Let's represent integers with D digits where each digit has B values (i.e., the base is B and we effectively work only with integers between 1 and B^D). Is it possible to choose a single ...
8
votes
3answers
522 views

Changing combination lock [closed]

Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific n-digit key sequence. However, trying a wrong key changes it according to an fixed but unknown function: new ...
35
votes
1answer
1k views

improving known bounds for Pierce expansions; cash prize

Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have ...
3
votes
1answer
195 views

Generalization of notion of convexity

I am searching for the correct term for the following, if it exists. A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius ...
2
votes
0answers
71 views

Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...
3
votes
1answer
111 views

A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not. The new problem is this. There is a tourist who has a having the following ...
5
votes
1answer
151 views

coin reversal puzzle with one hand and two stacks

Suppose that you have N labeled coins pinched in one stack in your fingertips (your palm is above your fingers and your palm is facing down, so that you can drop as many coins as needed from the ...
3
votes
2answers
185 views

Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
0
votes
0answers
59 views

Find minimal set of progressions which intersections, unions or negations covers given set

Given an integer $N$ and a set of integers in $[1; N]$. Find a minimal set of integer arithmetical progressions such as given set can be covered using operations $A \cap B$, $A \cup B$ and $\overline ...
1
vote
1answer
85 views

Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language: $L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$. ($G$ ...
7
votes
2answers
376 views

get a point in polygon (maximize the distance from borders)

I have several 2D polygons represented by lists of xy-coordinates of their vertices. It is needed to get several points inside the polygon so that they lie possibly far from the polygon's borders ...
2
votes
2answers
220 views

Integers up to n having an even number of trailing zeros in their factorial

It is well-known that the number of trailing zeros in the factorial $k!$ is given by the nice function $$ z(k) := \sum_{i \ge 1} \left\lfloor \frac{k}{5^i} \right\rfloor. $$ Now assume that we want ...
0
votes
0answers
74 views

Minimize the length of two disjoint segments in the string with given property

You are given a string s of size n, consisting of characters A and B only. You have to find minimum sum of size of the two disjoint segments of the string s such that number of A's in them are >= z. ...
3
votes
1answer
130 views

Random weighted selection without replacement

I am using the following procedure to select $m$ different numbers $\{i_1,\ldots,i_m\}$ from the set $\Omega = \{1,\ldots,N\}$, with $m,N\in\mathbb{N}$ such that $m< N$. Selection procedure ...
4
votes
4answers
409 views

Determine if a graph has a large clique

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed. I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density ...
2
votes
0answers
59 views

Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...
2
votes
0answers
30 views

largest size for a randomness extractor

I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature. Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
0
votes
0answers
45 views

Multi-objective set-cover optimisation problem

I'm looking for an algorithm to solve the following multi-objective set-cover problem. We start with a 'universe' (set) of items $\mathcal{U}$, along with a partitioning $P = \{p_0,\ldots,p_m\}$ ...
2
votes
0answers
134 views

Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers. To be precise, I want ...
3
votes
0answers
140 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
1answer
179 views

How to perform Importance Sampling with Prior Information

Let us define a random variable $X$ with density function $p(x)$. We wish to calculate $\mathbb{E}[f(X)] = \int f(x)p(x)dx$. We can compute the expectation by Monte Carlo simulations as ...
4
votes
0answers
101 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 ...
0
votes
0answers
66 views

approximate coordinates in a one dimensional lattice

suppose I have a finite set of real numbers ${r_1, \ldots r_n \in \mathbf{R} }$ and a single real number $x \in \mathbf{R}$. Is there a fast algorithm for finding integer numbers ${i_1, \ldots i_n \in ...
4
votes
1answer
142 views

Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?

Is there any known efficient algorithm (something that works better than brute-force algorithm) to check that given a $(0,1)$-$d \times d$ matrix $A$, is there a permutation matrix $P$ of the same ...
4
votes
2answers
145 views

Details of generation programs supplied with nauty

The program nauty comes with gtools which contains, among others, several generation programs like geng, genbg, ... I was ...
1
vote
4answers
415 views

Counting simple 4-cycles in an undirected graph [closed]

I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it ...
3
votes
0answers
167 views

Finding a basis for the (linear combinations) span of a matrix group, efficiently?

I have an algorithm whose bottleneck is the following task: Let $\mathbb{F}$ be a finite field. Given a set of $k$ invertible matrices $g_1,\dots,g_k\in GL_n(\mathbb{F})$, let $G=\langle ...
2
votes
1answer
560 views

Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq ...
12
votes
2answers
518 views

Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product $$ p=b_1 b_2 \cdots b_n$$ where each $b_i\in A$. Clearly $n-1$ multiplications suffice to compute $p$; ...
3
votes
2answers
187 views

Equipartition of the circle [closed]

Browsing an old technical studies pupil's school book, I have found the description of a method to place at equal distance $N$ points on the circumference of a circle. I am looking for a proof of this ...
3
votes
2answers
200 views

Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances. The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
2
votes
1answer
245 views

efficient arithmetic with (short) Conway games?

We consider "games" in the sense of ONAG. Conway's definition of a game $G$ as a pair $G = \{L \mid R \}$ of sets of games, together with the definitions of inequality and the arithmetic operations ...
1
vote
0answers
52 views

Finding special vectors generated by a matrix

Let $G\in \Bbb Z^{n\times n}$ be a unimodular matrix. Are there any efficient algorithms to find the maximum norm of a vector $v$ that satisfies $\langle\Delta(v),v\rangle=0$ over all vectors $v\in ...
1
vote
0answers
44 views

Covering a set of points by bounded geometric object/objects

1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$. 2) Also, in general setting, the problem is to ...
6
votes
0answers
140 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 ...
2
votes
1answer
133 views

Finding particular reduced words for Weyl group elements

I am studying cluster algebra structures on the coordinate rings of partial flag varieties, as defined in the paper Partial flag varieties and preprojective algebras by Geiss, Leclerc and Schröer. One ...
2
votes
1answer
137 views

Are there any good techniques for calculating Hausdorff measure?

I'm aware that many techniques have been developed for the purpose of calculating Hausdorff dimension (although I'm fairly unfamiliar with them), but my question is whether or not we have any good ...
12
votes
1answer
516 views

Stable matchings when switches have costs

The Gale-Shapley algorithm finds a stable matching in the complete bipartite graph, for any preference matrix. It's also well-known that stable matchings don't always exist in the complete graph ...