Recent advances in computer science since 2010? | Hacker News Reader

Recent advances in computer science since 2010?

cstheory.stackexchange.com

106 pointsazeemba25 comments

Calling Raft an advance in CS is a stretch. It is an alternate and equivalent reimplementation of Paxos by those who didn't understand Paxos. They did succeed in making a protocol which people have more confidence that they understand--but it still has weird edge cases, so it's a bit dangerous to give people that false confidence.

> some recent advances in computer science from the last decade that have 1) sound theoretical basis, are 2) implementable, and 3) have achieved some level of adoption in the industry (this last criterion is nice to have but not necessary).

Fair enough, but Paxos has all of those things too, despite being extremely hard to grok. I guess "advance" is in the eye of the beholder.

> Paxos has all of those things

Do you realize if that were true then the guy would have never been awarded a PhD for the work?

I’d add practical zero knowledge proof systems to the list.

Local-first web apps are (hopefully) the next frontier for web apps.

One of the technologies that enable this are CRDT's (Conflict-free data types) which apparently was "formally defined in 2011" according to Wikipedia.

Perhaps somebody else could chime in and point out to some popular products using CRDT's that I may not know of.

Worst Case Optimal Join Algorithms.

Tecnically they started in 2008 with the AGM bound, but most meaningfull algorithms have been developed after 2012.

excellent intro to worst case optimal joins: https://justinjaffray.com/a-gentle-ish-introduction-to-worst...

Surprised to see no mention of LLMs, although that's far more recent than 2010.

That's not computer science, that's ML, formally a branch of statistics.

Computer science techniques have been successful in implementing and optimizing the performance of LLMs but CS itself has absolutely nothing to do with the theoretical underpinnings of *why* they work.

So in your opinion There is no CS only math.

Of course not. Don't put words in my mouth.

Computer science concerns itself with computable things, which is a subset and except in very special cases only an approximation of the set of things that math concerns itself with. Making abstract theoretical constructs like ML models and algorithms computable (and representable, and efficient) is where the two intersect, but it's wise for proper understanding not to conflate iterative processes with computation per se, or perhaps more pithily, to confuse the map with the territory.

This comment seems misguided. I am a grad student working with LLMs in a CS department. I promise you CS has (and will have) much to say about theoretical underpinnings of transformers.

I can't see what you might be referring to. Even topics around quantization are fundamentally about information theory and not really computer science per se. It could just as easily be an explanation that your CS department is better-funded and more interested in tackling those problems -- statistics departments tend to be a bit behind the curve in this regard, but that doesn't magically move an entire branch of science somewhere else in the taxonomy.

Maybe if you can explain what you mean instead of merely providing some vague assertion, we could have a real conversation about it. In my experience, though, the hype train around software engineering has incited CS departments to retcon a lot of things as CS-related so that their grant writers have an easier time securing funding.

+1 for metatracing interpreter-jits.

While there's been impressive practical advances recently, the theory dates back to the mid-90s.

Advanced type theory dates back to the 90s too, and yet only now we see it being utilized in mainstream languages more and more

I guess this depends on what you define as "advanced". Many languages still struggle with dependent types and these date back even to the 80s, but I would not say they are "advancing computer science." I agree with the original article that liquid types represent a real recent CS advance (but aren't in any mainstream general-purpose languages yet).

Partial evaluation and meta-tracing, though, were more or less fully understood theoretically by ~2000. What was missing was the enormous amount of tooling and compiler design work needed to support them e.g. Graal, and that in turn preceded by enough work on Java / the JVM to make a project like Graal viable.

Unlike Graal/Truffle, PyPy was done by a very small team.

Dependent types: de Brujin (1967)

Curry-Howard: Curry (1934, 1958), Howard (1968)

MLTT: Martin-Lof (1972)

Polymorphic lambda-calculus: Girard (1972/3), Reynolds (1974)

Effect systems: Gifford/Lucassen (1986)

Calculus of constructions: Coquand/Huet (1988)

HKTs: Girard (1971)

Type classes: Kaes (1988)

Dates are imprecise and from memory.

Could you give me references for this theory of meta-tracing in the 1990s? It seems to me that PyPy was the first to, systematically and in a lightweight way, solve the problem of normal JITs optimising the wrong loop, when JITing interpreter loops.