The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
88 views

Toroidality testing

Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer-Myrvold algorithm (which has a MATLAB implementation) and would like to know if there is something ...
4
votes
1answer
240 views

Generating non-isomorphic graphs by adding edges to a given graph

Hello! This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here! I am given a fairly large graph $G$ and ...
6
votes
1answer
381 views

Is equality of terms for “real” numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
0
votes
0answers
107 views

Examples of applications that use the Schnorr digital signature?

Hi there. It may not be the best place to ask this question, but here goes: I have made a study on digital signatures, especially on the Schnorr digital signature, and I was just wandering if there ...
3
votes
1answer
104 views

Search for common substructures in list of graphs

I have had the following problem on several occasions and I was wondering whether there is a general technique to solve this problem. Given a list of graphs with property $P$. Is there a general ...
0
votes
1answer
158 views

An Algorithm to Determine a probable profit

I 'm searching for an algorithm (and except the naive brute force solution had no luck) that efficiently ($O(n^2)$preferably) does the following: Supposing I’m playing a game and in this game I’ll ...
2
votes
1answer
280 views

Finding a subspace disjoint from a union of subspaces

Let $k$ be a finite field (I care about $\mathbb F_p$, especially $\mathbb F_2$) and let $V_1,...,V_N\subset k^n$ be subspaces. I want to find a subspace $S\subset k^n$ such that $S\cap V_i=0$ for ...
8
votes
1answer
361 views

Constructive proof of “Projective implies proper”

For every ring $A$, the structural morphism of schemes $\pi_A : {\bf P}^n_{A} \to {\rm Spec}{A}$ is a closed map. The usual proof of this fact is not constructive : given equations of a closed subset ...
16
votes
3answers
844 views

Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute $f(x)$. The input consists of the digits of $x$ and the output of a rational number approximating $f(x)$. A function $f$ is called ...
6
votes
1answer
244 views

How do you compute the primes of bad reduction?

Suppose that I am given a subscheme $Y$ of $\mathbf{P}^n_{\mathbf{Z}}$, flat over $\operatorname{Spec}\mathbf{Z}$ and with smooth generic fiber $Y_{\mathbf{Q}}$, defined by the vanishing of some ...
4
votes
1answer
415 views

Exact arithmetic for real algebraic numbers

There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...
0
votes
2answers
281 views

Creating composite rank [closed]

Problem: Suppose that $K$ different students are ranked based on $N$ different parameters (such as Physics marks, English marks, Biology marks, IQ etc). The rank under each parameter can be repetitive ...
7
votes
1answer
318 views

Experimental mathematics: how are floating point equations discovered/converted to exact equations?

the 2005 AMS article/survey on experimental mathematics[1] by Bailey/Borwein mentions many remarkable successes in the field including new formulas for $\pi$ that were discovered via the PSLQ ...
2
votes
1answer
215 views

An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
4
votes
2answers
152 views

Computing Slim Extensions representing Ext

Hey Everyone Let $A$ be an algebra over a field (group rings $k[G]$ for group cohomology, the Steenrod Algebra). We want to compute, say, $Ext_A(k,k)$, so let $F_*\to k$ be an $A$-free resolution. ...
0
votes
3answers
650 views

Largest subarray with average $\geq$ k

I try to solve this problem. The algorithm I developped has a complexity of $O(n^2)$. When dealing with large data the program is brought to its knees. Do you have any idea that might be faster than a ...
0
votes
2answers
183 views

Maximizing number of factors contributing in the sum of sorted array bounded by a value

I have a sorted array of integers of size n. These values are not unique. What I need to do is : Given a B, I need to find an i<A[n] such that the sum of ...
6
votes
1answer
241 views

Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?

I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in ...
3
votes
1answer
110 views

Median-of-k elements

Hello, Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$. Then out ...
2
votes
1answer
233 views

