New answers tagged ds.algorithms
2
I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.
2
The problem as described is not convex, due to the nonconvexity of the constraint set. However, if you were to permit a relaxation, we could write your problem as
$\begin{array}{ll}
\max & \sum_{p\in P} t_p\\
\text{subject to }& t_p \geq \langle x, \|p\| p \rangle\\
& t_p \geq -\langle x, \|p\| p\rangle ,\\
& \|x\|_2 \leq 1.
\end{array}$
...
4
Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?
2
I found an answer in the paper "Fast sparse matrix multiplication" as Theorem 2.4. The authors cite "Fast rectangular matrix multiplications and applications", so that's the original source, I guess. It is possible to do it in a black-box fashion, so it works for any fast multiplication algorithms. That, of course, does not prove ...
5
It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a bit more of an open question.
If you mean GCT generally as applying algebraic geometry to complexity theory, or perhaps even slightly more specifically using ...
3
This question was posted more than 8 years ago, and much progress was done since then. However, many questions remain open, even very natural ones like sampling a random graph with prescribed clustering coefficient. Also, sampling simple graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult.
I would like to ...
2
Using Fermat theorem, $a^p -a = 0 (\mod p) $ and if a and p are co-prime, then $ a^{pā1} ā 1 =1(\mod p) $
So if u choose n to be a prime number(say p), then $a^{b^c} \mod p = a^{ (b^{c} \mod (p-1))} \mod p $ ,
Then you can use Fast Exponentiation trick in two levels, once for $b^c \mod p-1 $ then for $a^{b^c} \mod p $
I also suggest you to look at cses ...
7
Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments. As a result, the question is still open.
Please let me know if you have any ideas. :)
Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2. Then, you check if ...
9
There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142ā149, Jan. 1989.
The basic idea: Instead of checking $n = ab$ modulo $p$ for some random prime number $p$, check it modulo $2^i-1$ for some integer $i$. The reduction ...
3
Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$.
We can at least prove that if $x$ is chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case ...
Top 50 recent answers are included
