theory salon

3:03 AM

@vzn I didn't really get the problem from anywhere, it's my own little project I'm working on heh. I went to UCSD. I don't know the URL to my thesis lol.

vzn

4:04 AM

@enumaris ok. you dont seem to care if nobody else reads it. presumably not something youd want to state out loud at a thesis defense.

... huh, guess always-impressive google ML can even overcome ~~lazy~~ blase phd postgraduates arxiv.org/abs/1703.03039

enumaris

5:40 AM

lol, I think everyone knows that theses don't tend to get read all that much...unless you're like Richard Feynman I guess. I don't really mind if nobody reads my thesis.

vzn

7:01 AM

@enumaris youre not making it any easier. find your attitude surprising/ unusual, esp for something that took so much work & several years effort. apparently you regard it as mostly "self-serving". anyway would you care to chat about your spotify prj at greater length? have very strong interest in ML over the years, have some new ideas, may write them up at some pt... vzn1.wordpress.com/category/ai

enumaris

well right now I'm trying to build a RNN in tensorflow, but I'm having a bit of trouble haha

it's not really learning...

I think RNNs are much closer to turing machines than other kinds of networks

enumaris

8:08 AM

whoop, figured out the problem

Jarek Duda

11:27 AM

@ThomasKlimpel, as the weaker of two missing links seems quite basic for mathematicians, let's ask them:

0

Q: Analogoue of Vandermonde determnant for fittng quadratic form?

