protected groups are features that one shouldn’t use: as in, these cannot be used:

• race
• color
• national origin
• religion
• age
• sex and gender
• sexual orientation
• physical or mental disability
• reprisal (grudges)

a protocol for a function \(f\) is a pair of functions \(A,B:\qty {0,1}^{*} \times \qty {0,1}* \to [0,1,STOP]\) whereby:

• on input \((x,y)\), we initialize round counter \(r=0\), and initial (empty) message \(b_0 = \epsilon\)
• while \(b_{r} \neq STOP\)
  • \(r++\)
  • if \(r\) is odd, then Alice sends \(b_{r} = A\qty(x, b_1 \cdots b_{r-1})\)
  • else Bob sends \(b_{r} = B\qty(y, b_{1} … b_{r-1})\)
• our function output \(b_{r-1}\), and we call \(r-1\) the number of rounds

protocol cost

the cost of a protocol \(P\) for \(f\) on \(n\) bit strings is:

the fast you are willing to prototype, the more willing you are to fail, the faster you will get to a successful partial solution you can refine and repeat.

how to prototype faster?

In order of decreasing slowness—-

• build out the whole product…
• building the minimum viable product…
• skeleton prototyping (Figma)…
• Pen and paper…
• Talking about it

The trade-off: each level gives increased fidelity: its closer to what will actually ship, so you can get better+detailed feedback.

Coping with NP Completeness

It’s possible to solve NP complete problems!

• average case/worst case complexity: it’s possible to solve SAT for a lot of problems which solves the average case problems (“Heuristics vs. Algorithms”)
• special cases: 2SAT, subset sum, etc. can be solved in very special cases