September 28, 2022
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 29, 2022
- 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 3, 2022
- 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 5, 2022
- 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 6, 2022
- 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 10, 2022
- The VERTEX-COVER and INDEPENDENT-SET problems: definitions and reductions from CLIQUE.
- The SUBSET SUM problem: definition and reduction from 3CNF-SAT.
October 12, 2022
- 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 13, 2022
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 17, 2022
Approximation Algorithms (CLRS, Cap. 35)
- Definition of approximation algoritm
- PTAS and FPTAS
- 2 approximation algorithm for MINIMUM VERTEX-COVER
October 19, 2022
- 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 20, 2022
- 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 24, 2022
- MST-based 2-approximation of TRIANGLE-TSP: algorithm
- Christofides' 3/2-approximation of TRIANGLE-TSP: algorithm
October 26, 2022
- 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 27, 2022
- SET-COVER: finer, charging-based analyisis
- An FPTAS for SUBSET-SUM: The exact exhaustive algorithm.
November 2, 2022
- An FPTAS for SUBSET-SUM: the list trimming algorithm and its analysis
- Definition of randomized algorithm and randomized approximation algorithm
November 3, 2022
- 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 7, 2022
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, 2022
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 10, 2022
- 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 14, 2022
- 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 17, 2022
- RSA attacks.
- Decomposition of n=pq if p and q are very close.
tra loro.
- 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 21, 2022
- 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, 2022
- 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 24, 2022
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
November 28, 2022
Randomized Algorithms
- Introduction to randomized algorithms: Monte Carlo and Las Vegas algorithms.
- Analysis in expectation and in high probability
- Markov inequalities and their implications.
- Chernoff bounds on the tails of sums of bernoulli variables.
November 30, 2022
- Introduction to Randomized Quicksort: intuition on its computational efficiency
- Chernoff Bounds, Application 1: Analysis in high probability of Quicksort
December 1, 2022
- Average case complexity of Randomized Quicksort via Markov Inequality for bounded variables.
- Chernoff Bounds, Application 2: Correctness probability amplification
- Chernoff Bounds, Application 3: The Monte Carlo method
December 5, 2022
- Montecarlo counting for approximating pi = 3.1415...
- Min-cut on multigraphs: definition
- Contraction w.r.t. an edge
- Karger's Min-Cut algorithm: description and running time
December 7, 2020
- Karger's Min-Cut algorithm: probability of correctness and its amplification.
- Karger-Stein's Min-Cut algorithm: description of the recursive strategy and running time , recurrence on correctness probability.
December 12, 2022
- Karger-Stein's Min-Cut algorithm: derivation of correctness probability and its amplification.
- Coupon Collecting: analysis in expectation and in high probability
- Occupancy problems (m balls into n boxes): maximum load of a box for the case m=n. Application to hashing under linear chaining.
December 14, 2022
- Occupancy problems: further results
Exercise session: Randomized Algorithms
December 16, 2022
Exercise session: Randomized Algorithms
- Randomized Selection (analysis in expectation)
- Randomized Selection (analysis w.h.p., sketch)
- Tail bound for sums of i.i.d. Geometric variables
December 19, 2022
Exercise session: Randomized Algorithms
- Montecarlo approximation to Maximum Independent Set
- Las Vegas approximation to Maximum Independent Set
- Las Vegas approximation to Max-3CNF SAT
- Las Vegas approximation to Vertex Cover
January 11, 2023
Flipped classroom presentations: Session 1
- Gil Czaczkes and Thomas Trevisan: Algorithms with Predictions (Approximation + Learning)
- Giovanni Foti: Streaming Triangle Counting (Approximation + Randomization + Big Data)
- Pierre-Louis Lagunegrand and Andrea Matteazzi Map Reduce and Streaming Diversity Maximization (Approximation + Big Data)
- Luiggi Tenorio-Ku: Shortest-Path Broadcast (Approximation + Networking)
- Asifa Akter and Ashwini Bral: Elliptic Curve Cryptography ( (Cryptography)
January 12, 2023
Flipped classroom presentations: Session 2
- Massimo Boldrin and Martino Trapanotto: Entropy, Randomness and Information (Randomization + Information Theory)
- Mattia Borgo and Lorenzo Spina: Balanced Allocations and Cuckoo Hashing (Randomization + Data Structures)
- Simone Bortolin, Alessandra Pastore, and Matteo Pozzer Random graph models for Bluetooth Networks (Random graphs)
- Lorenzo Cappellotto, Borwoei Huang, and Paria Tahan: The Hiring Problem (Randomization)
|
