Archives Course MPRI 2.11.1 (2012-2022)

Dates for the lectures:

• Lecture 1: Thu 9 DEC Approximation & Randomized Algorithms 1/4
• Lecture 2: Thu 16 DEC Molecular algorithms 1/4
• Lecture 3: Thu 6 JAN Molecular algorithms 2/4
• Lecture 4: Thu 13 JAN Approximation & Randomized Algorithms 2/4
• Lecture 5: Thu 20 JAN Approximation & Randomized Algorithms 3/4
• Lecture 6: Thu 27 JAN Approximation & Randomized Algorithms 4/4
• Lecture 7: Thu 3 FEB Molecular algorithms 3/4
• Lecture 7: Thu 10 FEB Molecular algorithms 3/4
• Lecture 8: Thu 24 FEB Online (Zoom) - Live from the wetlab Molecular algorithms 4/4\\

Final exam

• Final Exam: Thu 10 MAR 8:45-11:45

Teachers:

• Nicolas Schabanel (CNRS - LIP): in Charge of the Course & Molecular Programming
• Chien-Chung Huang (CNRS - DIENS): Approximation Algorithms

Lectures will take place every Thursdays 8:45-11:45 in SG1002 starting on 9 DEC.

Internship proposals:

• 2022 M2 Internship proposal: DNA computing: Theory, Models and wet lab experiments

This lecture explore actual trends in algorithms (and complexity). We will first focus on classic technique mainly based on randomness to obtain approximate solutions to NP-hard problems with proven guarantee. Second, we will explore how algorithms (randomized algorithms and structures) can help understanding better how nature works.

1. Approximation algorithms: We will first learn how to provide guarantee on the quality of a solution with respect to the optimal when the optimal cannot be computed because either the problem considered is NP-hard or no known exact algorithms are fast enough to be effective. We will practise the various technics designed to analyze its cost guarantee. This field makes extensive use of randomness in order to improve performances.
2. Molecular algorithms: The second part of the lectures will be dedicated to an introduction to the new field of molecular programming where people are developing theoretical algorithmic models and realizing in wetlab experiments computers compatible with life as we know it. Exploiting the flexibility of DNA molecule, implementations of this new of a kind computer are already happening. We will explore the very rich theory behind this field and hopefully realize some wetlab experiments together to implement algorithms using molecular interactions. Computations in these models are naturally random.

Approximation algorithm design essentially consists on the positive side in finding the proper relaxation of the constraints in the initial problem in order to get a polynomial-time estimate of the optimal that can then be converted into a solution of the initial problem. The art consists in showing that the quality of the solution does not change in the process. Typical tools are linear and semi-definite programming. On the negative side, it consists in using the celebrated PCP theorem and polynomial reductions (very similar to the classic NP-hardness reductions) to show that some problems cannot be approached within some factor unless P=NP or other catastrophes of the same kind.

In this second part of the lecture, we will overview the various approaches to the exciting and uprising field of Molecular programming where one uses algorithms to design real molecules that processes information algorithmically. We will explore in details the various theoretical models, their complexity and expressiveness, learn how to program them and survey their experimental realizations, in particular how to design algorithmically these molecules for real. Depending on the timing, we hope to be able to have you take part to a real wetlab experiments where we will have molecules executing a (simple) program for us and observe at the end of its execution the nanoscopic results (usually only about few 100nm large) thru atomic force microscope (to be confirmed).

A good base in algorithms and complexity is helpful (elementary algorithms, circuits, complexity classes). Knowledge of discrete probabilities and basic information theory (Shannon entropy) helpful.

1. Approximation algorithms: (4 sessions)
2. Molecular Algorithms theory and practice (4 sessions)
   • Tile self-assembly system: model, intrinsic universality, algorithms, realizations, DNA computing nanotubes
   • Boolean circuits: model, circuit, realizations
   • RNA based computing: oritatami systems, shapes, Turing universality, uncomputability
   • Experiments: how do we proceed

The lectures will be given in english unless every attendee is fluent in french.

The exam will be given in English, and can be written by the students in either language (french or english).

Every session will consist in general of ≈2h lecture followed by ≈1h exercises session.

A small exercise will be given as an homework at the end of each session to be returned for the next session.

