Sign inSign in

Dictator test

Testing procedures for Boolean functions used in PCP and hardness of approximation to distinguish dictators from quasirandom functions.
as Ryan O'Donnell defines itCarnegie Mellon UniversityThe wording closest to all 3 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Lecturers

2

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Graduate

    A randomized algorithm designed to distinguish between dictatorial functions and functions with small influences.
    • 10:11Majority Is Stablest Theorem
  • John Wright

    Carnegie Mellon University · Research

    A test used in PCP and hardness of approximation reductions to check whether a function is a dictator or far from being a dictator.
    • 15:55UG-Hardness Results from Dictator Tests

Connections

7

The lectures that define it or assume it, and the concepts next to it.

2 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.