New answers tagged

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