• Algorithmes d'approximation, V. Vazirani, Springer, 2006 (traduit de l'américain par N. Schabanel)
• Approximation algorithms, V. Vazirani, Springer, 2001
• Probability And Computing: Randomized Algorithms And Probabilistic Analysis, by M. Mitzenmacher and E. Upfal, Cambridge University Press, 2005
• Computational Complexity: A Modern Approach . S. Arora and B. Barak. Cambridge University Press, 2009.
• Communication Complexity. E. Kushilevitz and N. Nisan. Cambridge University Press, 1997.
• Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science). S. Muthukrishnan. Now Publishers Inc, 2005.

There are no lecture notes. The lectures will be given on the board. Students will be encouraged to write down lecture notes that will be made later available to everyone. Some additional reading will be suggested during the course.

Internships are available. Contact the teachers of the lectures directly (for instance by email):

• Chien-Chung Huang (CNRS - DIENS): Approximation Algorithms
• Nicolas Schabanel (CNRS - LIP): Molecular Programming

• Chien-Chung Huang (CNRS - DIENS): Approximation Algorithms
• Nicolas Schabanel (CNRS - IRIF): Molecular Programming

The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.

• 1.24 Probabilistic aspects of computer science (Parts 3 & 4 starting in november)
• 2.11.1 Approximation Algorithms & molecular programming
• 2.11.2 Randomness in Complexity
• 2.12.1 Techniques in Cryptography and Cryptanalysis
• 2.13.2 Error correcting codes and applications to cryptography
• 2.18.1 Distributed algorithms for the networks
• 2.18.2 Algorithmique distribuée avec mémoire partagée
• 2.24.1 Optimisation
• 2.29.1 Graph algorithms
• 2.33.1 Theory of Computations
• 2.34.1 Quantum information and applications
• 2.38.1 Algorithms for embedded graphs

The following is a coherent list of courses on the thematic 'Molecular and Biological programming & modelling'.

• 2.11.1 Approximation Algorithms & molecular programming
• 2.19 Biochemical Programming

Some related research articles:

• Experiments:
  • DNA Origami
  • A cargo sorting DNA robot
• Abstract tile sel-assembly:
  • Minimizing tile set
  • Minimizing assembly time
  • Staged self-assembly
  • Self-Assembled Shapes
  • Tile-assembly system is intrinsically universal
  • One tile is enough
• DNA strand displacement systems:
  • Leakless DNA Strand Displacement Systems
• Oritatami:
  • Oritatami is Turing universal
  • Shapes in Oritatami

Lecture 1 (2021.12.9): Introduction to Approximation Algorithms

• Overview of the field
• Greedy algorithm/LP-based algorithm for Set Cover
• Greedy algorithm for disjoint-path Problem
• First Assignment PDF

Lecture 2 (2022.1.13): PTAS and TSP

• FPTAS for knapsack
• Asymptotic PTAS for bin packing
• Christofides' 1.5-approximation algorithm for TSP
• Second Assignment PDF

Lecture 3 (2022.1.20): Machine Scheduling

• PTAS for minimising makespan in identical machine setting
• 2-approximation for minimising makespan in unrelated machine setting
• Third Assignment PDF

Lecture 4 (2022.1.27): Facility Location

• LP-based deterministic 4-approximation algorithm
• LP-based randomized 3-approximation algorithm

Lecture 2 [1/4] (2021.12.16): Introduction to DNA programming & Tile Assembly Systems [ Slides ]

• Introduction to DNA programming & overview of the field
• Abstract tile assembly systems:
  • Definition
  • Minimizing the assembly time
• Exercise sessions [ HW1 ]
  1. Guess the assembly 1
  2. Guess the assembly 2 (HW1 to return before Thu 2022.01.06 8:45)
  3. Bit-cave
  4. Assembly time = O(rank of the produced shape)
  5. Staged self-assembly

Lecture 3 [2/4] (2022.01.06): Universality in assembly Model (I): Theory and experiment

• Universality in assembly Model (I) [ Slides ]
  • Simulating a Turing machine at temperature T°=2 in aTAM
  • Optimal hardcoding of a binary string at T°=2 in aTAM
  • Simulating a Turing machine at temperature T°=1 in aTAM in 3D
• An experimental realization of a universal computer [ Slides ]
  • Single stranded tile nanotubes
  • Atomic Force Microscopy (AFM)
  • Marking 0s and 1s using biotin-streptavidin
  • kTAM kinetic assembly model
  • Error correction using proof-reading tiles
  • DNA nanotube circuit model
  • Examples of nanotube circuits
  • A 6-bits Turing universal nanotube circuit
  • Minimizing errors with proof-reading tiles
  • Counting the glues
  • Sequence design
  • Experiment results
