Rupert Brooks will present Dual Contouring of Hermite Data by Tao Ju, Frank Losasso, Scott Schaefer, Joe Warren.
I'm going to remind everyone to review the PWL social rules (which are the Recurse Center's social rules) before the next meet-up so we can end the year on a high note. We also use their code of conduct.
Hanneli Tavante will present Ideal Theory in Rings by Emily Noether
[Translated by D. Berlyne]
Mixing concepts from mathematics, history and programming, this presentation will sum up some of the main ideas of 'Ideal Theory in Rings', written in 1921, and propose a different approach for thinking in abstractions when writing code.
Emmy Noether played an important role in the formalization and definitions of abstract algebraic structures. Programming is closely related to abstraction and we can use some of the ideas in this field to write better programs. This paper will bring some concepts of modern algebra categorized by Noether, such as many types of rings, groups and others. After a set of definitions, we will see an example of an application in code (in Python, Ruby, Haskell or Scala).
Julian Squires will present "Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems" by Zhang and Shasha, which he once used for implementing a structured version control system in XML documents.
He'll also discuss later work on tree edit distance and alternative approaches to structured version control.…
Mathieu Guay-Paquet will present Kiveris et al's Connected Components in MapReduce and Beyond. As I understand it, there'll be a bit of a war story here, about improving the efficiency of a Spark job that computes connected components, originally with GraphX. Correspondingly, Mathieu will talk about Spark and RDDs, starting with what I think is the original RDD paper, then GraphX, and then some actual distributed connected components approaches.
I think anyone interested in how Spark works, or doing computations on large graphs, will find something of interest here.
He wrote me a nice list of the papers and comments which I will reproduce exactly (modulo meetup.com's strange formatting):
1. This one is a very nice overview of the way Spark and its main data structure, RDDs, are meant to be used, with enough implementation details to understand what's going on. It's probably a very goo…
Suchakra Sharma will present McCanne and Jacobson's "The BSD Packet Filter: A New Architecture for User-level Packet Capture". This is very exciting not only because of the applications of the original BPF, but also the more recently developed eBPF which has become a crucial part of modern Linux kernels.
Incidentally, aside from the paper, and all the recent interesting work on eBPF (check out Brendan Gregg's page on eBPF, Quentin Monnet's page), I recommend reading the code for the BPF optimizer from libpcap (optimize.c) — to me, it's a great, simple example of some classic compiler optimizations, that's easy to understand because of how simple the VM is.
Marianne Corvellec will present Evaluating Collaborative Filtering Recommender Systems by Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen, and John T. Riedl.
What's better than a survey paper? Perhaps this paper that proposes a methodology for evaluating many different approaches, and then gives some empirical evaluations while giving us, also, a bit of a tour of the literature on recommender systems.
Added to that, our speaker used this paper in an implementation, so it's two of my favorite kinds of paper situations in one!…
Brendan Cordy will present Bos et al.'s "Elliptic Curve Cryptography in Practice". Aside from the already interesting contents of this paper (which discusses Bitcoin, SSH, TLS, and the PS3's famous security failure, among other things), he will show some code to demonstrate elliptic code arithmetic, ECDSA, and querying the blockchain.…
Rupert Brooks will present "Convolution-Based Interpolation for Fast, High-Quality Rotation of Images", by Unser et al. This paper considers a long line of methods for performing image rotation by factoring the rotation into two or more 1D transformations, and addresses the question of how to perform those 1D translations in the highest quality way.
While several authors have proposed these types of decompositions for image rotation, the paper by Paeth (A Fast Algorithm for General Raster Rotation) is one of the most commonly applied. (Also revised and updated as article III.6 in the original Graphics Gems.) It may be helpful to read that paper in preparation for this one.
The presentation will include digging into some open source packages to see what they actually do.…
I will present Hashed and Hierarchical Timing Wheels by Varghese and Lauck. This is the basis for pretty much every operating system's timer facility, and has an important role in distributed systems. (As usual, Adrian Colyer's writeup of this paper is great; see also the subsequent discussion of GD-Wheels.)
Remi Attab will be presenting McKenney and Slingwine's Read-Copy Update: using execution history to solve concurrency problems (RCU), and Desnoyers et al.'s User-Level Implementations of Read-Copy Update.
Everyone interested in concurrency or systems programming should certainly attend! Be sure to check out McKenney's series of articles on RCU on lwn.net.
Please note this meetup is at the new AdGear offices and that building is still under construction, so finding the temporary entrance is a little tricky. I've updated the Google Map marker to indicate the back entrance (on rue de Longueuil between Notre-Dame and Saint-Maurice), whereafter one can follow the signs up to the office.…
Rishi will discuss dynamic time warping, covering several papers, including "FastDTW: Toward Accurate Dynamic TimeWarping in Linear Time and Space" and
<a>"Computing and Visualizing Dynamic Time Warping Alignments in R : The dtw Package"</a>. Rishi also indicates a significant part of presentation will come from Chapter 4 of Rabiner L, Juang BH (1993). Fundamentals of Speech Recognition. Prentice-Hall, Upper Saddle River, NJ, USA. See also Sakoe and Chiba, which started it all.
For some motivation, check out the excellent presentation linked in the conversation below!
Please note that Keatext have kindly offered to host us this month.
Also, this is the two year anniversary of PWLMTL!…
Richard Kallos will present A Nanopass Framework for Compiler Education, touching also on A Nanopass Compiler for Commercial Compiler Development, with reference to the recently open sourced Chez Scheme.
I'm excited about this presentation because we will actually spend some time in the guts of Chez Scheme, which is a high-quality production compiler.
Aside from the compiler aspects, I think there's also an interesting software engineering case study here, as this describes a drastic refactoring of a large commercial software product.
Lovers of Lisp and those curious about compiler implementation should certainly attend.
Please note that since AdGear is moving offices soon, the venue is slightly uncertain. I will make an announcement if the venue changes.…
Soufiane Khiat will present papers on the state of the art in material description: https://eheitzresearch.wordpress.com/240-2/ and possibly also https://drive.google.com/file/d/0BzvWIdpUpRx_dXJIMk9rdEdrd00/view
This should be a good follow-up to Jeff's talk on Metropolis Light Transport. Those interested in graphics, physics, or probabilistic methods should certainly attend! I'm sure there will be interesting implementation details, too.
If you aren't sure where to start with these papers, try sections 4 (Insight and Overview) and 7 (Random Walk on the Microsurface) of the first paper.…
Raimi Rufai will present A Streaming Algorithm for the Convex Hull. Although this is his own work, it is an elegant algorithm with a clean, concise paper.
Unfortunately I haven't gotten the chance to finish my own implementation of it, but I invite everyone to read the paper, as it's short, and I expect the discussion tonight will be very interesting. Whether you're already a big fan of computational geometry, or you're wondering "what is a convex hull?", or you're wondering "is there any use for a convex hull outside graphics?", you should come to this one.…
If you can, it's worth tracking down the cited article by Johnson and Mizoguchi that describes a selection algorithm used in the medcouple algorithm. Unfortunately it does not appear to be freely available on the web. However, the wikipedia article for the medcouple has an excellent exposition which includes a good description of Johnson + Mizoguchi, which is elided from the paper.
Jordi has provided the following description for the talk:
Identifying outliers is a delicate but common statistical problem. One of the most basic definitions of an outlier is given by familiar b…
Elena Vlasenko will present Farsiniamarj and Haarslev's Practical Reasoning with Qualified Number Restrictions: A Hybrid Abox Calculus for the Description Logic SHQ.
A lot of the terminology here is specific to Description Logics, and I found this paper, A Description Logic Primer, to be useful in getting a handle on what was actually happening in the featured paper. Also, as the paper is rather long, one might consider skipping to section 5 after reading the introduction on one's first pass through it.
Elena indicates that she has used this paper heavily in her own work, so I will leave it to her presentation to explain and justify it.
This should be of particular interest to those with an interest in the semantic web, logic and automated reasoning, or applications of integer linear programming.…
You might find that Veach's thesis covers more background and has more details.
If you are interested in ray tracing, computer graphics, sampling, or probabilistic methods at all, you should definitely attend!
I'll end with a tantalizing quote from Veach's thesis, the section "Why Light Transport is Important":
One of the main goals of light transport algorithms is to increase human efficiency in the modeling of realistic virtual environments. [...] The main problem is that the algorithms…
Jeremie Lasalle Ratelle will present Abstract Interpretation by Cousot and Cousot, one of the most cited papers in compilation (and one of the 10 papers that all PhD students in programming languages ought to know).
This is the classic paper that unified previously ad hoc techniques in compilers and gave birth to modern concepts of static analysis. (It's worth comparing it with one of its major predecessors, Gary Kildall's earlier work.) The focus will be more on the concepts and their practical implications than on the details of lattice theory.
Jeremie will also talk about how static analysis evolved since this paper, and the use of these techniques in practice. Originally he was going to prese…
I'm a huge fan of Daniel Lemire's work on compressed bitmaps, sorted sequences of integers, and other data structures. I'd say half the papers I have on my desk at work right now have his name on them. I've invited him to speak at PWLMTL on his own work, rather than on a paper he loved, because I love his papers: I find them to be practical and accessible to the working developer in a way that few academic works manage to be.
He's going to speak about compressed bitmaps, in particular the Roaring bitmap approach he first published in this paper (cited below).
The bitmap, especially in compressed form, is a very versatile data structure despite its apparent simplicity, and I invite all developers to consider it for many purposes.
Just recently, I used compressed bitmaps in an application which needed to represent large sets of IP addresses efficiently. In the last few years, I've used them in…
I will present Browne et al.'s "A Survey of Monte Carlo Tree Search Methods" along with some discussion of the application of MCTS to fuzzing, test generation, and procedural content generation. Some of these aspects can be seen as a followup or tangent to my presentation last year on shape grammars and procedural modeling of buildings.
MCTS has been enjoying a lot of interest for its success in playing Go, but it generally has a lot of applicability in search problems where coming up with good heuristics in advance is tricky.
The paper, being a survey paper, is pretty long; if you just want to get the general idea, read sections 2 and 3, which introduce MCTS, UCT, and the ideas leading up to them. (Including the minimization of regret; and wh…
Chris Diggins will present A Short Cut to Deforestation (1993) by Andrew Gill, John Launchbury, Simon L Peyton Jones.
"Lists are often used as "glue" to connect separate parts of a program together. We propose an automatic technique for improving the efficiency of such programs, by removing many of these intermediate lists, based on a single, simple, local transformation. We have implemented the method in the Glasgow Haskell compiler."
Christopher Diggins is a Principal Developer at Autodesk and designed the MCG visual programming languge in 3ds Max 2016. He has an unhealthy obsession with programming languages.…
David Rowley will present Claude Shannon's "A Mathematical Theory of Communication" (later renamed The Mathematical Theory of Communication once its importance was recognized). This is a pretty hefty paper (anywhere between 49 and 55 pages depending on the printing), but so foundational in our field. David says:
My big interest is the discovery process by which Claude Shannon managed to "synthétiser / put it all together coherently and sequentially." Shannon took a lot of what was known in tidbits here and there and put it into a "one paper is all you need to read" kind of document.
I think that's a good reason to love this paper in particular. I hope that in the discussion we can hear all your perspectives on how Shannon's work continues to directly affect our work and many other areas.
I'll have some comments on this in relation to my o…
Bahar Sateli will present "Towards Robot Scientists for autonomous scientific discovery" by Sparkes et al. (PDF), which looks fascinating. Anyone interesting in planning, AI, even proof systems, should certainly attend. As per the last meetup, we will have pizza (I am open to alternative food suggestions; hopefully we will have the food before the talk, this time).…
Maxime Chevalier-Boisvert will present Soman and Krintz's paper, "Efficient and General On-Stack Replacement for Aggressive Program Specialization". Maxime had the following to say about the paper:
I am very excited about having an interesting compiler paper presented at PWLMTL, and I'm sure all you compiler design afficionados will enjoy this one. For those who don't think they're interested in compilers, consider how insight into JIT optimizations can help you reason about the performance of all…
Julia Evans will present <a>Machine Learning: The High-Interest Credit Card of Technical Debt</a>. After a number of talks about the wonders of machine learning, it's going to be nice to have a paper about the caveats, particularly the maintainability of such systems in production. I'm sure there will be lively discussion of this one, so bring out your best anecdotes!…
Rishikesh will present An Elementary Proof of a Theorem of Johnson and Lindenstrauss by Dasgupta and Gupta, with additional material from Ailon and Chazelle's The Fast Johnson-Lindenstrauss Transform and Approximate Nearest Neighbors.
The Johnson-Lindenstrauss Lemma is pretty awesome, and with the advent of the Fast Johnson-Lindenstrauss Transform this has become a practical tool for dimensionality reduction, approximate nearest neighbors, collision detection, among other things. There are applications for everyone who's dealing with the curse of dimensionality, from machine learning to realtime videogames.
Note that …
Peter Zion will present two great papers on deep learning; first, Yann LeCun’s seminal 1998 paper, "Gradiant-Based Learning Applied to Document Recognition", which will give some background and context for Krizhevsky, Sutskever, and Hinton's 2012 paper, "ImageNet Classification with Deep Convolutional Neural Networks", in which (to quote Peter), "they [...] create a GPU-based DNN that is better at image recognition than any human".
Given the length of the first paper, I recommend reading Krizhevsky's paper in detail, and skimming LeCun's paper as needed for background.
Everyone interested in machine learning, image processing and recognition, or GPU computing should come!
This event is part of Big Data Week. Be sure to check out the rest of the schedule!
Finally, a huge thanks to the folk…
Pablo Duboue will present "Structural Zeros versus Sampling Zeros" by Mohri and Roark; this looks like a fascinating paper with applicability to improving all kinds of probabilistic models. He will also be talking about the specific application of this idea to probabilistic context-free grammar (PCFG) parsing as discussed in another Mohri and Roark paper, "Probabilistic Context-Free Grammar Induction Based on Structural Zeros". Anyone interested in machine learning, natural language processing, parsing in general, even automated test generation and model checking, or all kinds of other topics should definitely attend!
I apologize for the delay in announcing this meetup. I was in Toronto checking out their PWL chapter to hopefully borrow some ideas (and speakers!) and lost track of time.
Note that since Radialpoint have kindly offered to host again, and th…
Guy Dumais will present "Learning to Rank with Multi-Aspect Relevance for Vertical Search" by Kang et al., which presents machine learning approaches to ranking the results of a query based on an aggregate of metrics whose combined weight is not well-defined.
While the relevance of this to people involved in machine learning or targeted search is clear, I would imagine there will be interesting discussion for anyone who has to deal with problems where heuristics are hard to come up with ahead of time.
Radialpoint have kindly offered to host the meetup this time.…
Christian organizes the Haskellers Montréal meetup which is well worth checking out!
(This is a tentative date; feel free to let me know if another date would be better. )…
I'm going to talk about shape grammars (split grammars, place grammars), in particular their application to procedural 3D content generation as presented in the paper "Procedural Modeling of Buildings" by Müller, Wonka, et al. This was a landmark paper (along with the 2003 "Instant Architecture") that is still the state of the art in some ways. There might be some digression into general grammar-driven generation, especially for automatic test generation, since it's a broad and interesting topic.
The primary paper I'll be discussing is available at
The author's site,
Peter Zion will present the paper ScatterAlloc: Massively Parallel Dynamic Memory Allocation for the GPU.
Autodesk have kindly permitted us to use their space for this meetup.…
(Sorry, this got munged by meetup.com the first time around)
I will present a paper I love (exactly which one is still pending; I will announce it and send out a copy shortly), and we can discuss papers we'd love to see presented and what the future of this meetup will be.
The venue for this meetup is http://tangosocialclub.ca/…