Assignment 2: Related Work

Due: Wednesday, October 9 at 4:00pm. Submit on Canvas.


Doing research means making a novel contribution. Novelty, as we discussed in class, is a litmus test for a research idea: a novel idea is new to the academic literature. To be able to argue for novelty, you need to know what ideas exist in the space. Then, you can articulate a bit flip relative to that prior work to motivate your own project.

This assignment takes you paper-reading skills from Assignment 1 and puts them to good use. You'll be doing targeted reading of a number of papers in order to synthesize the state of the literature and articulate your bit flip. The result will be a Related Work section that you can eventually adapt for your final paper.

This is your first group assignment. You will work on it with your project team, focused around the project you've selected.

Read your nearest neighbor paper

Your TA has provided your team with a nearest neighbor paper for your project. We refer to it as a nearest neighbor because it's the most adjacent piece of literature to the idea that you are pursuing. It's important that you understand it well. Read the nearest neighbor paper, and be able to state in your own words how your project is expanding on, or differing from, the nearest neighbor paper — and why that difference is an important one for researchers to pursue. It might be helpful to do a brief outline for the paper like you did in Assignment 1.

Next, pull out the five most relevant pieces of related work cited in that nearest neighbor paper. This can be a mix of foundational work that is less adjacent to your project but sets the stage, and incremental work that is highly adjacent to the work you want to do. Read each of these papers. You’re not necessarily reading them for every detail; you’re trying to understand how they’re situated relative to the work you want to do. If you can create a brief outline for each paper like in Assignment 1, you probably have it covered.

Expand your literature search

From here, follow citations in the papers you found, or in the nearest neighbor paper, to build out the local neighborhood. Use strategies that we discussed in class:

  • Tracking the influential citations in the papers that you're reading
  • Using Google Scholar's "Cited By" to find more recent papers that cited the one you're looking at
  • Using Google Scholar's "Related articles" to find papers on similar topics, or searching for key keywords and phrases you've uncovered from the papers
  • Using Semantic Scholar's "Highly Influenced" classification to find papers that draw heavily on the one you're looking at

To make your later writing easier, you may want to collect the BibTeX metadata for these papers into a shared Mendeley/Zotero library, or into a shared .bib file in Overleaf. You can typically find the BibTeX through a couple clicks on Google Scholarand on other sites that host papers.

You should get to the point that adding an additional paper is only telling you incrementally more information than you’ve already roughly assimilated. Most likely, you'll start hitting that asymptote after about fifteen papers: often, after this, the ideas will either be more of the same, or will start becoming more distant from your project.

You have a team, so you can split up some of the work here. You may want to split up papers by topic, rather than randomly, so each person is responsible for an area of related work. However, for the next phase, it is critical that you all have shared what you learned with each other, so that you share a collective understanding of the literature and how your project builds on it. You may want to meet up with your team and report back summaries of each paper you read.

Write a Related Work Section

At this point, you have all the raw materials that you need to write a Related Work section of a paper. In addition to being a useful exercise at this point in the project, you will be able to keep what you write for this assignment and adapt it for use in your final paper.

As a first step, perform an affinity mapping of the papers you've collected. With your group, grab some large post-it notes, write each paper on a post-it note, then start placing the post-it notes on a wall or whiteboard so that related papers are near each other. Once everything is up on the wall, take a second pass to re-organize, combine and split groups, looking for shared assumptions or approaches, until you have made sense of the related work.

Use this affinity mapping to organize your Related Work section. Each cluster, typically covering 5 +/- 2 papers, should become one paragraph. In each paragraph, your goal is to summarize what the literature knows about the topic. Order the paragraphs so that they build on each other, typically starting with the high-level motivation of the area, then exploring different approaches or assumptions that have been taken with one paragraph each. You may use one set of subheadings if it's helpful.

Finally, at the end of the related work section (or at the end of each subsection), summarize your bit flip. This means stepping back and asking: what assumption did all of the literature in this section make, and how is our research going to flip the bit flip behind that assumption? You should lay out the bit that's being flipped as a summary of the work in this section, then articulate the flip itself. For example:

Summary Paragraph Explanation
In summary, researchers have pushed for formal validation as a solution to runtime errors in foobars. This error checking typically involves a formal specification of expected behavior, and the use of a computational logic prover to establish the validity of the asserted behavior. Sets up the bit being flipped: error checking via formal proof.
Instead of formal error checking proofs, which are often intractable for non-trivial programs, this research demonstrates that running multiple independent foobars in parallel, and then comparing their outputs, allows a system to catch errors with very high probability and far less programmer effort. While formal proofs are still desirable for mission-critical systems, we argue that this approach scales to far more complex software where formal proofs are not currently feasible. Flips the bit: instead of using formal proof, we run it multiple times and look for empirical disagreement.

If you'd like an example, check out the Related Work section in this paper. It spans pages 2 and 3. Notice that the first few paragraphs of each subsection survey the related work in a narrative way, and the last paragraph articulates the bit flip. Other genres of bit flip argument include: "everyone else's problem setup was slightly different, and our problem setup requires changing the solution entirely", and "similar solutions have been applied in other areas, but not to ours, and require an adaptation to solve our problem".

Apply the following writing heuristics when writing your Related Work section:

  • The citations should be annotations, not proper nouns, in the sentence. In other words, you should be able to remove the citation from the sentence and it should still be readable. Avoid "[5] demonstrated that foobars can be optimized"; instead, "Foobars can be optimized [5]." In addition, it's often counternorm in computer science to name authors, except in CS theory papers. Instead of "Bernstein et al. demonstrated that foobars can be optimized", again focus on reporting the main claim and substantiate it with the citation instead: "Foobars can be optimized [5]."
  • Avoid "various" phrases like "There are various approaches to optimizing foobars [1,2,3,4]." This is an empty calorie sentence that doesn't tell the reader anything. Instead, be slightly more detailed in your summary: "Optimizing foobars requires eating large volumes of tasty instant ramen [1, 3] or pulling all nighters [2, 4]."
  • Your goal is not to bash the related work. It's to summarize (and even celebrate) what's been done, and then articulate how your work extends it. Keep in mind that, when you submit a paper for peer review, the people you're citing are likely going to be reviewing your paper! So keep the conversation productive.
  • You may find LaTeX and BibTeX useful in your writing, because it handles the proper citations for you via the \cite{} command. Stanford has an institutional subscription to Overleaf, which is essentially shared editing (a la Google Docs) for LaTeX. Here's a tutorial for citations with Overleaf.

Your group's Related Work section should be at least 600 words, targeting 600-700 words and at least 15 citations.


Submit a PDF with your Related Work section on Canvas. This is a group assignment; create a group for your team, and one member should submit on behalf of the group.


Your related work will be graded on the following rubric:

  • Completeness: does the related work cover all the most relevant ideas in the literature? (5pt)
  • Synthesis: does the related work combine the work and describe it in a narrative, rather than a paragraph-long list of each paper? (5pt)
  • Bit flip: does the bit flip successfully articulate the assumption in the related work, and this project's bit flip from that assumption? (5pt)
  • Clarity: is the writing overall clear and easy to follow for a technical expert in the field?