• Exercise sessions [ HW2 ]
  1. Exponential random variables and kTAM implementation
  2. Tileset for simulating cellular automata
  3. Probabilistic simulation of Turing Machine at T°=1 in 2D
  4. Scale the wall Option 1: to return by Thu. Feb 3, 2022 8:45 the latest
  5. Design a DNA origami Option 2: to return by Thu. Jan 27, 2022 8:45 the latest in order to process to the presentation of the designs and vote for the one we will assemble together in wetlab on Feb 24
     Some links for inspiration [ DNA origami | Survey | Dietz lab | Multi-component origami ]

Lecture 7 [3/4] (2022.02.10): Oritatami: a computational model for co-transcriptional folding

• Oritatami [ Slides ]
  • Co-transciptional RNA folding
  • Oritatami model
  • Oritatami vs aTAM
  • A binary counter
  • Efficient Turing machine simulation
  • NP-hardness and FPT linear algorithm for the rule design problem
  • Building shapes at constant scale with a set of 19 universal bead types
  • Turedo: building nanobots with oritatami
  • Intrinsic simulation
  • The macrocell
  • A key tool: folding meter and pocket
  • The density of limit configurations

• Exercise sessions [ HW3 ]
  1. Oritatami: impossible triangular path (Due on Thursday Feb 24 before 8:45)

Lecture 8 [4/4] (2022.02.24): Live AFM session

• Imaging the 8-squares origami designed in class
  • to be continued

Lecture 1 (2019.09.16): Introduction to DNA programming & Tile Assembly Systems [ Slides ]

• Introduction to DNA programming & overview of the field
• Abstract tile assembly systems:
  • Definition
  • Minimizing the assembly time
• Exercise sessions [ HW1 ]
  1. Guess the assembly 1
  2. Guess the assembly 2
  3. Assembly time = O(rank of the produced shape)
  4. Staged self-assembly
  5. Making turns

Lecture 2 (2019.09.23): Universality in assembly Model (I): Theory and experiment

• Universality in assembly Model (I) [ Slides ]
  • Simulating a Turing machine at temperature T°=2 in aTAM
  • Optimal hardcoding of a binary string at T°=2 in aTAM
  • Simulating a Turing machine at temperature T°=1 in aTAM in 3D
• An experimental realization of a universal computer [ Slides ]
  • Single stranded tile nanotubes
  • Atomic Force Microscopy (AFM)
  • Marking 0s and 1s using biotin-streptavidin
  • kTAM kinetic assembly model
  • Error correction using proof-reading tiles
  • DNA nanotube circuit model
  • Examples of nanotube circuits
  • A 6-bits Turing universal nanotube circuit
  • Minimizing errors with proof-reading tiles
  • Counting the glues
  • Sequence design
  • Experiment results
• Exercise sessions [ HW2 ]
  1. Exponential random variables and kTAM implementation
  2. Tileset for simulating cellular automata
  3. Probabilistic simulation of Turing Machine at T°=1 in 2D

Lecture 3 (2020.09.30): Universality in assembly Model (II): Intrinsic universality and Oritatami

• Intrinsic Universality in tile assembly model [ Slides ]
  • Intrinsic universality at T°2
  • The supercell, the probes
  • One (polygonal) tile is enough
• Oritami: a computational model for co-transcriptional folding [ Slides ]
  • RNA co-transcriptional folding
  • Oritatami model
  • A first example: a binary counter
  • Proving its correctness
  • Rule design is NP-hard but FP-tractable
  • Oritatami is Turing complete
  • Simple intrinsic Oritatami simulation of cellular automata
• Exercise sessions [ HW3 ]
  1. Building shapes with Oritatami

Lecture 4 (2020.10.07, Last): Strand displacement boolean circuits [ Slides ]

• DNA Strand displacement mechanism
• Some basic of thermodynamics [ Slides ]
• Reading with fluophore
• Dealing with leaks
• Double long domain [ Slides ]
• Exercise sessions [ HW4 ]
  1. DNA circuits
  2. Strand displacement: DNA gate (1 page maximum)
  3. aTAM: Scale the wall (1 page maximum)

Lecture 5 (2020.10.14): Introduction to Approximation Algorithms

• Overview of the field
• Greedy algorithm for Set Cover
• Laying algorithm for Weighted Vertex Cover
• Approximation scheme for Knapsack
• First Assignment PDF

