 Lectures Diary September 28, 2021

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, 2021
• 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, 2021
• 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.
• BC-SAT: definition

October 5, 2021
• The BC-SAT problem: definition.
• Cook's Theorem 1) Poly-time verifier for BC-SAT 2) Reduction from any language in NP to BC-SAT (high-level idea).
• The FORMULA-SAT (SAT) problem: definition.
• Non poly-time reduction from BC-SAT to SAT.

October 7, 2021
• Poly-time reduction from BC-SAT to SAT.
• The 3CNF-SAT problem: definition and reduction from BC-SAT.
• The CLIQUE problem: definition and reduction from 3CNF-SAT.

October 8, 2021
• The VERTEX-COVER and INDEPENDENT-SET problems: definitions and reductions from CLIQUE.
• The SUBSET SUM problem: definition and reduction from 3CNF-SAT.

October 12, 2021
• The SUBSET SUM problem: definition and reduction from 3CNF-SAT (cont'd)

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, 2021

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, 2021

Approximation Algorithms (CLRS, Cap. 35)

• Definition of approximation algoritm
• PTAS and FPTAS
• 2 approximation algorithm for MINIMUM VERTEX-COVER

October 21, 2021
• 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, 2021
• Primal-duale 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 26, 2021
• MST-based 2-approximation of TRIANGLE-TSP: algorithm
• Christofides' 3/2-approximation of TRIANGLE-TSP: algorithm

October 28, 2021
• Christofides' 3/2-approximation of TRIANGLE-TSP: analysis
• 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, 2021
• SET-COVER: finer, charging-based analyisis
• An FPTAS for SUBSET-SUM: The exact exhaustive algorithm.

November 2, 2021
• An FPTAS for SUBSET-SUM: the list trimming algorithm and its analysis
• Definition of randomized algorithm and randomized approximation algorithm

November 4, 2021
• 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, 2021

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 9, 2021

Number-Theoretic Algorithms (CLRS, Cap. 31)

• Divisibility: definitions and properties
• Greatest Common Divisor (gcd) and Bezout's identity.
• Euclid's algorithm: correctness and complexity.
• Extended Euclid's Algorithm

November 11, 2021
• 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's function, Euler's theorem and Fermat's little theorem

November 12, 2021
• Chinese Reminder Theorem: statement, proof, corollaries and applications
• Definition of cryptosystem and public key cryptosystem
• Communication and authentication protocols

November 16, 2022
• 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, 2021
• RSA attacks.
1. Decomposition of n=pq if p and q are very close. tra loro.
2. Attacks for choices of public keys sharing the same exponent.
3. Attacks for choices of public keys sharing the same modulus.
4. Attacks based on authentication. Digital digests and one-way hash functions.
• Introduction to primality.

November 19, 2021
• Base-a pseudoprimes and simple deterministic test for random inputs: probabilistic analysis based on Pomerance Theorem in the distribution of base-2 pseudoprimes.
• Compositeness certificates based on non base-a pseudoprimality or nontrivial square roots of unity.

November 23, 2021
• Miller-Rabin test: randomized search for a compositeness certificate.
• Miller-Rabin test: running time
• Miller-Rabin test: correctness analysis for non-Carmichael numbers.

Exercise session: Number-Theoretic Algorithms

• Integer division algorithm: computing quotient and reminder in quadratic time.

November 25, 2021

Exercise session: Number-Theoretic Algorithms

• Uniqueness of the multiplicative inverse
• Efficient computation of the least common multiple
• Integer linear combinations with two unknowns
• Bezout cofficients and solutions of integer linear combinations

Randomized Algorithms

• Introduction to randomized algorithms: Monte Carlo and Las Vegas algorithms.

November 26, 2021
• Analysis in expectation and in high probability
• Markov inequalities and their implications.
• Chernoff bounds on the tails of sums of bernoulli variables.

 Last update: November 23, 2021 Go to index