Concepts
5,907Terms and methods explained by more than one lecturer. Each opens at the minute it is taught.
Theory & Algos
162- ReductionA transformation of one problem into another to show hardness or solve it.
- Dynamic programmingA method for solving complex problems by breaking them down into simpler subproblems.
- NP-completeA problem is NP-complete if it is in NP and it is NP-hard.
- 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.
- NPA class of problems where a solution can be verified in polynomial time.
- Union boundA probability rule stating that the probability of the union of multiple events is at most the sum of their individual probabilities.
- 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.
- Directed acyclic graphA DAG is a directed graph with no directed cycles.
- 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.
- NP-hardA problem is NP-hard if every problem in NP reduces to it in polynomial time.
- 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.
- DiagonalizationA proof technique involving simulation to construct an object that differs from every object in a given enumeration.
- PThe class of problems that can be solved in polynomial time.
- Fermat's little theoremA theorem stating that aᵖ⁻¹ ≡ 1 pmod p for any prime and integer not divisible by .
- Stirling's formulaAn approximation for factorials given by .
- Unitary matrixA matrix whose columns form an orthonormal basis and whose conjugate transpose is its inverse.
- 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.
- Decision treeThe representation of a Boolean function represented as a binary tree where internal nodes are labeled by variables and leaves are labeled by numbers.
- Randomized algorithmAn algorithm that employs a degree of randomness as part of its logic.
- LanguageA subset of all possible strings over an alphabet.
- Modular arithmeticA system of arithmetic for integers where numbers wrap around after reaching a certain value called the modulus.
- ConfigurationA complete description of the state of a Turing machine, including the current state, the tape contents, and the head position.
- IndirectionThe ability to map virtual addresses to physical addresses, which is completely controlled by the operating system.
- Grover's algorithmA quantum algorithm that solves the unstructured search problem (finding a 1 among N bits) in square root of N queries.
- Pairwise independenceA condition where any two particular events or random variables in a set are independent, even if the entire set is not mutually independent.
- Halting problemThe problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
- ExpectationExpectation or mean is the probability-weighted average of all values a random variable can take.
- Indicator functionA function that takes the value 1 if a condition is met and 0 otherwise.
- Interactive proofsA proof system where a prover and a verifier interact to establish the truth of a statement.
- NP-completenessA language B is NP-complete if it is in NP and every language in NP is polynomial-time reducible to B.
- AnthropoceneA proposed new geological epoch defined by the dominant influence of human activity on Earth's climate and ecosystems.
- Computational complexityThe study of the resources, such as time and space, required to solve computational problems.
- ConsciousnessConsciousness comprises what you see, hear, feel, and dream, with dreams being conscious and dreamless sleep not.
- CryptographyThe art and science of scrambling and encrypting information so that it can be transmitted securely.
- Edit distanceThe minimum number of edits including insertions, deletions, or substitutions needed to make a read exactly match a reference segment.
- Time hierarchy theoremA theorem stating that giving a Turing machine more time allows it to solve strictly more problems.
- Exponential time hypothesisThe assumption that 3SAT cannot be solved in sub-exponential time for some .
- Cook-Levin theoremA theorem stating that every language in NP reduces in polynomial time to CIRCUIT-SAT.
- Decision problemAny problem with a yes or no answer.
- BPPThe class of languages decidable by a probabilistic polynomial-time Turing machine with an error probability of at most 1/3.
- Hamming weightThe number of non-zero elements in a string, which for binary strings is the number of ones.
- PSPACEThe class of decision problems solvable by a Turing machine using a polynomial amount of space.
- DerandomizationThe process of replacing random bits in an algorithm with pseudorandom strings generated deterministically from a short seed.
- CutA partition of the vertices of a flow network into two sets, one containing the source and the other containing the sink.
- Interactive proof systemA generalization of NP where an all-powerful prover interacts with a probabilistic verifier over multiple rounds.
- Search problemA computational problem where there can be multiple correct answers or no answer at all.
- 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.
- Universal Turing machineA Turing machine that takes a description of a machine and input and simulates its execution.
- Ellipsoid algorithmAn algorithm that solves linear programs in polynomial time.
- Graph isomorphism problemThe computational problem of determining whether two finite graphs are isomorphic, meaning one can be transformed into the other by permuting its vertices.
- Probabilistic Turing machineA PTM is a variant of a nondeterministic Turing machine where each computation step has 1 or 2 possible choices, with 50% probability assigned when there are two choices.
- Quadratic convergenceA rate of convergence where the number of correct digits of precision doubles at each iteration step.
- RelaxationThe fundamental operation in shortest path algorithms where we continually reduce estimated path distance values down to the true shortest path length.
- All pairs shortest pathsThe problem of finding the shortest path weights between all pairs of vertices in a directed graph.
- Amortized analysisAn analysis technique where we bound the total cost of a sequence of operations rather than the individual running time of each operation.
- Bernoulli random variableA random variable that takes the value 1 with probability p and 0 with probability 1-p.
- Bit vectorAn array of bits representing a set, where a 1 indicates an element is present and a 0 indicates it is absent.
- GadgetA substructure in a reduction that converts features of an input problem into corresponding features of an output problem.
- Homomorphic encryptionEncryption that allows computations to be performed on ciphertexts without decrypting them first.
- Linear programAn optimization problem with linear variables, a linear cost function to minimize or maximize, and linear constraints.
- Little o notationA notation used to describe the limiting behavior of a function relative to another, indicating it grows slower.
- One-to-one correspondenceA mapping between two sets of points where each point in one set is paired with exactly one point in the other set.
- Polynomial interpolationThe process of finding a polynomial that passes through a given set of points.
- Public key encryptionA method of secure communication where a secret is encrypted using the recipient's public key, ensuring only the recipient can decrypt it.
- Semidefinite programmingA generalization of linear programming where the optimization is over the cone of positive semidefinite matrices.
- PCP theoremA theorem stating that approximating Max-E3Sat to within some constant factor strictly less than 1 is NP-hard.
- Strong exponential time hypothesisThe assumption that for any delta, there exists a k such that k-SAT requires two to the one minus delta times n time.
- Berry-Esseen theoremA theorem used to bound the error in the normal approximation of a sum of independent random variables.
- Polynomial time reductionA method to transform one problem into another using an algorithm that runs in polynomial time.
- Savitch's theoremA theorem stating that any problem solvable by a non-deterministic Turing machine in space is solvable by a deterministic Turing machine in space.
- ArithmetizationThe process of converting a Boolean formula into a polynomial whose values match the Boolean formula on Boolean inputs.
- Circuit SATThe problem of determining if there exists an input to a boolean circuit that makes the circuit output 1.
- Expander graphA graph is an expander if its second largest eigenvalue is bounded away from one by some constant.
- P/polyThe complexity class containing all languages decidable by polynomial-size circuit families.
- Schwartz-Zippel lemmaA lemma stating that a non-zero multivariate polynomial over a finite field evaluates to a non-zero value with high probability when given random inputs.
- Space hierarchy theoremA theorem stating that giving a Turing machine more space allows it to solve strictly more problems.
- Unitary transformationA linear transformation on a complex inner product space that preserves inner products, representing reversible quantum operations.
- EXPThe complexity class of problems solvable in exponential time, specifically 2 to the power of a polynomial in n.
- Non-determinismA computational model where the machine can be in multiple states or follow multiple paths simultaneously, accepting if at least one path reaches an accept state.
- Oracle Turing machineA Turing machine equipped with an additional oracle tape and oracle state that allows it to decide membership in a specified language in a single step.
- Polynomial hierarchyA hierarchy of complexity classes that generalize P, NP, and coNP using alternating quantifiers.
- Polynomial identity testingThe problem of checking whether two given algebraic circuits compute identical polynomials.
- Radix sortA sorting algorithm that sorts integers by processing their individual bits or digits from least significant to most significant using a stable sort.
- SATThe counting problem of determining the exact number of satisfying assignments for a given Boolean formula.
- Separation oracleAn oracle that, given a point, either confirms it is in the convex set or returns a separating hyperplane.
- Space complexityThe class of problems that can be decided using a bounded amount of tape cells as a function of the input size.
- Space constructible functionA function such that a Turing machine can compute the value using space.
- Tall-cache assumptionThe assumption that cache size is at least , meaning the cache is taller than it is wide.
- Time constructible functionA function is time constructible if there exists a Turing machine that, given , outputs in time.
- Word RAM modelA standard computational model where words of size proportional to can be processed in constant time.
- Birthday paradoxA probability principle implying that an attack on a hash function requires roughly half the bit length of security steps to find a collision.
- Bounded-error probabilistic polynomial timeThe class of languages decided by a polynomial-time probabilistic Turing machine with an error probability of at most 1/3 on all inputs.
- ChainingA collision resolution technique where colliding keys in a hash table are stored together in a linked list.
- CNOT gateA 4x4 unitary quantum gate that applies a NOT operation to the target qubit if and only if the control qubit is in the state 1.
- Co-NPThe class of languages whose complements are in NP.
- Communication complexityThe study of computing functions when two parties are computing them and the thing that is measured is how much they need to communicate.
- Computable functionA function is computable if there is a Turing machine that halts with the function's output on its tape for any given input string.
- Deutsch-Jozsa algorithmA deterministic quantum algorithm that distinguishes whether a boolean function is constant or balanced with a single query, providing an exponential speedup over classical deterministic algorithms.
- Dictator testTesting procedures for Boolean functions used in PCP and hardness of approximation to distinguish dictators from quasirandom functions.
- DiffusionAn atomic operation where the influence of each plaintext bit is spread over many ciphertext bits.
- Fine-grained complexityThe study of exact running times and fine-grained differences within polynomial time complexity rather than just polynomial vs exponential.
- Flow conservationThe principle that for any vertex other than the source and sink, the total flow entering must equal the total flow leaving.
- Fourier coefficientThe coefficient of a specific monomial in the Fourier expansion of a function.
- Gadget reductionA reduction that translates instances of one problem to another using structural components called gadgets.
- Graph isomorphismThe computational problem of determining whether two finite graphs are isomorphic, known to be in NP.
- Hypercontractivity theoremA theorem quantifying how the noise operator smoothes out spiky boolean functions by bounding higher norms in terms of lower norms.
- Leader electionThe process where exactly one process in a connected graph outputs a special leader signal.
- One-time padA perfectly secure encryption scheme where the secret key is a uniformly random string of the same length as the message and is used only once.
- PaddingA complexity theory trick of artificially changing the input length of a language or problem.
- Parity check matrixA parity check matrix H for a code C is a matrix whose rows are orthogonal to every codeword in C.
- Probabilistically checkable proofsA type of proof system where a reviewer can verify a proof with high confidence by spot-checking only a constant number of symbols randomly.
- ReducibilityIf we have two languages or problems A and B, then A is reducible to B means that we can use B to solve A.
- RelativizationThe property of simulation results holding equally well when both machines are given access to the same oracle.
- Schönhage-Strassen algorithmAn asymptotically fast multiplication algorithm for large integers running in O(n log n log log n) time.
- Shor's factoring algorithmA quantum algorithm for factoring integers in polynomial time.
- TrieA rooted tree whose child branches are labeled with letters in the alphabet, used here to represent strings as root-to-leaf paths.
- A complexity class in the polynomial hierarchy corresponding to .
- BadnessAn aesthetic cost function that quantifies how undesirable a specific line break configuration is.
- BrainishThe internal language created and used by the Conscious Turing Machine processors to communicate via chunks.
- Complexity theoryComplexity theory investigates what is computable in practice, focusing on resources like time and space required by algorithms.
- Conscious Turing machineA simple model of a machine designed to understand consciousness, based on Turing's machine and Baars' Theater Model.
- Diagonalization methodA proof technique similar to Cantor's diagonal argument used to show uncountability or undecidability.
- DiscrepancyThe absolute value of the sum of the coloring values in a row, which we want to keep small.
- Euler tourA walk that traverses every edge exactly once and starts and finishes at the same vertex.
- Exact 3-satisfiability3SAT with the restriction that every clause has exactly three distinct literals and three distinct variables.
- Freivalds' algorithmA randomized algorithm that verifies whether the product of two matrices is equal to a third matrix in time.
- Hardness versus randomnessA paradigm in complexity theory showing that computational hardness can be traded for pseudorandomness to derandomize efficient probabilistic algorithms.
- Integral approximation of sumsBounding sums like log factorials by comparing them with the area of rectangles and under curve integrals.
- Inverse elementAn element for every group element that, when combined with it via the group operation, yields the neutral element.
- Irreducible polynomialA polynomial of degree at least 2 that cannot be factored as a product of two lower-degree polynomials.
- K-wise independenceA property where for any k distinct output positions, the joint probability distribution equals the uniform distribution of k bits.
- Karatsuba algorithmA fast multiplication algorithm that reduces the number of recursive multiplication operations from 4 to 3.
- Linear probingA probing strategy in open addressing where the hash function adds the probe number sequentially to an ordinary hash function.
- Lovasz local lemmaA tool in probability theory for proving the existence of combinatorial objects with certain properties.
- LP dualityA principle where every linear maximization program has a dual minimization program whose optimal value provides an upper bound on the primal.
- Median findingThe problem of finding the median or an element of a specific rank in a set of numbers in better than time.
- Multi-tape Turing machineA Turing machine variant that has one or more tapes, where the input is on the first tape and the others are initially blank work tapes.
- Newton's method for divisionDivision reduces to computing 1 over y by solving the equation yz = 1 using Newton's method, then performing a multiplication with x.
- Nondeterministic timeNondeterministic time NTIME(f(n)) is the class of languages decidable by a nondeterministic Turing machine within f(n) time steps.
- Nth roots of unityNumbers that yield 1 when raised to the nth power, uniformly spaced around the unit circle in the complex plane.
- Order of an elementThe cycle length or number of distinct values reached when computing successive powers of an element in a group.
- PAC learningA framework where given an unknown distribution and samples, one aims to output a classifier with low error with high probability.
- Polynomial evaluationThe process of computing a polynomial's values given its coefficients representation.
- Potential methodA technique for amortized analysis that maps a data structure's state to a potential function value to pay for costly operations.
- Predecessor problemThe problem of maintaining a set of elements to support insert, delete, predecessor, and successor queries.
- Pseudo-random generatorA generator that takes a short seed of log n bits and expands it to n bits such that efficient polynomial-time machines cannot distinguish it from true randomness.
- Push operationThe operation of adding a new symbol onto the top of a stack, which pushes existing symbols down.
- Random access machineThe algorithmic model we really work in when we do algorithms, where memory access is random.
- 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.
- Symmetric differenceThe set of all elements that are in either of the two sets, but not in their intersection.
- Time complexityThe total time required for an algorithm to complete its execution in the worst case.
- Time-space relationshipThe containment relationship between time complexity classes and space complexity classes.
- Transdichotomous RAM modelA model of computation where running times only depend on and work for all word sizes .
- Transitive closureThe reachability relation between vertices in a graph, computed via repeated squaring or specialised matrix operations.
- Van Emde Boas treeA tree-based data structure supporting predecessor queries in Θ(log log u) time using space.
- Zero-error probabilistic polynomial timeZPP is the complexity class of problems solvable by a probabilistic Turing machine in expected polynomial time with zero error.