Lecture 6 (2020.10.21): Introduction to Linear Program

• Christofides' TSP Algorithm
• Introduction to Linear Program and Duality Theory
• Two Rounding Algorithm for Set Cover
• Analysis of Greedy for Set Cover Using Dual-Fitting
• Second Assignment PDF

Lecture 7 (2020.10.28): Introduction to Large Concentration Inequality

• Third Assignment PDF

Lecture 1: Introduction

• Introduction to Approximation Algorithms & overview of the field
• Examples of Combinatorial/LP-Based/Randomized Algorithms for NP-hard Problems
• Min-Cut Algorithm of Karger
• First Assignment PDF

Lecture 2: Chernoff Bounds

• Christofides' TSP algorithm
• Chernoff Bounds
• Integer Multi-commodity Flow
• 3-Coloring Dense Graphs
• Second Assignment PDF

Lecture 3: Random Walk and Submodular Function

• 2SAT
• K-Coverage

Lecture 4: Semi-Definitie Programming

• Max-Cut
• Color-Coding
• Vertex-Cover Revisited
• Third Assignment PDF

Lecture 5 (2019.10.09): Introduction to DNA programming & Tile Assembly Systems [ Slides ]

• Introduction to DNA programming & overview of the field
• Abstract tile assembly systems:
  • Definition
  • Minimizing the assembly time
• Exercise sessions [ HW1 ]
  1. Guess the assembly 1
  2. Guess the assembly 2
  3. A binary counter
  4. Staged self-assembly
  5. Assembly time = O(rank of the produced shape)

Lecture 6 (2019.10.16): Universality in assembly Model (I): Theory and experiment

• Universality in assembly Model (I) [ Slides ]
  • Simulating a Turing machine at temperature T°=2 in aTAM
  • Optimal hardcoding of a binary string at T°=2 in aTAM
  • Simulating a Turing machine at temperature T°=1 in aTAM in 3D
• An experimental realisation of a universal computer (I) [ Slides ]
  • Single stranded tile nanotubes
  • Atomic Force Microscopy (AFM)
  • Marking 0s and 1s using biotin-streptavidin
  • kTAM kinetic assembly model
  • Error correction using proof-reading tiles
  • DNA nanotube circuit model
• Exercise sessions [ HW2 ]
  1. Staged self-assembly (from HW1)
  2. Exponential random variables and kTAM implementation
  3. Tileset for simulating cellular automata
  4. Probabilistic simulation of Turing Machine at T°=1 in 2D

Lecture 7 (2019.10.23): Universality in assembly Model (II): experiment, intrinsic universality and Oritatami

• An experimental realisation of a universal computer (II) [ Slides (again) ]
  • Examples of nanotube circuits
  • A 6-bits Turing universal nanotube circuit
  • Minimizing errors with proof-reading tiles
  • Counting the glues
  • Sequence design
  • Experiment results
• Intrinsic Universality in tile assembly model [ Slides ]
  • Intrinsic universality at T°2
  • The supercell, the probes
  • One (polygonal) tile is enough
• Oritami: a computational model for co-transcriptional folding [ Slides ]
  • RNA co-transcriptional folding
  • Oritatami model
  • A first example: a binary counter
  • Proving its correctness
  • Rule design is NP-hard but FP-tractable
  • Oritatami is Turing complete
  • Simple intrinsic Oritatami simulation of cellular automata
• Exercise sessions [ HW3 ]
  1. Window movie Lemma

Lecture 8 (2019.10.30 - Last): Oritatami Shapes & Strand displacement boolean circuits

• Oritatami: building shapes [ Slides ]
  • The problem
  • Some impossible shapes
  • Scaling schemes
  • Algorithm for scales B_n≥3
  • Filling a pseudo-hexagon
  • Bead type set for tight Oritatami systems
  • Algorithm for scales A_n≥5
  • Algorithm for scale A₄
  • Algorithm for scale A₃
  • Time anomalies and how to fix them

• Strand displacement boolean circuits [ Slides ]
  • DNA Strand displacement mechanism
  • Some basic of thermodynamics [ Slides ]
  • Reading with fluophore
  • Dealing with leaks
  • Double long domain [ Slides ]

Lecture 1 Introduction to Randomised and Approximation Algorithms

• Introduction to the Course
• Optimization problems & Approximation Algorithms
• Vertex Cover
• Set Cover
• Min Cut of Karger
• First Assignment PDF

