The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
281 views

Find root in finite field

What efficient algorithms exist for the solving $x^N = a$ in GF(q)? What are their complexities?
1
vote
1answer
271 views

calculate function from its divizor

There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$. There is algebraic function f on C. We have div(f). How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + ...
2
votes
0answers
189 views

Choosing a base where a given digit of a given number appears the most times

Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)
0
votes
0answers
150 views

Condition and algorithm for Decomposition of formal power series

$$F(x)= \Sigma_0^{\infty} a_i x^i$$ is formal power series, $a_i\in N\bigcup 0$,N is the set of natural number,under what condition may it be decomposed into a system of equations terms of which are ...
0
votes
2answers
229 views

Enlcosing a set of ellipses within one ellipse

Hello, Is there an algorithm that takes in a set of ellipses and gives back and ellipse that encloses the set?
1
vote
0answers
76 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
224 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
356 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
92 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
103 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
152 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
260 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 ...
7
votes
1answer
354 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
840 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
240 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
358 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
254 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
308 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
195 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
150 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
567 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
176 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
229 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
223 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
246 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
285 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
252 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
484 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
434 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
652 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
635 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 ...
12
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
171 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
1k 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
249 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
449 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
336 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
197 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
135 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
236 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
191 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
130 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 ...