Section outline

  • 7) Δευτέρα 27 Οκτωβρίου

    • Fine-Grained Complexity: ETH and SETH, the Sparsification Lemma and applications. SETH implies ETH via sparsification. Fine-Grained reductions.
     
     

    8) Πέμπτη 30 Οκτωβρίου

    • Fine-Grained Complexity: Fine-Grained reductions. Main barriers, 3SUM, SETH and APSP hardness, and the web of fine-grained reductions. Orthogonal Vectors and variations. SETH hardness of OV, the Hitting Set Conjecture. Hitting Set Conjecture implies Orthogonal Vectors Conjecture.

    Μπορείτε να διαβάσετε: