Hacker News Reader

Comment by Zach_the_Lizard | Hacker News Reader

How long until we start seeing this algorithm in Google interviews?

Very long, most CS people don't know any group theory.

Just a week or two ago I saw someone get downvoted for suggesting that many CS degrees don't include real analysis. I suspect that by now undergrad CS programs are all over the place, and I wouldn't dare make broad generalizations about the math content of a CS degree anymore.

I am pretty sure that most CS students don't have the algebra background to understand what's going on in this algorithm. I've taken a year's worth of algebra and the algorithm still relies on stuff that I don't get.

Edit: and most CS programs do not emphasize traditional math anyways. No analysis, some linear algebra, very very little abstract algebra, and that's pretty much it.

My father got a BA in CS that didn't even require calculus. He graduated in the 90s.

I would, because I'm on the inside. There are even many CS degrees that don't require a course in algorithms. You have to remember that most CS degrees come from public/state universities, not Stanford and MIT. And CS students at public/state universities are largely mathphobic.

That's a very broad generalization. There are many public/state universities with amazing CS research and programs (e.g. UC Berkeley) that are very math-heavy.

As a student at UC Berkeley, students need to study at most linear algebra and multivariablr calc to major in CS/EECS.

No Boolean algebra, probability, or statistics?

>There are even many CS degrees that don't require a course in algorithms.

What CS degree doesn't require a course in algorithms? I assume there are some Software Engineering degrees that don't, but how can you spend 4 years studying computer science without an algorithms course?

>And CS students at public/state universities are largely mathphobic.

I agree that most CS students try to avoid relatively proof heavy classes like Automata. But almost all CS courses require up to Calc 2 and discrete math, so I'm sure the truly "mathphobic" students would have majored in CIS or something else.

I also don't think this has anything to do with Standford MIT vs public universities. Students at those Universities would avoid elective proof heavy classes as well. I did undergrad at a relatively unknown state school, and now I'm in grad school in a top ten program. I know plenty of people from both schools who avoid rigorous proof heavy classes when they can.

Here is one such program, North Carolina State University, which requires a basic theory course (automata) but no algorithms course.

https://www.csc.ncsu.edu/academics/undergrad/semester.php

There are many more X state universities that churn out computer science degrees than the top schools.

CSC 316 appears to be the main algorithms course (recommended 4th semester course).

Pretty big generalization there. There are 20+ CSU's and 10 UC's in California. You really going to paint 30 schools with such broad strokes in one state alone, plus the rest of the US?

Most CS programs that I am aware of don't require real analysis. I know Berkeley EECS doesn't, and it's a very rigorous program. Stanford too.

I plan on taking it, but only because it shows up in a few esoteric theoretical machine learning contexts.

Too true, it's one of the reasons why I did a Maths degree to complement my Comp Sci degree.

is that all it's good for?

Nope, it's got useful applications in the real world in, say, chemical compound databases.

This algorithm in its current state really doesn't; GI for most natural instances was already being solved quickly via some heuristics.

This algorithm proves a quasipolynomial upper bound on the complexity of GI.

Er, perhaps.

InChI is already based on nAUTy, which even this work acknowledges as the fastest general approach (except for saucy, bliss, etc).

So there are no implications of László Babai that have an impact on chemistry, AFAICT.

Reply on news.ycombinator.com