theory salon

12:38 AM

@vzn Very tempting. The "Look Inside" previews indicate that the topics which I would like to better understand (p-groups, deriving graph isomorphism from graph automorphism group, cone graphs, ...) are treated, and the book is not too expensive either. But it appeared in 1982, and Luks' algorithm is from 1983. But maybe one of the university libraries in my area has a copy of the book.

Thomas Klimpel

12:56 AM

@vzn Maybe, but some friendly comments by Emil Jeřábek pushed me slightly towards becoming more independent, for example by pushing me to ensure that I have access rights for the libraries in my area, or by giving only the main idea of the answer in a comment, effectively forcing me to workout the complete solution myself.

Thomas Klimpel

1:13 AM

Part of the truth on SE is also that often specific people end up answering all questions from one person in a certain area. For example Joseph Van Name has answered many lattice theory questions for me, and Martin Brandenburg helped me with multiple questions whose answers turned out to be some adjoint functors or a similar category theoretical universal construction.

vzn

1:57 AM

@ThomasKlimpel se reminds me sometimes of churchills legendary quote/ quip about democracy (& note not entirely uncoincidentally how much se's voting relates it to one)...

> its the worst of all possible systems, except for all the others...

so what is your interest in GI? mainly its connection to groups, and/or ...? defn a premiere CS problem in many ways... havent attacked it so much like P v NP but have long been tempted! have dabbled in it over the yrs...

sometimes graphs seem the lingua franca of CS or even more...

maybe even a near-rosetta stone, someday...?

vzn

4:18 AM

3

Q: Google's Deep Dreamer

I was just wondering on a more technical side, if anyone could explain what Google does to create these amazing images from it's deep dream system. Could anyone explain to me in a step by step way, what the program does and how it does it. Many Thanks George

in Computer Science, 5 mins ago, by vzn

↑ not a bad question! many cs angles! state of the art machine-learning and neural-networks research ripped from headlines! killed by the elitists!

@$%& se hardliners/ perfectionists! pointy headed ivory tower academics!

David Richerby

18.9k 5 22 60

complexity-theory algorithms terminology turing-machines computability formal-languages asymptotics

D.W.

24k 3 21 58

algorithms complexity-theory graphs optimization data-structures machine-learning graph-theory

Raphael ♦, Kaiserslautern, Germany

29.4k 9 74 176

algorithms formal-languages terminology computability complexity-theory proof-techniques asymptotics

What research have you done? There are multiple resources out there that explain what's going on at various levels of technical detail. What ones have you looked at? What didn't you understand? What did you find that was or wasn't suitable? We expect you to do a significant amount of research on your own before asking here, and to show us in the question what research you've done and tell us how they did or didn't meet your needs. Sharing your research helps us gives you better answers and helps others as well. See our help center for more. — D.W. 6 hours ago

"How did Google draw these pictures?" is not a computer science question per se. The first step is to ask Google (cf. above comments); then you can ask questions about the used concepts. — Raphael ♦ 4 hours ago

watch the vedio on this page: coursera.org/course/neuralnets — Jake 7 hours ago

Google blog has some posts on this, for example googleresearch.blogspot.ch/2015/06/… and googleresearch.blogspot.com/2015/07/…. — Yuval Filmus 7 hours ago

think this is halfway decent question & was going to work up answer. fyi re DW/Rs objections see should se award As for effort / shog9, meta — vzn 1 min ago

machine-learning application-of-theory big-picture soft-question teaching

experimental image-processing ai.artificial-intel

bioinformatics ne.neural-evol cv.computer-vision

Thomas Klimpel

7:30 AM

@vzn I guess the underlying question is fine, but its formulation as a question about one specific system is not:

> Questions about how a particular piece of software or hardware works aren't science (unless you're asking about the scientific concepts behind that software or hardware).

Thomas Klimpel

8:22 AM

6 hours ago, by vzn

so what is your interest in GI? mainly its connection to groups, and/or ...? defn a premiere CS problem in many ways... havent attacked it so much like P v NP but have long been tempted! have dabbled in it over the yrs...

@vzn Good question. Maybe I just would like to understand it deep enough to have any opinion on the question "Is GI is P?" For example, I'm convinced that "Factoring is not in P", basically because I'm convinced that the set of prime numbers provides a strong source of randomness. But my interest in the connection of GI to groups happened by accident:

6

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

Somebody else had asked a question about the concept of classification (in math) before, which got closed immediately. So I tried to formulate a question which makes it clear that the concept of classification (in math) is far from obvious. I used finite nilpotent groups, because they seemed simple to be. But the problem reduced to finite (indecomposable) p-groups, and I quickly realized that p-groups are far from simple.

Then I found the blogpost The Group Isomorphism Problem: A Possible Polymath Problem? by Dick Lipton, which convinced me that a better understanding of p-groups would be important for making progress on GI.

2

Thomas Klimpel

9:00 AM

But asking "Is p-group isomorphism GI complete?" directly seems pointless, because the question "Is group isomorphism GI complete?" is a well known open question. I could ask "Is p-group isomorphism equivalent to nilpotent group isomorphism?" or "Is nilpotent group isomorphism equivalent to solvable group isomorphism?", but what would I do with the answer?

Joshua Herman

12:13 PM

@vzn GI is hard.... i tried solving it years ago. The thing is is that there is so much noise from chemist saying that they have solved it for special cases....

@vzn It has its own complexity class you should look at that.

@ThomasKlimpel also its a problem which cranks tend to try to do like p=np