Lecture 2 Chernoff Bounds

• Chernoff Bounds
• Integer Multi-commodity Flow
• Coloring 3-colorable Graph
• Christofides Algorithm
• Second Assignment PDF

Lecture 3

• Introduction to Linear Programming
• Facility Location
• Third Assignment PDF

Lecture 4

• Introduction to Semi-Definite Programming
• Max-Cut
• Color-Coding and Vertex-Feedback Set

Lecture 5: Introduction to DNA programming & Tile Assembly Systems [ Slides ]

• Introduction to DNA programming & overview of the field
• Abstract tile assembly systems:
  • Definition
  • Minimizing the assembly time
• Exercise sessions [ HW1 ]
  1. Guess the assembly 1
  2. Guess the assembly 2
  3. A binary counter
  4. Staged self-assembly
  5. Assembly time = O(rank of the produced shape)
  6. Minimum number of tiles self-assembling squares and rectangle

Lecture 6: Universality in assembly models & Introduction to Strand displacement

• Universality in assembly models [ Slides A ]
  • aTAM simulate Turing machines at temperature T=2
  • Optimal seed encoding at T=2: Kolmogorov complexity & unpacking
  • aTAM simulate Turing machines at temperature T=1 in 3D but not 2D
  • Intrinsic universality of aTAM at temperature T=2
  • One (polygonal) tile is enough!
• Introduction to Strand displacement [ Slides B (by Chris Thachuk) ]
• Exercise sessions [ HW2 ]
  1. Tileset for simulating cellular automata
  2. Probabilistic simulation of Turing machine at temperature T=1 in 2D
  3. Window movie lemma

Lecture 7: Strand Displacement

• Boolean circuits using Strand displacement [ Slides (by Chris Thachuk) ]
  • Making an AND gate: rough computation of energy and entropy deltas
  • Composing gates: making a wire
  • Reading the result optically: fluorophore and quencher
  • Implementing a reaction gate
  • Implementing monotonic gates (AND and OR)
  • Handling NOT gates with dual rails
  • Moving NOT gates to the top
  • Robustness: preventing leaking:
    • Fixing molecular synthesis imperfection
    • Using double long domains (DLD)
  • Presenting Breadboard 1.0
• Exercise sessions [ HW3 ]
  1. DNA circuits
  2. Building shapes with oritatami

Lecture 8: Oritatami: A computational model for cotranscriptional molecular folding [ Slides ]

Movies & animations: [ RNA folding (slide 11) | Oritatami step 1 (slide 15) 2 (slide 21) 3 (slide 25) | Oritatami counter (slide 30) | Module G (slide 102) ]

• Co-transcriptional RNA folding experiment
• Oritatami
  • The model
  • A binary counter
  • Proving the binary counter
• Complexity
  • NP-hardness of the rule design problem
  • Fixed parameter linear-time algorithm of the rule design problem
• Efficient Turing machine simulation in oritatami
  • Skipping cyclic tag systems (SCTS)
  • Simulating SCTS with oritatami
  • Proving the correctness of the simulation
  • Oritatami programming toolbox: switchback/glider, offsets, exponential coloring & socks
  • Proving the correctness of the implementation
• Exercise sessions
  1. HW2 exercise 1
  2. HW3 exercise 2

Lecture 1 Introduction to Approximation Algorithms

• Introduction to the Course
• Optimization problems & Approximation Algorithms
• Set Cover (two LP-based approximation algorithms)
• Min Cut of Karger
• First Assignment PDF

Lecture 2 Chernoff Bound

• Chernoff Bound
• Congestion Minimization
• 3-Coloring in Dense Graph
• Travelling Salesman Problem (Christofides algorithm)
• Bin-Packing
• Second Assignment PDF

Lecture 3 Max Cut

• An algorithm of Fernandez de la Vega for max cut in dense graph (an exposé of Nicholas Schabanel is here PDF)
• Third Assignment PDF

Lecture 4 Semi-Definite Programming

• Goemans-Williamson Max-Cut
• Integrality Gap

Lecture 5: Introduction to molecular programming & Tile assembly systems (Oct 18) Video

• Introduction to the course [0:00:00]
• A little history of the field [0:09:14]
• Tile assembly systems [0:35:41]
• A binary counter [0:51:50]
• Minimizing the assembly time [1:10:01]
• Exercises session [1:51:44] HW1 PDF
  1. Guess the assembly 1
  2. Guess the assembly 2
  3. A counter
  4. Staged assembly of a candelabrum
  5. Expected assembly time & rank of a construction
  6. Minimum number of tiles for the families of squares and rectangles

