Hi! How are you @vzn and @ThomasKlimpel? long time not coming here!

I have a question (or inquiry) regarding Discrete Log problem! suppose we have find an efficient algorithm for factoring problem, then does it mean that we have an efficient algorithm for Discrete Log problem?

my answer is YES; because discrete log problem asks us to find log_a b = k?! Now, the problem is that given a and b, find k. The difficulty of this problem is that if b is big number, then you cannot find answer k. So, the brute force would be to try a^., a^.., ...., until a^k. Now, using polynomial time algorithm for factoring, we can the prime factor of b. so we can get k in poly-time. Do you have any argument!

Interesting answer by Jean Marie (still something is missing): math.stackexchange.com/questions/2547251/…

@vzn No, it is not a randomized coloring algorithm. Section 2.2 - 2.4 in Pascal Schweitzer's thesis provides very good, correct and to the point explanations. Babai's famous paper also contains good material on WL, which is at least correct. There is also "The Weisfeiler-Lehman Procedure", by Vikraman Arvind as advertised here, but ...

... I am not sure whether I should really recommend it. The many typos early in the paper already indicate the sort of quality to expect from that article, and also the content itself has so many minor inaccuracies that I don't know what to say. For example, it writes just after introducing the k-dimensional WL method: "It turns out that 2-WL coincides with the color refinement procedure". OMG!

Pascal Schweitzer correctly requires k >= 2 for the general definition, and makes it clear that color refinement is considered to be the 1-dim WL method. Most of the theorems later discussed in the article are only for color refinement (or for 2-WL??? avoiding unnecessary inaccuracies would really help readers!), and the k-dim case is most of the time referred to the original research papers. The article even lacks pictures, so its only use is as an entry point into the research literature...

Let me shortly explain why the mistake with respect to 2-WL is obvious, and does not need an expert to point out: the color refinement procedure cannot refine regular graphs. But the graphs which cannot be refined by 2-WL are the strongly regular graphs.

@vzn The problem solved in Babai's famous paper is actually slightly more general, and related to group theoretic question. The coset intersection problem is representative of the type of problems equivalent to it. That problem is also more natural (in a certain sense) than graph isomorphism, since it arises as a subproblem when you try to solve GI and want to only work with an abstract summary of what you already know.

That type of problem might indeed turn out to be a useful "subroutine" for other algorithms, some kind of group theoretic preprocessor.

I tried to dig deeper into that strange thing with 2-WL from "The Weisfeiler-Lehman Procedure" by Vikraman Arvind. It turns out that already the definition of WL is different from Pascal Schweitzer and Laszlo Babai. V. Arvind is correct that for his definition, 2-WL "coincides" with the color refinement procedure, if we ignore that it is slower and uses more memory.

@YOUSEFY hi again, my understanding is you are correct, factoring is "at least as hard" as discrete log, but its open question whether "discrete log is at least as hard as factoring". neither has been proven NP hard, another foremost open problem.

@enumaris thought they might have some working in US. think you should inquire, would like to know what you find out. they are arguably top corp in the world for deep learning at the moment. re your ML work, would love to hear more/ details/ discuss at length, but understand if youre not in the mood to communicate on it.

@vzn Because it is not randomized. What is randomized is Pascal Schweitzer's ScrewBox, and potentially also his paper about graph kernels.

@ThomasKlimpel maybe only imagined anyone referring to it as a randomized algorithm, but looking, it chooses vertexes to apply colors to but seems to make no ordering to vertices chosen. what is the proof it leads to identical results no matter what vertex ordering is chosen? if that is not the case, seems uncontroversial to call it randomized. it also leads to both false positives/ negatives, a characteristic of randomized algorithms.

You refine until no further refinement is possible. By this you obtain "coherent configurations", as explained in Babai's paper. Since this procedure is applied to each graph individually, it would be catastrophic if the result would be random. The result is not just "not random", but actually "isomorphism invariant".

@ThomasKlimpel am not claiming the "result is random". think it is quite possible the algorithm can produce different results on the same graph depending on vertex order. do you have any evidence to the contrary? that is not the same as saying "the result is random".

If the result would depend on the vertex order, then it would not be isomorphism invariant!

@ThomasKlimpel uh, ok, so what is the proof the algorithm is isomorphism invariant?

Each basic step in the algorithm is isomorphism invariant, hence the total algorithm is isomorphism invariant as well.

I'm happy to talk about ML, but the project I'm working on is still at the very early stages, so I don't really want to delve too deep into that particular project. I'm trying to learn RNNs using pytorch atm tho. It seems to be more dynamic than Tensorflow.

@enumaris am sure even the early stages have interesting ideas/ details. to me its better than nothing :)

Yeah, but I'm not too keen on divulging the details at this point in time, sorry. :(

@enumaris ok/ np. but still dont see why not.

o.o

maybe at a later time :)

I'm working on a cat/dog detector in pytorch to get myself acquainted with it lol

@ThomasKlimpel lol doesnt exactly sound like a proof to me. does anyone define "isomorphism invariant"? there are other randomized algorithms that look similar to me & can get different results afaik. eg basic coloring algorithms. afaik they can color with different # of colors depending on vertex order (chosen). they dont nec vary widely, but they vary. its statistical.

@enumaris you can chat about what you want.

what do u mean?

@enumaris youre in a cyberspace chat room

alrighty