Concepts
5,907Terms and methods explained by more than one lecturer. Each opens at the minute it is taught.
Theory & Algos
43- ReductionA transformation of one problem into another to show hardness or solve it.
- Turing machineA mathematical model of computation that manipulates symbols on a strip of tape according to a table of rules.
- Chernoff boundA tail bound providing exponential decay probabilities for sums of independent random variables.
- Discrete Fourier transformA mathematical transformation that decomposes a discrete signal into its constituent frequencies.
- Fast Fourier transformAn algorithm used to compute the discrete Fourier transform and its inverse.
- Approximation algorithmAlgorithms that run in polynomial time and find solutions that are guaranteed to be close to the optimal or satisfy a large fraction of constraints rather than being exact.
- Probabilistic methodA technique used to prove the existence of a mathematical object with certain properties by showing that a randomly chosen object has positive probability of having those properties.
- AssociativityThe property where grouping of elements in a binary operation does not change the result.
- CompletenessThe property that if the input W is truly in the class, there exists a proof that causes the tester to accept with probability 1.
- Linearity of expectationThe expected value of the sum of two random variables is equal to the sum of their individual expected values.
- Constraint satisfaction problemA problem defined by variables, domains, and constraints, where the goal is to find an assignment of values to variables that satisfies all constraints.
- Markov's inequalityMarkov's inequality bounds the probability that a non-negative random variable is greater than or equal to a positive constant by the ratio of its expected value to that constant.
- Interactive proofsA proof system where a prover and a verifier interact to establish the truth of a statement.
- Circuit complexityThe measure of the resources needed to compute a boolean function using logic circuits, specifically evaluated as family sizes for languages.
- ConsciousnessConsciousness comprises what you see, hear, feel, and dream, with dreams being conscious and dreamless sleep not.
- Dijkstra's algorithmAn algorithm for finding the shortest paths between nodes in a graph with non-negative edge weights.
- Network flowA collection of problems associated with maximizing the amount of commodities that can push through a network with capacities.
- Time hierarchy theoremA theorem stating that giving a Turing machine more time allows it to solve strictly more problems.
- DerandomizationThe process of replacing random bits in an algorithm with pseudorandom strings generated deterministically from a short seed.
- Context-free grammarA formal grammar used to generate all possible strings in a given formal language.
- Unique games conjectureA conjecture stating that for all delta, it is NP-hard to distinguish between Label-Cover instances where almost all constraints can be satisfied versus instances where at most a delta fraction can be satisfied, even when the projection constraints are bijections.
- Ellipsoid algorithmAn algorithm that solves linear programs in polynomial time.
- Post-quantum cryptographyCryptographic algorithms that are secure against a cryptanalytic attack by a quantum computer.
- Church-Turing thesisAny real-world algorithm can be simulated or compiled by Turing machines.
- Homomorphic encryptionEncryption that allows computations to be performed on ciphertexts without decrypting them first.
- SoundnessThe property that if the input W is far from being in the class, then no proof will be convincing and the tester rejects with high probability.
- Zero-knowledge proofsAn interactive proof system where a prover convinces a verifier of a statement's truth without leaking any information beyond the fact that the statement is true.
- PCP theoremA theorem stating that approximating Max-E3Sat to within some constant factor strictly less than 1 is NP-hard.
- Berry-Esseen theoremA theorem used to bound the error in the normal approximation of a sum of independent random variables.
- Expander graphA graph is an expander if its second largest eigenvalue is bounded away from one by some constant.
- Unitary transformationA linear transformation on a complex inner product space that preserves inner products, representing reversible quantum operations.
- Dictator functionA Boolean function whose output depends only on a single input coordinate.
- Separation oracleAn oracle that, given a point, either confirms it is in the convex set or returns a separating hyperplane.
- Dictator testTesting procedures for Boolean functions used in PCP and hardness of approximation to distinguish dictators from quasirandom functions.
- Hypercontractivity theoremA theorem quantifying how the noise operator smoothes out spiky boolean functions by bounding higher norms in terms of lower norms.
- Notable coordinatesIndices of coordinates that are influential for a function.
- Shor's factoring algorithmA quantum algorithm for factoring integers in polynomial time.
- BrainishThe internal language created and used by the Conscious Turing Machine processors to communicate via chunks.
- Conscious Turing machineA simple model of a machine designed to understand consciousness, based on Turing's machine and Baars' Theater Model.
- Dictator versus no-notable testA local tester for Boolean functions that accepts dictators with high probability and functions far from dictators with low probability.
- Error termThe difference between two approximations in a Taylor expansion, bounded to analyze the approximation quality.
- Lovasz local lemmaA tool in probability theory for proving the existence of combinatorial objects with certain properties.
- Random self-reducibilityA property where a problem can be solved in the worst case with high probability by reducing it to instances of the same problem on random inputs.