Lecture 6: Universality in tile assembly systems (Oct 25) Video

• Simulating Turing Machines at T°=2 [0:00:00]
• Kolmogorov Complexity [0:29:02]
• Lower Bounding the minimal number of tiles to hardcode the input seed with Kolmogorov complexity [0:54:16]
• Optimal number of tiles for hardcoding the seed [1:06:43]
• Exercises session [1:42:54] HW2 PDF
  1. HW1 exercise 5: Assembly time = O(rank) w.h.p.

Lecture 7: Universality in Tile Assembly and Oritatami Systems (Nov 8) Video

• Tile sets self-assembling an arbitrary shape [0:00:00]
• Turing-Universal tile set in 3D at T°1 [0:29:05]
• Intrinsically universal tile set in 2D at T°2 [0:49:06]
• Magic Powder [1:11:56]
• Oritatami: A model for co-transcriptional folding [1:15:19]
• Exercise session:
  1. Designing DNA origami using cadnano [2:19:08]

Lecture 8: Some experimental achievements in DNA programing (Nov 15) Video

• The equipment: Pipetters, thermocycler & AFM microscopy [0:00:00]
• A tour of built DNA nano-structures [0:39:17]
• DNA single stranded tiles [1:00:41]
• Stacking interactions [1:01:29]
• Strand displacement [1:03:55]
• Exercise session:
  1. cadnano is back [1:11:49]
  2. HW1-6: Tile set of minimimum size for Squares and Rectangles [1:15:28]
  3. HW2-1: Discrete slope [1:31:01]
  4. HW2-2: Window movie lemma [1:42:40]

Lecture 1 [Wed 14/9/2016 16:15-19:15] Introduction to Approximation Algorithms Video

• Introduction to the Course
• Optimization problems & Approximation Algorithms
• About Hardness of approximation
• Approximation Algorithms for Metric TSP
• Exercices Session 1 PDF
  1. 3/2-Approximation for Metric TSP
  2. Cost-based approximation for Vertex Cover
  3. Maximum Arc-Disjoint Paths (1)

Lecture 2 [Wed 21/9/2016 16:15-19:15] Mathematical Programming 1: Linear programming Video

• Mathematical Programming [0:00:00]
• Introduction to Linear Programming [0:01:45]
• First Example: Max-CUT as an Integer Program [0:07:04]
• LP Relaxation for Max-CUT & Randomized Rounding [0:38:16]
• Max-SAT: Random Assignment [1:09:26]
• Max-SAT: Randomized Rounding [1:24:23]
• Max-SAT: Combining both Algorithms into One [2:12:33]
• Exercises Session 2 PDF
  • Maximum Arc-Disjoint Paths (2)
  1. Dumb Algorithm for Max-SAT
  2. Metric k-Center
  3. SDP Approximation for Weighted Max-2SAT

Lecture 3 [Wed 28/9/2016 16:15-19:15] Mathematical Programming 2: Semi-definite / Vector programming Video

• 0. Introduction [0:00:00]
• 1. A quadratic program for Max-CUT [0:02:09]
• 2. Relaxing a Quadratic Program as a Vector Program [0:10:17]
• 3. Vector Programs = Semi-Definite Programs [0:16:14]
• 4. VP is indeed a relaxation of integer QP [0:27:28]
• 5. Rounding VP: the Random Hyperplane Technic [0:38:43]
• 6. Analysis of the Random Hyperplane Algorithm [1:10:09]
• Exercise Session 3: PDF
  • Exercise HW2-1: A Dumb Algorithm for Max-SAT [1:31:47]
  • Exercise HW2-3: SDP-Approximation for Max-2SAT [1:39:12]
  1. Randomized Rounding for Set Cover

Lecture 4 [Wed 5/10/2016 16:15-19:15] Polynomial Time Approximation Schemes Video

• 0. (F)PT(R)AS: (Fully) Polynomial-Time (Randomized) Approximation Schemes [0:00:00]
• 1. A FPTAS for the Knapsack Problem [0:10:31]
• 2. A FPTRAS for Max-Cut in α-Dense Graphs [1:05:27]
• Exercise Session 4: PDF
  1. A PTAS for the Minimum Cost Overflow Problem

Lecture 5 [Wed 26/10/2016 16:15-19:15] Nature Programming: Abstract Tile Assembly Model Slides

