Concept
Polynomial-time reduction
Related courses (6)
CS-250: Algorithms I
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
MATH-261: Discrete optimization
This course is an introduction to linear and discrete optimization.
Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p
COM-501: Advanced cryptography
This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it pr
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
PHYS-435: Statistical physics III
This course introduces statistical field theory, and uses concepts related to phase transitions to discuss a variety of complex systems (random walks and polymers, disordered systems, combinatorial o
MATH-683: Fine-grained and parameterized complexity
The classical distinction between polynomial time solvable and NP-hard problems is often too coarse. This course covers techniques for proving more fine-grained lower and upper bounds on complexity of