CMPT 881 - Average-Case Complexity - Spring'11
- Apr 16. HW 2 is now graded; see the gradebook for your
grade. (Everyone solved all problems, so there is no need for me to
post solutions online.) Please submit your HW 3 on or before the
deadline, as I'm required to submit the final grades for the course by
Apr 22! So no deadline extensions this time.
-
Apr 8. HW 3 is now available. It's due April 21 (Thu); you can drop it off at my office, before 5pm (slide it under the door if I'm not in).
You can also submit it earlier and/or by emailing me the pdf file. The homework is not hard.
Please solve it by yourself, without consulting the internet! Ask me
if you have any questions (or something is not clear in the problem description).
- Apr 5. We start project presentations this Thursday, at 15:45 in TASC 1 #9005 (Shawn). Then we
have presentations next Tue, Wed, and Thu, starting at 11 am, also in TASC 9005. Everyone is expected to attend.
You'll have 40-45 min for your talk
(so you may want to use slides, but just blackboard is fine, if you manage your time wisely). Your goal should be
to explain some neat facts to your fellow students in the clear and understandable way; don't squeeze too
much material into your presentation!
- Mar 30. HW 2 due date is postponed till next Tuesday.
- Mar 27. The grades for HW 1 are now in the gradebook; I'll bring th\
e graded assignments to the next class. Also, the solutions to HW 1 are now
posted.
- Mar 16. HW 2 is now posted (due Mar 31). No classes next week (as I'll be away at a conference).
- Feb 24. No classes next week (Mar 1 & 3). Please start
thinking about your project for the course (see below for the project
description).
- Jan 20. Homework 1 is
now posted (see below); it is due Feb 10. Also, the scribe notes for Lecture 2 are now also posted (thanks to Mert!).
- Jan 3. The first lecture is on Thu, Jan 6.
Course description
Is it easy to generate a hard problem? For example, is a random
problem (e.g., a random 3-SAT formula) hard to solve? Assuming NP is
different from P, can it still be the case that NP is efficiently
solvable on average (for any natural distribution of instances)? Is it
possible to base cryptography on the worst-case hardness assumption
that NP is different from P?
In this course, we will study these and related questions. The goal of
the course is to provide the "big picture" for various aspects of the
modern theory of average-case complexity. We will discuss random k-SAT
and other natural problems, see the "state of the art" for the known
algorithms, and highlight the important algorithmic challenges. We
will also discuss the relationship between worst-case and average-case
hardness, and connections to cryptography.
Topics
- Average-case completeness
- Worst-case to average-case reductions
- Impagliazzo's Five Worlds
- Random k-SAT and its variants
- Algorithmic tools (local search, spectral partitioning, etc.)
- Other (to be decided based on the interests of the class)
Course Text: There is no textbook for this
course. We will use some surveys and research articles; some useful links will be posted (see the bottom of the page).
Grading There will be 3-4 homework assignments, and a project; the students are also expected to take turns at scribing the lectures. The details to be discussed in the first week of the class.
Instructor:
Valentine Kabanets (kabanets@cs.sfu.ca), Office:
TASC I #8011
-
Lectures: Tue 14:30-16:20 and
Thu 14:30-15:20, both in AQ 5019.
-
Office Hours: please email me if you want to meet.
Important dates
-
Assignments due: Feb 10 (HW 1), Mar 31 (HW 2)
Please choose one research paper to read, and present it in class
(using blackboard or slides, as you wish); expect to be given about
30-50 min for your presentation. Almost any paper related to
"average-case complexity" is possible as a project. However, please
consult with me to for the approval of your course project! To choose
a paper, you can consult the surveys by Bogdanov-Trevisan and
Achlioptas (see below) for some important papers in the area. You can
also do your own search for the paper you find interesting. Once you
have some candidate paper(s), please talk to me to finalize your
project. Also, if you can't seem to find a good paper you would like
to read, please talk to me.
- Jan 6: Intro (why average-case complexity?)
-
Jan 11: Lecture 2.
Definitions of "average-case easy" (AvgP, HeurP);
restricted distributions (P-computable and P-samplable); equivalence
between AvgP and P for the universal (Kolmogorov) distribution
- Jan 13: Lecture 3.
Definition of AvgP-reductions; Bounded Halting
(BH) problem and the uniform distribution U over BH; sketch of the
completeness result for (BH,U)
- Jan 18: Lecture 4.
Proof that (BH,U) is complete for (NP, PComp)
under AvgP-reductions; Search vs. Decision for (NP,U): definitions of
HeurBPP and efficient randomized search heuristics
- Jan 20: Lecture 5.
Proof that if (NP,U) is in HeurBPP, then all search
problems for (NP,U) have efficient randomized search heuristics (the
definition of universal hash function families, the Valiant-Vazirani
isolation lemma)
- Jan 25: Lecture 6.
Randomized reduction between search problems;
proof that every (NP,PSamp)-search problem is reducible to
(NP,U)-Search problem via randomized reduction (warmup cases)
- Jan 27: Lecture 7.
Proof that every (NP,PSamp)-search problem is
reducible to (NP,U)-Search problem via randomized reduction
(completed); Corollary: (BH,U)\in HeurBPP implies there is no OWF;
Leftover Hash Lemma (x -> (h(x),h) is a randomness extractor for
distributions with certain amount of entropy/randomness)
- Feb 1:
Lecture 8.
Impagliazzo's Five Worlds (Algorithmica,
Heuristica, Pessiland, Minicrypt, and Cryptomania); OWF vs. "hard
solved SAT-instances"; Levin's universal search algorithm, and
"OWF-complete" function f_{Levin}; proof that "If there is a OWF,
then f_{Levin} is weakly OWF".
- Feb 3:
Lecture 9.
weak vs. strong OWF: Existence of weak OWFs implies the
existence of strong OWFs (direct-product construction & its analysis).
- Feb 8:
Lecture 10. Impagliazzo's Hardcore Lemma (with Holenstein's
proof).
- Feb 10: Lecture 11.
Yao's XOR Lemma (via Impagliazzo's
Hardcore Lemma).
- Feb 22: Lecture 12.
Random k-SAT (definition; threshold phenomenon).
- Feb 24: Lecture 13.
Random k-SAT threshold: The second-moment method.
-
Mar 8: Lecture 14.
Random k-SAT satisfiability threshold: The
second-moment method (cont'd) (NAE-k-SAT, and k-SAT); the random k-SAT solution space
geometry.
-
Mar 10: Lecture 15.
The random k-SAT and k-XORSAT solution space (cont'd);
DPLL algorithm analysis (Unit Clause heuristic)
- Mar 15: Unit Clause heuristic analysis (cont'd): differential equations, and branching processes.
- Mar 17: WalkSAT algorithm analysis for random k-SAT: success up to density 2^k/k^2.
- Mar 29: Planted random k-SAT: Spectral algorithm for constant density.
- Mar 31:
Spectral partitioning algorithm & analysis (based on Trevisan's
lecture notes)
- Apr 5: Spectral partitioning (cont'd); decoding of expander codes.
- Apr 7: Decoding of expander codes (cont'd). Some open problems.