Complexity of establishing finite groups (non)-isomorphism ?

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N ...
8
votes
3answers
1k views

Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ? (Main case - complex numbers, comments on other cases are also welcome. "Given" ...
2
votes
2answers
256 views

Lattice reduction on an orthonormal lattice?

Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you ...
0
votes
1answer
93 views

Provided a list of sets, $L$, computing an array where each entry $q_i \in Q$ is the family of sets in $L$ that have intersection $k$ with $l_i \in L$

I have a set of $(l_1, ..., l_N) \in L$ smaller sets, each with $(r_1, ..., r_M) \in R$ integer elements. I would like create an ordered array of $(q_1, ..., q_N) \in Q$ sets s.t.: (1) Each $q_i \in ...
9
votes
1answer
295 views

Algorithm to test for discrete or quasi-Fuchsian subgroups of PSL(2,C)

Let $\Gamma = \pi_1(S)$ denote the fundamental group of a compact surface $S$ of genus $g>1$. Given a representation $\rho : \Gamma \to \mathrm{PSL}(2,\mathbb{C})$, specified by matrix ...
1
vote
1answer
260 views

Computing the ratio of two large integers modulo m

$P(n)$ and $D(n)$ are two large integers. Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer. I want to compute $R(n)\bmod m$. $P(n)$ and $D(n)$ are too large to be computed but $P(n)\bmod m$ and ...
0
votes
1answer
538 views

Finding the lowest cost set of disjoint paths using all nodes in a directed graph?

I have a directed graph with edges connecting nodes representing costs. I wish to find the set of paths which -go from node 'start' to node 'end' -are node-disjoint (except for the start and end ...
1
vote
5answers
1k views

The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure. Thanks
1
vote
0answers
123 views

Efficient algorithm for computing the integral closure of a computable domain

what is known? even talking about efficiency relatively to the complexity of the computation of the domain itself?
6
votes
2answers
494 views

Algorithm for reducing words in a Coxeter group

Let $W$ be a Coxeter group with set of simple reflections $S$. Suppose that I have chosen a preferred reduced decomposition for every element of $W$. Given an arbitrary word in the alphabet $S$, is ...
1
vote
0answers
90 views

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard? Equally interesting would be to learn about such problems with a ...
-5
votes
2answers
685 views

why do we need algorithms, and why is non-convex optimization difficult? [closed]

A simple question, but (I'm quite sure) not a superficial one: is the basic distinction between algorithms and much of the rest of math that algorithms try to tackle problems for which we lack global ...
9
votes
2answers
679 views

How to compute the Picard rank of a K3 surface?

I'm curious about the following question: Given a K3 surface, how does one proceed to compute its rank? Of course the answer may depend on the form of the input, i.e. how the K3 is "given". So ...
15
votes
1answer
2k views

Conceptual explanation of Strassen's trick for matrix multiplication

Algorithms for fast multiplication of polynomials and integers have well-known conceptual explanations. A good survey paper is Daniel J. Bernstein's Fast Multidigit Multiplication for Mathematicians. ...
2
votes
0answers
178 views

A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete. I provide two simple definitions and one example at first. Definition 1. Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...
6
votes
1answer
2k views

Origin of square-and-multiply algorithm

I'm teaching an introductory course in cryptography and explained the square-and-multiply algorithm to the class. http://en.wikipedia.org/wiki/Square-and-multiply_algorithm Someone asked who ...
0
votes
1answer
252 views

Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...
10
votes
3answers
470 views

Algorithms in Invariant Theory

Let $V$ be a polynomial representation of the general linear group $\Gamma:=\DeclareMathOperator{\Gl}{Gl}\Gl_n(\newcommand{\C}{\mathbb C}\C)$. In chapter 4.6 of his book "Algorithms in Invariant ...
2
votes
3answers
2k views

Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote: "This scheme will thus work as ...
5
votes
0answers
350 views

Determine if a matrix is unimodular

Is deciding if an integer square matrix has determinant $\pm 1$ faster that calculating the determinant of the matrix?
5
votes
0answers
200 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 ...
1
vote
0answers
138 views

Randomized alternative to Buchberger's algorithm

Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra. Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...
0
votes
1answer
237 views

Algorithm for vector space

I have $n$ vectors $e_1 \in (\mathbb Z/2 \mathbb Z)^m,\dots,e_n \in (\mathbb Z/2 \mathbb Z)^m $ and a vector $ v \in (\mathbb Z/2 \mathbb Z)^m $ I need to find the better algorithm which answers ...
3
votes
2answers
1k views

Generation of All Path in a Directed Acyclic Graph

I am working on a very large dataset of a single DAG whose vertices have a low branching factor. I need to generate all possible (simple) paths starting from the source and write them to a file. My ...
1
vote
1answer
193 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
2
votes
1answer
133 views

How to deconstruct a sum of intersecting upsets

A set system $\mathcal{U}\subset P([n])$ is an upset if $B\supset A \in \mathcal{U}$ implies $B\in \mathcal{U}$, intersecting if $A,B\in\mathcal{U}$ implies $A\cap B \ne \emptyset$. Note that a ...
3
votes
2answers
383 views

pseudo-random algorithm allowing O(1) computation of Nth element

It is obvious that using seed value one can easily compute next value of some (deterministic) pseudo-random algorithm - so Nth element can be computed in O(N). But is there such PRNG that allow to ...
0
votes
1answer
237 views

Designing a Hash function that results in minimum size and no collisions

Dear all, I have the following problem: Consider an array of $N$ vectors $v_{i} \ i=1...N$ of size $L$ bits, where each bit is 1/0 with equal probability. I want to find a hash function $H()$ that ...
12
votes
2answers
505 views

Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...
10
votes
1answer
688 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time. ...
15
votes
4answers
783 views

Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem: Show, for all integers $1 \leq i \leq k$, that the univariate ...