@ThomasKlimpel which also increases the hardness of even researching the damn problem...

@ThomasKlimpel Also solving graph isomorphism has a high motivation for people to solve the problem...

Thomas Klimpel

2:35 PM

@JoshuaHerman Do you have any opinion on the question "Is GI in P?" When you tried to solve it years ago, did you try to show that it is harder than integer factorization (or discrete logarithm, or any other problem expected to be outside of P), or did you try find an efficient algorithm for deciding GI?

vzn

3:22 PM

@JoshuaHerman agreed it is a crank magnet but why should that "increase hardness of the problem"? or are you saying something else is increasing its hardness? there is a ton of excellent research on GI, as TK is confirming...

GI/ factoring are both long recognized as "odd problems", they dont fit neatly into the P/NP distinction so far. mysterious. or mystery on top of mystery. note AKS primality in P was a "recent" breakthrough.

TK dont know if you saw this, fyi great reading on group classification thm

in The Blog Room, Jun 24 at 18:50, by vzn

Researchers Race to Rescue the Enormous Theorem before Its Giant Proof Vanishes / sciam

@JoshuaHerman what motivation are you referring to?

vzn

4:10 PM

ICALP/LICS 2015: Christos Papadimitriou on 40 years of TCS / aceto, process algebra diary blog

↑ broad 4 decade survey of CS field highlights & use of "algorithmic lens" on the brain by a hard core senior TCS scientist!

Thomas Klimpel

5:17 PM

@vzn Hey, it took me quite some ingenuity to figure out your name, and now you give it away for free :-(

Joshua Herman

5:46 PM

@vzn it becomes harder to know signal from noise when it is a crank magnet

@ThomasKlimpel my opinion is that it is somewhere in between and we don't have the tools to understand why

Thomas Klimpel

@JoshuaHerman So you think that GI is not in P, but that it should be solvable in polylogarithmic space (like group isomorphism).

vzn

@JoshuaHerman strongly disagree. crank papers are pretty obvious/ transparent. the signal is much different than the noise. there is very rarely any mistaking the two. (a rare exception would be the deolalikar paper, but it was open to question only a few wks or so.)

you guys are both familiar with or have at least heard of ladners thm right?

vzn

6:10 PM

you guys understand that if GI is "really" NPI then any proof of such fact would also almost surely prove P≠NP right?

the general consensus/ educated guess in TCS seems to be that GI is NPI.

TK with all this flirting & dancing around, why dont you try out nauty sometime just for fun? :D

Thomas Klimpel

6:39 PM

@vzn Good idea, might be fun trying to break it.

vzn

@ThomasKlimpel have long wanted to play with it myself but never got around to it.

Thomas Klimpel

6:51 PM

I spend most of my time budget for practical experiments with automated theorem prover software. The TCS people which I meet somewhat regular in person are working on things like modal mu calculus (this is related to PPAD), Isabelle (a generic proof assistant), and graph automata (similar to tree automata).

vzn

@ThomasKlimpel nauty is a thm prover for isomorphism cases :) ... what are you working on proving in ATP? which pkgs?

Thomas Klimpel

7:08 PM

@vzn I use prover9/mace4, the-e-theorem-prover, Isabelle and the TPTP (Thousands of Problems for Theorem Provers) library.

vzn

8:10 PM

@ThomasKlimpel (cool...) are you attempting to prove anything new? convert human readable proofs to machine-readable? etc?

Thomas Klimpel

8:41 PM

Saying "convert human readable proofs to machine-readable" is a nice way of stating it, even so the theorem provers are actually powerful enough to come up with their own proofs. I basically just convert the theorem (or lemma) itself to machine-readable, and see how well the different theorem provers can cope with that, how I can help or influence them, and how to read/interpret their proofs or counter examples.

vzn

@ThomasKlimpel ok. what types of thms? would be interesting to hear more in eg blog post :)

Thomas Klimpel

Of course I use them to check conjectures new to me, because they are so powerful and easy to use. Often I just get a counterexample, which is certainly news for me, but not interesting to anybody else (except in cases where it is a counterexample to a published theorem, but even then I doubt anybody really cares).

@vzn The type of theorems is an extension of my earlier work on inverse semigroups and rings to semirings, i.e. addition is still commutative, but only an inverse semigroup instead of a group.

vzn

9:00 PM

@ThomasKlimpel did you hear of the recent erdos discrepancy problem advance?

vzn

9:20 PM

ps re RJLipton blog, one of my all-time favorites, a public treasure. iirc he got an award citing his blog.

vzn

9:36 PM

@ThomasKlimpel wow, the comments on that are quite lively/ variegated. some of it makes me think an empirical attack might yield something. gowers:

> I very much like the sound of this project, but like you I feel that my group theory is inadequate. One thing I’d like to know is how to get a rich source of non-trivial 2-groups. Without that I have no way of assessing any algorithmic ideas. It would be particularly interesting to have two definitions of 2-groups that resulted in groups that were isomorphic but not obviously so — to get some kind of feel for the obstacles that an algorithm would have to overcome.

could it be "easy" to generate random 2-groups? dunno...

josh zelinsky:

> Group isomorphism is known to be reducible to graph isomorphism, but the reverse direction is not known.

vzn

10:27 PM

Paolo Codenotti:

> The best known algorithm already takes advantage of the extra structure, namely generators. Indeed it gives a quasipolynomial time (n^log n) algorithm for group ISO, whereas the best algorithm for graph ISO is n^\sqrt{n}.

Transcript for