• 0. Introduction to Nature programming & DNA assembly
• 1. Abstract Tile Assembly Model
• 2. A binary counter
• 3. Minimizing the assembly time for squares & cubes
• Exercise Session 5: PDF
  1. Guess the result of the algorithmic Self-Assembly (I)
  2. Guess the result of the algorithmic Self-Assembly (II)
  3. Counter at T°=2
  4. Staged assembly scheme at temperature T°=1
  5. Concentrations, Rank and Assembly time
  6. Minimum number of tile types for squares and rectangles

Lecture 6 [Wed 2/11/2016 16:15-19:15] Nature Programming: Universality in Tile Assembly Systems Video

• 0. HW4: NP-completeness & Optimization Problems [0:00:00]
• 1. Turing Universality in tile assembly systems [0:05:43]
• 2. Turing universality at T°=2 [0:12:31]
• 3. Turing universality at T°=1 [0:36:19]
• 4. Minimizing the number of tiles to build a shape [1:19:04]
• Exercise Session 6: [2:31:39]
  1. HW5(2): Assembly time, rank & concentrations

Lecture 7 [Wed 9/11/2016 16:15-19:15] Nature programming: Intrinsic Universality & Other Models including Oritatami Video

• 0. Theory vs Practice [0:00:00]
• 1. Intrinsic Universality of Tile Assembly Systems at T°=2 [0:04:59]
• 2. One (Polygonal) Tile is Enough! [0:39:20]
• 3. Other Models: Bio-Logical Circuits [0:43:00]
• 4. Nubots: a Model for Molecular Reconfiguration [0:49:43]
• 5. About Experiments: Nanotubes that Compute [0:54:07]
• 6. Oritatatami: one Molecule that computes co-transcriptionally [0:58:26]
  • 6.1 Experiment: Synthetic RNA Co-Transcriptional Folding-based Meshes [0:58:54]
  • 6.2 Oritatami: A Model for Co-Transcriptional Folding [1:11:58]
  • 6.3 Oritatami: How to Compute? [1:18:02]
  • 6.4 Oritatami: Rule Design is NP-hard but Fixed Parameter Tractable [1:31:55]
  • 6.5 Oritatami Systems simulate efficiently Turing machines [1:41:20]
  • 6.6 Oritatami: How to Prove the Correctness? [2:04:36]
  • 6.7 Oritatami: Conclusion [2:28:48]
• No Exercise Session

Lecture 8 (last) [Wed 9/11/2016 16:15-19:15] Nature programming: Experiments

• 1. Description of the recent experiment of Damien Woods et al on building nanotubes implementing 6-bit circuits computation
• 2. Introduction to CADNano, a DNA Origami Designer
• 3. Introduction to NUPack, a DNA/RNA strand(s) energy/partition function calculator

Lecture 1 [18/9/2014] NP-completeness, Hardness of approximation & Approximation algorithms Video 1 2 3

• Introduction to approximation algorithms
• NP-completeness, PCP theorem & hardness of approximation
• Definitions: Optimization problem & Approximation
• Hardness of approximation for non-metric TSP
• A 2-approximation for metric TSP
• A 3/2-approximation for metric TSP
• Exercise session 1 PDF
  1. Max-Cut: randomized 2-approximation and greedy approximation by the conditional expectation method
  2. Coloring 3-colorable graphs
  3. Cost-based 2-approximation for Vertex Cover

Lecture 2 [25/9/2014] Introduction to Integer Programming, Linear Relaxation and Rounding Video 1 2 3

• Max-SAT
• Random solution to Max-SAT
• A (1-1/e)-approximation based on a randomized rounding of a solution to a linear program for Max-SAT
• Mixing both algorithms yield a 3/4-approximation
• Exercise session 2 PDF
  1. Dumb algorithm for Max-SAT
  2. Simple rounding f-approximation for Set Cover
  3. Randomized rounding (ln(n)+O(1))-approximation for Vertex Cover
  4. 2- and 3-approximations for Minimum Weighted Sum of Completion Time Scheduling with dependencies and with and without release dates

Lecture 3 [16/10/2014] PTAS: Polynomial Time Approximation Schemes Video 1 2 3

• Euclidean Traveling Salesman problem
• Exercise session 3 PDF
  1. A Fully Polynomial Time Approximation Scheme (FPTAS) for the Knapsack Problem
  2. A Constant Time Approximation Scheme (CTAS) for the size of a maximal matching in a constant degree graph

