The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
41 views

all paths between two nodes of an grid structure [on hold]

i have an 5*5 matrix numbered from 1 to 25. i wanted to print all paths between any two nodes. ...
11
votes
1answer
205 views

Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question. Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the ...
-3
votes
0answers
58 views

Messages on rotating wheels [closed]

The question is: Would it be possible display a message (image, logo, text, ...) on a rotating wheel so that it would become readable once rotating at a certain speed, knowing that our brain will ...
0
votes
2answers
93 views

Generate all non-isomorphic partitions $\pi = \{ \{1, …, n-1\}, \{n\} \}$ for all graphs of order $n$

Let $G$ be any connected, undirected, and unweighted graph of order $n$. Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster ...
4
votes
0answers
30 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 ...
1
vote
1answer
162 views

Finding the “minimum norm” of points in projective space above a prime field

I am working on doing explicit computations finding class groups of quaternions over $\mathbb{Q}$, and the following question (with $n=3$) was a clear choking point: Given a point $P = [x_0, \dots, ...
5
votes
4answers
156 views

From a (not positive definite) Gram matrix to a (Kac-Moody) Cartan matrix

Suppose I am given a symmetric matrix $G_{ij}$ with $G_{ii} = 2$. Can I always find an invertible integer matrix $S$ such that $(S^T G S)_{ii}=2$ and $(S^T G S)_{ij} \leq 0$ for $i \neq j$? Is there a ...
-4
votes
1answer
148 views

Without the use of a calculator, how to calculate the logarithm of 2 and 3 in base 10 [closed]

Without the use of calculator how to calculate $\log_{10} ~2$, $\log_{10} ~3$?
1
vote
1answer
132 views

Using Jacobi fields to approximate parallel transport along geodesic:is the following limit true?

I apologize if this is not a research level question (already tried asking http://math.stackexchange.com/questions/1303288/relation-between-parallel-transport-and-jacobi-field-iion stack exchange with ...
8
votes
1answer
99 views

Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time

I have the book "Handbook of Computational Group Theory", by Derek Holt, and in it is a section on finding the transversal of a subgroup. Recall a transversal of a subgroup $H$ of $G$ is a single ...
0
votes
0answers
52 views

Finding a “special” non singular submatrix

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ ...
7
votes
2answers
140 views

Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic. Now it feels to me that this class of graphs is "too ...
5
votes
0answers
157 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, ...
1
vote
1answer
73 views

Algorithm to generate a (pseudo-) random high-dimensional function

I don't mean a function that generates random numbers, but an algorithm to generate a random function. "High dimension" means the function is multi-variable, e.g. a 100-dim function has 100 different ...
2
votes
1answer
101 views

Positive rational numbers as sum of unit fractions [duplicate]

Let $U = \{\frac{1}{n}: n\in\mathbb{N}, n>0\}$ be the set of unit fractions. For integers $m,n>0$ there is always a finite subset $S\subseteq U$ such that $\frac{m}{n} = \sum_{u\in S} u$, see ...
8
votes
0answers
130 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, ...
2
votes
0answers
63 views

A basic minimization problem over finite fields

Let $p$ be a prime, and suppose we are given $n$ values mod $p$: $a_1,...,a_n\in Z_p$. Is there a fast algorithm for finding $\alpha\in Z_p$ which minimizes the value $\max_i (\alpha\cdot a_i$ mod ...
5
votes
1answer
336 views

How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field. Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra. Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$ that one needs to take ...
4
votes
2answers
239 views

Breaking a rectangle into smaller rectangles with small diagonals

Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...
2
votes
2answers
162 views

Paper of Denis Simon on quadratic equations in dimensions 4, 5?

In several places I have come across references to a 2005-6 preprint of Denis Simon entitled Quadratic equations in dimensions 4, 5, and more This paper gives fast algorithms to find isotropic ...
4
votes
1answer
203 views

Constructing the oracle for Grover's algorithm

For a final project in my class, I decided to try to simulate a quantum computer and implement Grover's algorithm. I followed this excellently written blog post by Craig Gidney, and was successful in ...
9
votes
3answers
349 views

Computing minimal polynomials using LLL

I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation ...
4
votes
0answers
163 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 ...
3
votes
1answer
123 views

Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
11
votes
1answer
458 views

Can Shor's Algorithm be modified to run efficiently on a classical computer?

Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...
4
votes
0answers
134 views

Minimum number of real multiplications to multiply two quaternions [closed]

Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows: $$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$ We only need the ...
5
votes
2answers
190 views

Ordered lattice point enumeration

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community. Setup: Let ...
4
votes
0answers
108 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 ...
0
votes
1answer
106 views

Is there a closed form for tan(q*pi) with q rational? [closed]

I'm looking for a closed-form expression for tan (q*pi) for q rational, or an algorithm that generates one, or some other means of compactly describing the closed-form without referencing an infinite ...
1
vote
2answers
188 views

Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime ...
4
votes
1answer
61 views

Smallest sum $S \geq k > 0$ using one element from each of several sets of nonnegative integers

Does there exist a way to efficiently solve the following problem? Given some constant $k$ and several sets of non-negative integers: ...
3
votes
1answer
94 views

What is the Complexity Class of the “Function Variant” of the Integer Factorization Problem?

I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered. So, ...
0
votes
0answers
25 views

Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...
2
votes
0answers
88 views

Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)

Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of ...
1
vote
2answers
136 views

Curves similarity metric [closed]

I am working on an optical character recognition algorithm that takes vector data (i.e. polylines) as input rather than raster picture. E.g., we have N polyline samples, and when certain polyline is ...
12
votes
1answer
361 views

Computer software for periods

Kontsevich and Zagier define a period as an integral of a rational function (over $\mathbb{Q}$) defined on a $\mathbb{Q}$-semialgebraic set. They conjecture that if two periods are equal, then the ...
1
vote
1answer
53 views

Hamiltonian Path through $n$-bit strings with maximum number of $0\mapsto 1$ transitions

Let $G_n$ be the complete graph whose vertices are the $2^n$ $n$-bit strings. Let $H_n$ denote the Hamiltonian path through $G_n$ that uses the maximum number of edges that correspond to a single bit ...
1
vote
0answers
50 views

Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M

this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :) Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...
1
vote
0answers
48 views

Can we give efficiently the solution of a bilinear system of equations over a finite field?

Consider a finite field $F$ and suppose we have a system of equations $$h_1(\alpha,\beta)=0,h_2(\alpha,\beta)=0,...,h_t(\alpha,\beta)=0$$ where $\alpha=(\alpha_1,...,\alpha_s)$ and ...
6
votes
4answers
380 views

Expected value of a function over random sets

I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows: Pick $k$ distinct numbers out of numbers ...
2
votes
0answers
175 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning? [closed]

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). It seems to me that much ...
2
votes
1answer
97 views

