espeed

Direct link (PDF): https://zenodo.org/record/2565243/files/stream-ring-theory.p...

Here's part 1 of Prof Knuth's 2007 interview by the ACM in honor of his 1974 Turing Award (it's the interview that ended up going on for more than 7 hours over 2 days). It's in a conversational style on life topics that are familiar and relatable to most.

Don Knuth, 1974 ACM Turing Award Recipient - Part 1 [video] https://www.youtube.com/watch?v=vUJ01nRE7r0

Transcript: https://amturing.acm.org/pdf/KnuthTuringTranscript.pdf

Stuttering is not the right word. I'm not a speech specialist, but stuttering and stammering are not the right words. It's something else.

Have you ever noticed how some of the world's smartest people have a somewhat jerky stop-and-go speech pattern, sort-of like Google's autocomplete? It's not uncommon among smart people who are careful about what they say, strive for precision, and are cognizant and empathetic to potential contextual gaps among their audience and their different levels of understanding.

Elon Musk has a similar pattern, but it's not so much a speech disorder as it is their brain is working so fast, pulling from multiple sources and considering multiple perspectives. They're auto-editing their words in real-time, revising what they're saying while considering all of the above factors and more. But sometimes they get ahead of themselves and so in an effort to be clear and precise, they backtrack a few words and rephrase, filling-in as they anticipate potential contextual gaps. This is what you're seeing.

Rather than thinking they need to see a speech therapist, view it as a mark of authentic speech by someone who strives for precision and is empathetic to their audience. When you look at it this way, you can know and appreciate that you're witnessing the genuine workings of a brilliant mind.

These videos were just released yesterday from the Stanford archives in honor of Prof Knuth's 81st birthday so there may not be higher resolution versions available. Maybe this is a subtle call to some aspiring hacker to re-res them with a super-resolution deep learning algorithm. What a cool gift to the world that would be.

For those closer to the hardware with insight into the emerging architectures and market dynamics, how far away is AMD/Intel/IBM/Google from catching NVIDIA from a technology perspective, and does NVIDIA have a defensible competitive advantage now that market forces have moved well beyond gaming and shifted US strategy toward a spending spree of buying up all IP?

Yeah, and areas of that "wind belt" can get pretty violent at the extremes. It includes Tornado Alley [1], which we got to experience in full force in 2017. The house got hit by a mile-wide EF4 tornado. We were fortunate -- it only took half the house and one of the vehicles -- but the three houses around the corner were left to slabs, swept clean as the day the foundations were laid -- and hundreds of heads of cattle from the surrounding ranches were just gone -- no one ever figured out where they landed; however, other items were discovered 50 miles away. That was a crazy day.

[1] https://en.wikipedia.org/wiki/Tornado_Alley

Texas has $1.8 trillion economy [1], which is the 10th largest economy in the world. To put that in perspective, the Texas economy is ~$500 billion larger than the entire Russian economy [2]. Texas is called the energy capital of the world for good reason, but the energy market is massive -- it includes much more than oil -- and the Texas economy overall is way more diverse than that [3]. It is tied with New York with 52 Fortune 500 corporations headquartered in Texas, only California has more with 54. What happened in Detroit is unfortunate, but Texas is not Detroit. That would be like comparing Dallas to Detroit in the NFL - they both wear silver and blue and they both play on Thanksgiving Day, but they are on polar opposite ends of the spectrum in every other conceivable way.

[1] https://www.forbes.com/places/tx/

[2] https://en.wikipedia.org/wiki/Comparison_between_U.S._states...

[3] https://en.wikipedia.org/wiki/Economy_of_Texas

Yes, the original title of the post included Nobel Minds 2018, but it was modified to emphasize the description. I discovered the Nobel Minds series a few years ago. I think last year's was better, but I agree, the episodes can be hit or miss. They should let Joe Rogan do the interviews -- he's been interviewing a bunch of leading scientists of late (Sir Roger Penrose a couple weeks ago) -- Rogan's our modern day Charlie Rose -- he let's them talk and it evolves into interesting conversations.

Here's the resulting visualization of the 11 maps and the relationships between the 187 unique mathematical structures, including a detailed 47-page catalog describing the properties of each...

Map Map [pdf] http://www.mit.edu/~kepner/GravelMathMap.pdf

...or GANFAM to better emphasize a more healthy spirit of competition and collaboration.

No. Incorrect on all levels. You can do declarative with both, or take a procedural approach with both. You can use SQL or Datalog with both. You can create views with both, materialized or otherwise. Graphs have never been obsolete. Graphs and the networks they represent are the foundation for some of the most sophisticated algorithms we know.

GANMAF

Yes, a lot of innovation had to occur to make the GraphBLAS linear algebra model practical, which has been in the works for more than 10 years. It began with Jeremy Kepner and John Gilbert's work formalizing the linear algebra model over semi-rings [1]. And then working with Intel, IBM, Nvidia and the other hardware vendors to define and implement a standard set of hardware primitives. But you could really see the stars align a few years ago then when the deep-learning ML wave hit because it paved the way with a surge in demand for GPU/TPU accelerators in the data center. A lot of things had to happen in to make this all come together. It's been an industry-wide effort.

[1] Graph Algorithms in the Language of Linear Algebra, by Jeremy Kepner and John Gilbert https://epubs.siam.org/doi/book/10.1137/1.9780898719918

IBM also has a GraphBLAS [1] implementation in the works [2], and this summer Jenna Wise [3], a PhD candidate at CMU, spent the summer at IBM working on a formal verification proof of the GraphBLAS code [4].

[1] http://graphblas.org

[2] IBM GraphBLAS https://github.com/IBM/ibmgraphblas

[3] Jenna Wise, CMU http://www.cs.cmu.edu/~jlwise/

[4] Formal verification proof of the GraphBLAS C API https://github.com/jennalwise/graphblas-verif

Here's the Redis Day London Nov '18 launch video [1] of RedisStreams and RedisGraph 1.0 GA [2] -- their benchmarks show it to be up to 600X faster over previous-gen graph DBs [2] (and that's before the coming parallel/distributed GraphBLAS GPU implementations that are in the works)...

[1] RedisGraph 1.0 launch video https://www.youtube.com/watch?v=S5WWBzi0LcM

[2] RedisGraph 1.0 https://github.com/RedisLabsModules/RedisGraph

[3] RedisGraph benchmarks https://redislabs.com/redis-enterprise/redis-modules/redis-e...

And it's not just graphs...as referenced in the linked comments above, there are now linear algebra models that encode Datalog and/or the entire typed-lambda calculus as linear algebra matrix operations (and as shown in the Datalog paper [1], the Datalog linear algebra implementation is the fastest Datalog implementation to date).

But MIT and Sandia Labs are taking the linear algebra model to the next level, and are now working on encoding an entire operating system in the language of linear algebra...

Jeremy Kepner (the head of MIT Lincoln Labs and GraphBLAS lead) and his team just published a paper [2] where they define an entire unix operating system using the same linear algebra model as they used for D4M/GraphBLAS. The linear-algebra OS model scales linearly way beyond the Linux limits, and since the entire OS kernel representation is defined as generic matrix transformations, it can run on any processor, including CPUs, GPUs, or a cluster of TPUs.

[1] A Linear Algebraic Approach to Datalog Evaluation (2017) [pdf] https://arxiv.org/abs/1608.00139

[2] TabulaROSA: Tabular Operating System Architecture for Massively Parallel Heterogeneous Compute Engines (2018) [pdf] https://arxiv.org/pdf/1807.05308.pdf

New graph DBs implemented with the GraphBLAS linear algebra model will be orders of magnitude more performant than previous gen DB models. RedisGraph 1.0 is the first public GraphBLAS database implementation. And things are about to get even faster with the GraphBLAS GPU implementations in the works.

See previous discussions on GraphBLAS https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&pr...

There's a new Datalog [1] implementation written in the language of linear algebra (similar in nature to the ideas behind GraphBLAS [2] "graph algorithms in the language of linear algebra"). Evidently the linear-algebra approach works well for Datalog too -- the paper below shows it's the fastest Datalog implementation to date, several orders faster than the best Prolog engines.

NB: GraphBLAS runs in the recently-released RedisGraph. The Datalog linear-algebra approach is so close to simi-ring primitives in GraphBLAS. A Datalog implementation on GraphBLAS could be slick as hell. The GraphBLAS code is implemented by Tim Davis, and the code is pristine.

[1] A Linear Algebraic Approach to Datalog Evaluation (2017) [pdf] https://arxiv.org/abs/1608.00139

[2] GraphBLAS http://faculty.cse.tamu.edu/davis/GraphBLAS.html Discussion: https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&pr...

I'm interested to see how well Halide's approach would pair with the GPU optimizations being put into GraphBLAS [1].

[1] https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&pr...

In addition to this video overview by Andrew Adams from the Stanford course [1], there's also an MSR talk given by Jonathan Kelley [2], and there may also be a Google TechTalk somewhere on YouTube (don't remember for sure so just search for "Halide" or by one of the authors' names).

And of course there's also the videos of lectures of the MIT 6.815/6.865 course on computational photography given by Frédo Durand (those videos are linked to from the Halide home page under the Getting Started section [3]).

[1] Stanford CVPR2015 http://halide-lang.org/cvpr2015.html

[2] Decoupling Algorithms from the Organization of Computation for High-Performance Graphics & Imaging (MSR talk given by Jonathan Kelley) [video] https://www.youtube.com/watch?v=dnFccCGvT90

[3] MIT 6.815/6.865 Digital & Computational Photography lecture videos by Frédo Durand http://halide-lang.org/#gettingstarted

Ron Pressler (the presenter) is an active contributor to HN [1], and he blogs at blogs at https://pron.github.io [2]. There he has a multi-part blog post under the same name as the presentation, and if he chimes in here, he may be able to provide ptrs to additional resources (else ping him on Twitter [3]).

[1] https://news.ycombinator.com/user?id=pron

[2] https://pron.github.io, http://www.paralleluniverse.co

[3] https://twitter.com/pressron, https://twitter.com/puniverseco

Among other optimizations and advancements, Halide provides compiler support for advanced latency-hiding scheduling/optimizations beyond the capabilities of generic compilers, which essentially enables you to generate highly-parallel optimized CPU/GPU compute kernels to make memory accesses free.

See Halide, a latency-hiding scheduler/compiler for GPUs and CPUs...

Halide: a language for fast, portable computation on images and tensors http://halide-lang.org/

Three years ago I got a similar call to build a user-facing knowledge graph for the region. Effectively replicating Freebase, backed by the regional telecom and the Royal Family. It was likely the same group that approached you because I was approached in precisely the same way.

Have you heard that Idris 2 is implementated in Scheme, and runs faster than when it was on the GHC. Check out Edwin's tweet stream, he's loving Scheme and can't stop raving about it. The idea of Idris on Scheme is so sweet and surreal it's got to be to the combo of the year.

For more on trits, see Mihai's 2010 paper...

An Alternative to Arithmetic Coding with Local Decodability (2010) [pdf] http://people.csail.mit.edu/mip/papers/trits/paper.pdf

Changing base without losing space (2010) [pdf] https://dl.acm.org/citation.cfm?id=1806771 (same paper as above, different title)

"The ternary numeral system (also called base 3) has three as its base...a ternary digit (trit) is analogous to a bit. One trit is equivalent to log2 3 (about 1.58496) bits of information" [1].

NB: Base 3 is the integer base with the lowest average radix economy; however, base e has the lowest average radix economy overall [2].

[1] Ternary numeral system https://en.wikipedia.org/wiki/Ternary_numeral_system

[2] Radix economy https://en.wikipedia.org/wiki/Radix_economy

[3] Three-valued logic https://en.wikipedia.org/wiki/Three-valued_logic

Good recommendations. In addition to the UT, MIT and Stanford courses you recommend above, for developing your visual intuition, 3Blue1Brown's Essence of Linear Algebra video series is second to none. [0]

Another good one is MathTheBeautiful [1] by MIT alum Pavel Grinfeld [2]. He approaches Linear Algebra from a geometric perspective as well, but with more emphasis on the mechanics of solving equations. He has a ton of videos organized into several courses, ranging from in-depth Intro to Linear Algebra courses to more advanced courses on PDEs and Tensor Calculus.

Esp note his video on Legendre polynomials [3] and Why {1,x,x²} Is a Terrible Basis: https://www.youtube.com/watch?v=pYoGYQOXqTk&index=14&list=PL....

Gilbert Strang was Greenfield's PhD advisor: https://dspace.mit.edu/handle/1721.1/29345. Pavel has a clear and precise teaching style like Strang, and he makes reference to Prof's Strang and his MIT course from time to time.

NB: Prof Strang has a new book Linear Algebra and Learning from Data that just went to press and will be available in print by mid Jan 2019. A few chapters are available online now, and the video lectures from the new MIT course should on YouTube in a few weeks. [4]

[0] Essence of Linear Video Series (3Blue1Brown): https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw/pla...

[1] MathTheBeautiful https://www.youtube.com/watch?v=pYoGYQOXqTk&index=14&list=PL

[2] https://en.wikipedia.org/wiki/Pavel_Grinfeld

[3] https://en.wikipedia.org/wiki/Legendre_polynomials

[4] MIT Linear Algebra and Learning from Data (2018) http://math.mit.edu/~gs/learningfromdata/

Yes, thanks -- my browser glitched and auto-posted before it captured the URL...

http://www.axler.net/DwD.html

NB: Rosette 3.0 has been released: https://github.com/emina/rosette/blob/master/NOTES.md

Also, the 2017 Clojure/West talk "Synthesis and Verification for All" [1] presented by UW Prof Emina Torlak (Rosette's creator) is one of the best talks I've seen in a while.

Synthesis and Verification for All, Emina Torlak [video] https://www.youtube.com/watch?v=KpDyuMIb_E0