Lecture 4 [23/10/2014] Introduction to semi-definite programming Video 1 2 3

• From quadratic formulation to vector program
• Rounding with cutting hyperplanes for Max-Cut
• A O(n^1/3)-approximation for coloring 3-colorable graphs
• Exercise session 4 PDF
  1. How to draw unit vector uniformly at random
  2. A O(n^1/4)-approximation for coloring 3-colorable graphs

Lecture 5 [30/10/2014] Introduction to Lasserre's hierarchy (1/2) Video 1 2 3

• Important properties of semi-definite matrices
• Equivalence of vector programs and semi-definite programming
• Definition of Lasserre's hierarchy
• First properties of the solutions
• Decomposition: lemma and theorem
• No exercise session today

Lecture 6 [6/11/2014] Lasserre's hierarchy (2/2) Video 1 2 3

• Decomposition theorem
• First examples of applications
• Exercise session 5 PDF
  1. Lasserre support lemma
  2. Scheduling with precedence constraints: application of Lasserre decomposition
  3. A (1-ε)ln(m)-approximation for Set Cover with Laserre hierarchy

Lecture 7 [13/11/2014] Natural algorithms: the Small-World phenomenon Video 1 2 3

• Sociological context: Milgram's experiment
• First Small World models
• Kleinberg's augmented grid model
• Case α < 2: Long-range links are too messy
• Case α > 2: Long-range links are too short
• Case α = 2: The greedy algorithm
• Small-World emergence: the Move-and-Forget model
• No exercise session today

Lecture 8 (last) [20/11/2014] Algorithmic self-assembly & Non-clairvoyant scheduling Video 1 2 3

• Simulation of routing algorithms in Kleinberg's small world model
• Algorithmic self-assembly PDF
  • Winfree's model and Rothermund's realizations
  • Cube construction in real-time (order, signals and synchronization)
• Non-clairvoyant scheduling PDF
  • Introduction to online algorithms
  • Jeff Edmonds's non-clairvoyant model
  • Competitive hardness of approximation
  • Competitive analysis with resource augmentation: LAPS_β algorithm
  • Extension to precedence constraints
• No exercise session today

1. Introduction to Approximation Algorithms
   • P vs NP, a refinement of NP-completeness: Inapproximability results
   • Definitions of Optimization problems and Approximation algorithms
   • General principles for obtaining approximation algorithms
2. An exemplary example: the Travelling Salesman Problem
   • Definition of TSP
   • Inapproximability of general TSP unless P = NP
   • A first 2-approximation algorithm (MST-based)
   • Cristofides algorithm: a 3/2-approximation algorithm
   • Family of tight instances for both algorithms

1. Random Cut for Max-Cut and derandomization by the conditional expectation method
2. 2-approximation for Metric Steiner Tree and isofactor reduction from general to metric

1. Linear Programming
   • Introduction, LP Relaxation, First rounding (Vertex-Cover)
   • Duality and Complementary Slackness Conditions
   • Application: primal-dual algorithm for Vertex-Cover & Maxim-um/-al Matching
   • (Note for next year: primal dual algorithm for Set-Cover would have been a better choice)

1. Basic duality manipulation
2. A randomized LP-rounding algorithm for Set-Cover

1. Definition of PTAS, PTRAS, example of dependence in ε
2. Dense Max-Cut
   • definition
   • the partition of the cut covers a constant fraction of the nodes
3. A first algorithm
   • A non-adaptative randomized sampling based algorithm
   • An example on why it does not work
4. The PTRAS
   • Description of the algorithm
   • Exhaustive guessing
   • Hybridation
   • Algorithmic analysis
   • Probabilistic analysis
   • Final theorem

1. A Fixed-Parameter Tractable (FPT) algorithm for k disjoint triangles
2. A Constant Time Approximation Scheme (CTAS) for the size of a maximal matching

1. A little bit of history
2. Gap problems and Hardness of approximation
3. The CSP: Graph Constraints Satisfaction Problem
4. Overview of the Gap amplication process 2.a) definition
5. A key tool: Expander graphs I
6. Step 1: Degree uniformization
7. Step 2: Expanderization
8. Expander graphs II: spectral theory and random walks
9. Step 3: Gap amplification
10. Step 4 (last): Alphabet reduction
11. Gap-preserving reductions

1. Gap-preserving reductions for Vertex-Cover and Steiner Tree
2. Random walks on expanders