The problem The Survey of Consumer Finances (SCF) is a survey performed by the Federal Reserve every 3 years to gather information about the finances of families in the U.S. It is designed to produce a representative sample of families across various demographics, and so the data can be used to estimate things like distributional properties of income, net worth, savings, etc^[The data that underlies this post is obtained from the 2016 SCF and is viewable here.
Introduction When trying to solve problems with computers, it’s generally important to understand both when and why it is that the problem you are trying to solve is hard. This is ostensibly so that you can be smart about trying to solve this problem in practice (maybe don’t spend a million bucks on AWS credits trying to factor large primes, e.g.), but many people (including myself) think that the abstract analysis of problem hardness is interesting in its own right.