Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithms
Search options questions only
not deleted
user 12481
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
2
votes
1
answer
161
views
Complexity of numerically solving systems over the reals
Basically I am interested in
What is the complexity of numerically solving systems over $\mathbb{R}$?
By solving I mean finding at least one numeric solution with given
precision.
Probably the …
- 25.4k
3
votes
0
answers
50
views
Complexity of OBDD isomorphism (representing same function after permutation of variables)?
According to wikipedia Ordered Binary Decision Diagarams (OBDD) are a data structure that is used to represent a Boolean function.
OBDD is a DAG with two sinks $0,1$.
The size of the BDD is number o …
- 25.4k
4
votes
3
answers
290
views
Complexity of a problem remotely related to the discrete logarithm $A=x g^x$
I suspect generic exponential algorithms will work.
The solution over $\mathbb{C}$ containts Lambert W function,
so a reduction might not be possible. …
- 25.4k
2
votes
2
answers
392
views
Algorithm for finding integral points $P,n P$ on an elliptic curve
We found and implemented algorithm which finds integral points of infinite order $P=(X_1,Y_1)$
and $nP=(X_2,Y_2),n>1$ on an elliptic curve $E : y^2=x^3+a_4 x + a_6$.
Let $X(x)/Z(x)$ be the $X$ coordin …
- 25.4k
2
votes
1
answer
260
views
Does Coppersmith's method always finds non-trivial factor of integers of the form $n=a(2^k b...
Got an argument and numeric evidence that pari's implementation
of Coppersmith's method finds non trivial factor of integers
of certain form under some assumptions very efficiently.
Three $5000$ bit …
- 25.4k
1
vote
2
answers
182
views
Finding polynomial $f$ given $\{f(x_i)\}$ for unknown $x_i$
Given $\{a_i=f(x_i)\}$ ($x_i$ are unknown) and $d$, what are the best algorithms
to find $f$ or another polynomial $g$, satisfying $a_i=g(y_i)$ for
known $y_i$, possibly $x_i=y_i$? …
- 25.4k
4
votes
1
answer
282
views
Small roots of $f(x) \equiv 0 \pmod{n^2}$
Let $f(x)$ be squarefree polynomial with integer coefficients.
For integer $n$ define "small root modulo $n^2$" integer $a$
satisfying $1 \le a \le n$ and $f(a) \equiv 0 \pmod{n^2}$ and
$f(a) \ne 0$. …
- 25.4k
5
votes
1
answer
307
views
Complexity of graph 3 coloring and counting algorithm
:=0
Enumerate independent sets A up to size n/3
If G \ A is bipartite set cols := cols + number_of_2_colorings of G \ A
# G \ A might not be connected
Q1 What is the complexity of these algorithms …
- 25.4k
1
vote
1
answer
178
views
Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?
Let $G$ be connected simple graph.
Clique cover of graph $G$ is partition of the vertices of $G$
into $k$ disjoint cliques $D'_i$.
Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle
in …
- 25.4k
3
votes
1
answer
694
views
Is strictly harder than NP-hard cryptography possible?
Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear co …
- 25.4k
1
vote
0
answers
72
views
Reduction maximum independent set to MIS in a very dense graph
We got a reduction maximum independent set to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G$ be graph of order $n$ and adjace …
- 25.4k
4
votes
0
answers
241
views
Can we make cryptography signature algorithm based on hardness of isomorphism?
In public key cryptography, Alice knows functions $f$ and its inverse
$f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message
$m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the ver …
- 25.4k
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is polyno …
- 25.4k
5
votes
2
answers
521
views
Diffie Hellman cryptography based on graph isomorphism?
We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph …
- 25.4k
7
votes
2
answers
676
views
What is wrong with this deterministic algorithm efficiently generating large primes?
According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k …
- 25.4k