ConceptTheory & Algos
Boolean function
A function that maps binary strings of length n to a single bit.
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.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
1Ryan O'Donnell
Lectures that assume it
54The first 12 are shown.
- Boolean Fourier Formulas
- Communication Complexity of Equality
- Analysis of Boolean Functions: Open Problems
- Grover's Algorithm
- Revealing XOR-patterns II
- Random Restrictions and AC0 Circuit Lower Bounds
- Pseudorandom Generators
- Deterministic Communication Complexity
- The Switching Lemma: PRST Version
- Simon's Algorithm
- Majority, LTFs, and the CLT
- Complexity and Computability with Closed Timelike Curves
Connections
62The lectures that define it or assume it, and the concepts next to it.
Lectures56
- The Fourier Expansion and Basic Formulas
- Fourier Analysis of Boolean Functions
- Boolean Fourier Formulas
- Communication Complexity of Equality
- Analysis of Boolean Functions: Open Problems
- Grover's Algorithm
Show 50 moreShow fewer
- Revealing XOR-patterns II
- Random Restrictions and AC0 Circuit Lower Bounds
- Pseudorandom Generators
- Deterministic Communication Complexity
- The Switching Lemma: PRST Version
- Simon's Algorithm
- Majority, LTFs, and the CLT
- Complexity and Computability with Closed Timelike Curves
- Probability Densities and BLR Linearity Testing
- Noise Stability and Arrow's Theorem
- Linial-Mansour-Nisan Theorems
- Level-1 Inequality and the 2/π Theorem
- Håstad's Hardness Theorems
- The Hypercontractivity Theorem
- Multivariate Polynomials and the Schwartz Zippel Lemma
- Razborov Smolensky Lower Bounds for AC0[p]
- Hardness Amplification
- Geometric Structures II
- Dictator Testing and the FKN Theorem
- Invariance Theorems
- Digital Design and Computer Architecture - L1: Intro: Fundamentals, Transistors, Gates
- Computational Models: Circuits
- Revealing XOR-patterns I
- Course Introduction and Overview
- NP-Completeness and the Cook-Levin Theorem
- Restrictions and the Goldreich-Levin Theorem
- Bonami's Lemma and the KKL Theorem
- Probabilistic Computation
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- Hardness vs. Randomness II
- Quantum Query Complexity
- Digital Design and Computer Architecture - L2: Combinational Logic
- Quantum Algorithms Synthesis I: The Hadamard Transform
- The Exponential Time Hypothesis: Foundations of Computational Hardness
- Social Choice and Influences
- Spectral Concentration and Learning
- LTFs and Noise Stability
- Probabilistic Computation, BPP
- Basics of Quantum Computing
- Efficient Algorithms for Reliable Machine Learning
- DNF Formulas
- Constraint Satisfaction Problems
- UG-Hardness Results from Dictator Tests
- What Is "Quantum" About Quantum Computing?
- Machine Learning: Neural Networks and Decision Trees
- Monotone Circuit Lower Bounds
- Probabilistically Checkable Proofs of Proximity
- Majority Is Stablest Theorem
- Analysis of Boolean Functions: Applications in Social Choice
- Quantum Computing Overview