Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Theory of Computation: Monotone Complexity and XOR-SAT Lower Bounds

Description

This lecture delves into the theory of computation, focusing on monotone complexity and XOR-SAT lower bounds. It covers the concept of monotone circuits, the absence of negation gates, and the implications of monotone circuits in the P vs. NP problem. The instructor presents a new lower bound theorem related to XOR-SAT, showcasing the complexity of monotone circuits. Additionally, examples of monotone computations are provided to illustrate the concepts discussed. The lecture concludes with an overview of various topics in the field, such as optimization, learning theory, and proof complexity.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computational complexity theory

Related concepts (32)

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.

NP (complexity)

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.

Communication complexity

In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and .

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

Related lectures (33)

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Graph Coloring: Random vs Symmetrical

Compares random and symmetrical graph coloring in terms of cluster colorability and equilibrium.

Dynamic Programming: Pascal's Triangle & Floyd's Algorithm

Explores dynamic programming through Pascal's Triangle and Floyd's Algorithm.

Graph Algorithms II: Traversal and Paths