September 29, 2025
NP Completeness (CLRS, Ch. 34)
- Course Introduction.
- Syllabus.
- Problem classes: undecidable, intrinsically exponential,
intractable, polynomial.
- Abstract problems and decision problems. Reduction from optimization to decision problems. Example: SHORTEST UNWEIGHTED PATH.
September 30, 2025
- Encodings. Abstract and concrete problems. Reasonable encodings
- Formal Languages. Concrete problems and associated languages.
- Poly-time decision of languages. Definition of P.
- Verifiability. Example: HAMILTON
- Poly-time verifiability of languages. Definitiom of NP.
October 1, 2025
- Theorem: P is a subset of NP
- Reducibility. Example: verifier for HAMILTON
- Poly-time reducibility: characteristics of reduction functions.
- Theorem: if L1 < L2 and L2 is in P, then also L1 is in P
- Classes NPH and NPC.
- Corollary: if L is both in NPC and in P, then P=NP.
October 6, 2025
- The BC-SAT problem: definition.
- Poly-time verifier for BC-SAT
- Reduction from any language in NP to BC-SAT (Cook's Theorem, high level idea)
- The FORMULA-SAT (SAT) problem: definition.
- Non poly-time reduction from BC-SAT to SAT.
October 7, 2025
- Poly-time reduction from BC-SAT to SAT.
- The 3CNF-SAT problem: definition and reduction from BC-SAT.
- The CLIQUE problem: definition.
October 8, 2025
- The CLIQUE problem: reduction from 3CNF-SAT.
- The VERTEX-COVER and INDEPENDENT-SET problems: definitions and reductions from CLIQUE.
- The SUBSET SUM problem: definition.
October 13, 2025
- The SUBSET SUM problem: reduction from 3CNF-SAT
Exercise session: NP-completeness
- Any NP language is decidable (in exponential time)
- The HALTING problem is in NPH
- If L1 < L2 and L2 is in NP, the L1 is in P.
- BC-TESTING is in NPH
- KNAPSACK is in NPH
October 14, 2025
Exercise session: NP-completeness
- Complementary languages and the class Co-Np
- DOMINATING SET is in NPH
- LONG-PATH is in NPH
- Construction of a solution starting from an oracle for the decision problem. Application to SUBSET_SUM.
October 15, 2025
Approximation Algorithms (CLRS, Cap. 35)
- Definition of approximation algoritm
- PTAS and FPTAS
- 2 approximation algorithm for MINIMUM VERTEX-COVER
October 20, 2025
- MIN VC approximation cannot be used for MAX-CLIQUE
- Greedy approaches to MIN VC without approximation guarantees
- MINIMUM WEIGHTED VERTEX COVER: fair pricing approach
- MINIMUM WEIGHTED VERTEX COVER: ILP rounding approach
October 22, 2025
- Primal-dual relationship between the two MWVC approaches
- Decision TSP: NP-completeness
- Inapprossimability of general TSP
- Decision TRIANGLE TSP (TSP with metric function): NP-completeness
- MST-based 2-approximation of TRIANGLE-TSP: algorithm
October 27, 2025
- MST-based 2-approximation of TRIANGLE-TSP: algorithm
- Christofides' 3/2-approximation of TRIANGLE-TSP: algorithm and analysis
October 28, 2025
- State-of-the-art results on TRIANGLE-TSP and EUCLIDEAN-TSP
- SET-COVER: NP-completeness of decision problem and greedy algorithm.
- (ln n)-approximation bound
October 29, 2025
- SET-COVER: finer, charging-based analyisis
- An FPTAS for SUBSET-SUM: The exact exhaustive algorithm.
November 3, 2025
- An FPTAS for SUBSET-SUM: the list trimming algorithm and its analysis
- Definition of randomized algorithm and randomized approximation algorithm
November 4, 2025
- MAX-SAT. Definition, NP-completeness and 8/7 randomized approximation algorithm
Exercise session: Approximation Algorithms
- RESOURCE SELECTION: 2-approximation based on linear relaxation
- MAX-CUT: deterministic 2-approximation
- MAX-CUT: randomized 2-approximation
November 5, 2025
Exercise session: Approximation Algorithms
- Impossibility of an FPTAS for TRIANGLE TSP
- SUBSET-SUM: greedy 2-approximation
- INDEPENDENT SET: greedy max-degree approximation
- LOAD-BALANCING, 2-approximation and hints to 3/2-approximation
November 10, 2025
Number-Theoretic Algorithms (CLRS, Cap. 31)
- Divisibility: definitions and properties
- Greatest Common Divisor (gcd) and Bezout identity.
- Euclid algorithm: correctness and complexity.
- Extended Euclid Algorithm
November 11, 2025
- Modular arithmetic: the quotient structure Zn: group properties wrt sum
- The subset Z*n and group properties wrt multiplication
- Computation of the multiplicative inverse via EXTENDED-EUCLID
- Euler function, Euler theorem and Fermat little theorem
November 12, 2025
- Chinese Reminder Theorem: statement, proof, corollaries and applications
- Definition of cryptosystem and public key cryptosystem
- Communication and authentication protocols
November 17, 2025
- RSA details: computing public and private key. Recursive and iterative algorithms for modular exponentiation.
- RSA correctness: public and secret encoding are one the inverse of the other.
- RSA: complexity considerations
November 18, 2025
- RSA attacks.
- Decomposition of n=pq if p and q are very close.
- Attacks for choices of public keys sharing the same exponent.
- Attacks for choices of public keys sharing the same modulus.
- Attacks based on authentication. Digital digests and one-way hash functions.
- Introduction to primality.
November 19, 2025
- Base-a pseudoprimes and simple deterministic test for random inputs: probabilistic analysis based on Pomerance's Theorem on the distribution of base-2 pseudoprimes.
- Compositeness certificates based on non base-a pseudoprimality or nontrivial square roots of unity.
|