Is there any algorithm can find local minima of nonconvex objective function in guaranteed polynomial time?

More precisely, The setting could be formulated as, $min. F_{\lambda}(p)$ over permutation matrices $P$ Here $F_{\lambda}(p)$=$\lambda *F_{0}(p)+(1-\lambda)F_{1}(p)$ where both $F_{0}(p)$ and ...
8
votes
0answers
247 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 ...
5
votes
0answers
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 ...
2
votes
1answer
79 views

Future-Proof Encrypt for Multiple Independent Parties

I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...
3
votes
1answer
127 views

Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...
5
votes
0answers
192 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 ...
1
vote
1answer
152 views

Finding Laurent Series of a function [closed]

I've been assigned to write a computer program which then calculates the Laurent series of a function. Of course I'm familiar with the concept, but I've always calculated the Laurent series in an ad ...
0
votes
0answers
63 views

Generating alternating cycles on a perfect matching

Given a perfect matching $M$ in a regular bipartite graph $G$, is there an efficient algorithm to randomly generate self-avoiding alternating cycles with uniform distribution? Ideally, such an ...
1
vote
1answer
121 views

Computation Complexity for Golden Section method

I need to provide computational complexity for the algorithms in my work. One of the algorithms I have used is Golden Section method for line search. I took a look at "Nonlinear Programming" book by ...