Aaron Levin will present J. O. Smith's "Digital Audio Resampling Home Page," (https://ccrma.stanford.edu/~jos/resample/resample.pdf) itself an expanded version of J. O. Smith and P. Gossett's “A flexible sampling-rate conversion method" (Proc. 1984 Int. Conf. Acoustics, Speech, and Signal Processing) and its associated implementation in libresample (https://github.com/minorninth/libresample) as used in Audacity and other audio software.
This paper introduces the concept of "resampling" audio signals and an algorithm to perform it. Sound, as it comes out of your speakers, has a peculiar digital representation. It's a sequence of values between -1 and 1. The number of values in your sequence is determined by the "sample rate". A higher sample rate means more values and a higher quality representation. It's helpful someti…
Zhentao Li will present "Sikuli: Using GUI Screenshots for Search and Automation" by Yeh, Chang and Miller.
Sikuli is a tool for automating repetitive tasks through GUIs. To automate a program, it makes use of screenshots and image recognition to decide where to click and type. Tasks are scripted in Python using Sikuli's IDE which makes taking and viewing screenshot easy. Using screenshots gives the user a more natural flow from manual task to automation, and provides the same API across multiple programs.
The paper also present a screenshot based search engine but the presentation will focus on the automation portion. I will also show how to reimplement a simple version of Sikuli.
Please note that we are in Café OSMO and not the Clark room this time. The event starts at 6:30pm (instead of 6pm) but Café OSMO is open to the public so feel free to go there earlier.…
Amédée d'Aboville will present Curtsinger and Berger's "COZ: Finding Code that Counts with Causal Profiling" https://arxiv.org/pdf/1608.03676 and its associated implemntation Coz.
This paper introduces causal profiling, a technique to find key parts of multithreaded code and figure out how improvements to these parts would speed up the overall application. The main implementation of this idea is a tool called Coz (https://www.youtube.com/watch?v=jE0V-p1odPg and https://github.com/plasma-umass/coz), which has recently added Rust support.
This paper was the recipient of the Best Paper Award at the Symposium on Operating Systems Principles 2015.
(Note for those at the last meetup, we've shuffled speakers and therefore topics around.)
See you soon at our …
Max Golubev will present Alvaro et al.'s "Dedalus: Datalog in Time and Space" and show us his implementation of it. http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-173.pdf
Keeping the distributed timekeeping theme from last PWL meeting with
hybrid logical clocks, this next meeting will present a different
approach to the problem via Dedalus, a subset of the declarative
Datalog language that nevertheless introduces new concepts such as
negation, aggregate functions, and choice. Together with a successor
relation, this makes Dedalus a suitable modelling language for
communication and synchronisation of a distributed system.
See you soon at our next PWL!…
Richard Kallos will present "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" by Kulkarni et al. https://cse.buffalo.edu/tech-reports/2014-04.pdf
This paper introduces Hybrid Logical Clocks (HLC). They were originally presented as an alternative to Google's TrueTime, a proprietary timekeeping mechanism in Spanner DB based on atomic clocks for totally ordering transactions. HLC works well for partially ordering events in a distributed system, as well as rooting them in wall-clock time, something that Lamport clocks, vector clocks & co. don't do. Several distributed databases have implemented Hybrid Logical Clocks, such as MongoDB, Couchbase, CockroachDB and Yugabyte.…
Sevag Hanssian will present "A Smarter Way to Find Pitch" by McLeod and Wyvill (http://miracle.otago.ac.nz/tartini/papers/A_Smarter_Way_to_Find_Pitch.pdf), which presents a practical algorithm for determining the frequency of a sampled sound (e.g. the note being played by a recorded instrument); an interesting aspect is the algorithm also gives a "clarity" metric. Anyone interested in signal processing, computing with audio and music, and so on should enjoy this.
Sevag has done a lot of work on pitch detection, and some of his code related to this paper and others can be found at https://github.com/sevagh/pitch-detection
Thanks to Evolving Web for hosting us again, untether.ai for sponsoring food and drinks, and everyone in the group for their patience in waiting for this meetup happening aga…
Sam Gélineau will present Conor McBride's "Clowns to the Left of me, Jokers to the Right" (http://strictlypositive.org/CJ.pdf), in which a "dissection" operation is presented, as a generalization of the derivative of datatypes (http://strictlypositive.org/diff.pdf), out of which a bunch of interesting things can be derived, notably Huet's zipper (http://gallium.inria.fr/~huet/PUBLIC/zip.pdf) and Brzozowski's derivative of a regular expression (https://en.wikipedia.org/wiki/Brzozowski_derivative).
Everyone interested in powerful applications of type systems should enjoy this. I recommend reading the zipper pearl before attempting this month's paper, if one hasn't already.…
Marina Chirchikova will present Yang et al.'s "How not to structure your database-backed web applications: a study of performance bugs in the wild" (https://hyperloop-rails.github.io/220-HowNotStructure.pdf). This will be a joint meetup between Montreal.rb (https://www.montrealrb.com/) and Papers We Love Montreal, thanks in part to this fascinating paper analyzing performance problems in Rails applications, although the results are applicable for anyone using an ORM in any language.
Adrien Colyer has a great writeup of this paper at https://blog.acolyer.org/2018/06/28/how-_not_-to-structure-your-database-backed-web-applications-a-study-of-performance-bugs-in-the-wil…
Mathieu Petitpas will present Bernhard and Warinschi's "Cryptographic Voting — A Gentle Introduction" (https://eprint.iacr.org/2016/765.pdf). We have an election coming up so this seemed like as especially apropos topic! Aside from those interested in voting, anyone interested in designing secure protocols with cryptographic building blocks should enjoy this paper.
Thanks again to Evolving Web for hosting us!…
Jordi Gutiérrez Hermoso will present Blanc and Schlick's "X-splines: a spline model designed for the end-user". (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.5770&rep=rep1&type=pdf) A classic computational geometry paper for a change, and there will be code. I think the focus on making these splines "user friendly" makes this paper especially interesting.
It's a shame I can't track down their other paper "X-Splines: Some Additional Results" (reference ) because it appears to discuss some other details (if anyone has a copy, please post a link in the comments).
Thanks to Evolving Web for hosting us this time!…
Edith Viau will present Arrow's original paper, "A Difficulty in the Concept of Social Welfare" (https://www.stat.uchicago.edu/~lekheng/meetings/mathofranking/ref/arrow.pdf), that first presented his well-known eponymous theorem. From a practical point of view, she will talk about applying Arrow's impossibility theorem to the problem of scheduling meetings.
Arrow's theorem (https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem) is one of those fascinating, counterintuitive results that always comes up when discussing voting, but for some completely different applications, I recommend Ryan O'Donnel's Analysis of Boolean Functions (http://www.contrib.andrew.cmu.edu/~ryanod/) [I'll bring a copy of t…
Zhentao Li will present "OMeta: An Object-Oriented Language for Pattern-Matching", from Alessandro Warth's VPRI report, "Experimenting with Programming Languages" (http://www.vpri.org/pdf/tr2008003_experimenting.pdf up to page 40).
OMeta is one of the most practically useful outputs of the VPRI and is of interest to everyone, particularly authors of DSLs, compiler writers, minimalists, and anyone who has had a language-shaped problem (lexing, parsing, pattern matching). The Wikipedia page (https://en.wikipedia.org/wiki/OMeta) and Warth's homepage (http://www.tinlizzie.org/ometa/) both have links to various implementations and example code.
Thanks to Evolving Web (https://evolvingweb.ca/) for hosting us…
Lysiane Bouchard will present Liu and Lane's "Attention-Based Recurrent Neural Network Models for Joint Intent Detection and Slot Filling" (https://arxiv.org/pdf/1609.01454.pdf). A corresponding implementation is https://github.com/HadoopIt/rnn-nlu. The paper itself is short but the references provide more than enough meat. I particularly encourage anyone interested in the implementation of spoken language understanding, speech recognition, or machine learning tasks in general to attend.
I apologize profusely for the delay in bringing PWLMTL back after the December break! Among other things, I got hit hard by the flu, twice, and we had a lot of venue difficulties. We would really like to find a stable, regular venue for PWLMTL, so please contact us (through meetup, or email me at [masked]) if you have a place we can host a meetup that: can f…
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 presen…
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/…