1D interpolation: finding a polynomial satisfying $\forall_i\ p(x_i)=y_i$ can be written as system of linear equations, having well known Vandermonde determinant: $\det=\prod_{i<j} (x_i-x_j)$. Hence, interpolation problem is well defined as long as the system of equations is determined ($\det\neq...

Thomas Klimpel

11:44 AM

@JarekDuda Yeah, there might be a nice answer to that simpler question. Adding a motivation to the question is also fine. A slight problem is that the motivation needs an answer to a less simple question, even so that less simple question probably still has an answer. The answer to that less simple question does not necessary imply an efficient "non-group theoretic" algorithm for graph isomorphism.

Jarek Duda

@ThomasKlimpel, this seems a diametrically different approach, but sure can have own specific problems ... which might have a deep connection to problems of e.g. WL-based approaches ...

There are two missing links - one is comparing two affine spaces of quadratic polynomials - while it can be cheaply done for 1 or a few dimensional affine spaces, can we cheaply do it for larger dimensions? If not, can we manipulate the number of points to this stiff number the method works for?

The second link is this issue with adding extra points in intersection of wobbling ellipsoids ... I see my original hope was wrong - it definitely adds -x for every x ... but this seems not a problem for what we have in strongly regular graphs (still needs a proof) ... are there more such added extra points?

Thomas Klimpel

Yes, it might really be a different approach. There is one relatively simple indication for this. As long as it is just a matter of writing down the coefficients of some additional characteristic polynomials, then it is probably not a fundamental different approach. The point about WL is that it leads directly to a canonical labeling scheme.

One characteristic of WL is that it is applied to a single graph in isolation. This gives you additional labels or colors on the vertices, edges, (and multi-edges in k-dim WL), and so on.

Jarek Duda

12:00 PM

Sure, this approach doesn't seem very practical, WL is definitely more useful ... the purpose here is only to prove that GI is P ... but there is still a long road there :/

Regarding applying to only a single graph, e.g. to find automorphisms, we could also do it here ...

Thomas Klimpel

WL is useful as a baseline, and for being able to quickly judge new sufficiently well specified algorithms for graph isomorphism. The most straightforward way for doing this is just to feed the counter-examples to k-dim WL to a sufficiently well specified graph isomorphism algorithm. In a sense, this is what you do routinely by focusing on strongly regular graphs.

Jarek Duda

Still, many years have not allowed it to show that GI is in P ... and we don't know much about P vs NP ... it is why I am looking for completely different perspectives on these problems - exploring exotic options ...

Thomas Klimpel

12:24 PM

We do know much about P vs NP, all those barrier results like relativization, algebrization, natural proofs, counter-examples for resolution based algorithms, counter-example for linear programming based algorithms, relations to proof systems, relations to higher-order proof systems, ... They are simply not fun, even so they are pretty strong indications that P != NP, and that it will be hard to proof that.

We also know quite a bit about GI, but what we know is much more positive and actually real fun, once you dive into it. It is quite possible that GI is in P, but I doubt that you can get there by a "non-group theoretic" algorithm.

7

Q: Classifications of finite nilpotent groups

I would like to understand the concept of classification in the context finite groups. For finite abelian groups and finite simple groups, it's clear to me what is meant by classification. However, these are the cases where a "perfect classification" turns out to work fine. Because I have a pret...

abstract-algebra finite-groups

Jarek Duda

While linear programming is continuous (and useful e.g. for compressed sensing problem: which seems exponential but is P), the rest seems discrete (?) - approaches using continuous math seems less explored, and so I focus there.

Thomas Klimpel

That question about "finite (indecomposable) p-groups" was my own starting point for thinking about GI. It was a question about "the concept of classification", and those p-groups were choosen because they don't feel too complicated, yet still escape naive approaches at a solution.

Jarek Duda

If you like abstract algebra, what is known about Grassmann variables: anti-commuting (t_i t_j = - t_j t_i), how large matrices are needed to realize them?

While physicists like them (fermionic fields), mathematicans seem unaware, there is probably no deeper theory?

I am asking because being able to realize them (in non-exponential cost), we could solve Hamilton cycles in P ...

Grassmann number

In mathematical physics, a Grassmann number, named after Hermann Grassmann (also called an anticommuting number or supernumber), is an element of the exterior algebra over the complex numbers. The special case of a 1-dimensional algebra is known as a dual number. Grassmann numbers saw an early use in physics to express a path integral representation for fermionic fields, although they are now widely used as a foundation for superspace, on which supersymmetry is constructed. == Informal discussion == Grassmann numbers are generated by anti-commuting elements or objects. The idea of anti-commuting...

Thomas Klimpel

12:45 PM

(I still want to finish other stuff and later (quite soon actually) meet friends.) If you want to know what is known already, then at least for GI there is a good chance that I can help. However, you were not really thrilled when I told you that you are reinventing stuff. And when I told you that your newest approach might indeed by new, you didn't care either. For algebra in general, there are other people at math.se and mathoverflow much more qualified than me to answer your query.

Even for GI, Joshua Grochow might be more helpful than me, you can find him here on cstheory.SE.

Thomas Klimpel

12:58 PM

...

My motivation for being blunt is not to hurt you. I saw that you found Craig Gidney in order to discuss details of quantum computing, and I just thought that I might be the analog of Craig Gidney for GI, in case you like to discuss details of GI. For me, being flattered when Peter Shor answers one of your question is something different than discussing details with Craig Gidney, even if you don't know much about his credentials.

...

Jarek Duda

Thank you, I really value contact with you, especially seeing your experience with GI

Thomas Klimpel

And when I talk about WL, the intention is to show how one could create a concrete story about a new approach to GI, even if one cannot prove that it is in P. Even if it fails completely, if it is sufficiently new (and well defined), it can still be interesting to compare it to WL, both practically (i.e. by using the counter-examples to k-dim WL as test cases) and theoretically.

Jarek Duda

I see these fields as being dominated by combinatorics, abstract algebra focused people - so I am trying to attack them from very different perspectives

WL is natural combinatorial approach ... but I haven't seen approaches based on eigenbases earlier - which are very different, directly base on global structure of graph (egenvectors), not local like WL ... it seems new and promising, and I am open for a collaboration ...

vzn

3:40 PM

@ThomasKlimpel CG is working at google now and has great credentials. trying to remember, where did his name come up? on a reply to JDs questions? not understanding the point you seem to be making about CG vs PS.

vzn

3:52 PM

youve been talking about WL so long, decided to do a minisearch on it, just turned up 3 nice/ great refs. esp like the empirical angle. have you seen any of these? it would be great if you wrote up a list of your own favorite papers.

arxiv.org/abs/1101.5211

simons.berkeley.edu/sites/default/files/docs/5854/…

jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf

seems to be spelled both Weisfeiler-Leman and Weisfeiler-Lehman. 1968

seems to be randomized coloring algorithm.

wondering what Babai has said about it, do any of his papers connect to it? esp his recent breakthru O(polylog(n)) GI algorithm.

am esp interested in empirical attacks, think it is well suited for that. an obvious setup would be to try to code up adversarial algorithms which try to construct hard instances for WL, but on quick search do not seem to see that at all yet.

@enumaris what field do you want to get a job in? are you open to relocation? are you currently in CA? are you aware of recent very high demand/ rates for ML data scientists? its a phenomenon... have you thought about/ considered Deepmind?

WL-GI algorithm/ problem reminds me of SAT. by analogy suspect there would be some basic transition point phenomenon/ phenomena...

in fact have long thought that SAT solution seems to be related to GI as some kind of "subroutine" ie seen in the "intrinsic GI" of different SAT formulas on the input... maybe someone has pointed this out/ expanded it but havent seen it much. it seems natural that an optimal SAT algorithm might (even provably?) have some kind of GI-like preprocessor.

any idea, is WL used in nauty?

superficially it reminds me/ seems to have some similarity to some O(n log(n)) FSM minimization algorithms.

afaik the FSM algorithms can also be said to work thru "refinement" (of partitions)...

a natural/ basic question for WL is how often the "same graph" gets "different results" based on probability. and presumably there would be a strong connection between this rate and the "intrinsic hardness" of the graph.

a key parameter these days with graph algorithms (complexity) is treewidth. how does WL relate to it?

enumaris

5:15 PM

@vzn actually I have been applying for a lot of data science positions which utilize ML, I have seen that it is the hot thing right now haha.

I haven't considered deepmind though since they are a English company.

Transcript for