\item(?) Derandomization Somewhat small. I suggest introducing "Randomness in TCS" and removing this one. \item(?) Hardness amplification Small subtopic. I suggest removing. \item(!!) Hardness of approximation Large and important topic, keep. \item() Interactive proofs \item() PCP These two are essentially the same and almost solely used for "hardness of approximation". They are however large enough to justify a separate subtopic so I suggest merging these two into just "Proof systems". Questions about MA may very well go in here as well.
login/create account
Drupal
CSI of Charles University
Proposed topics (cont 5)
(continuation of prev post)
Subtopics of complexity: Current ones:
\item(?) Derandomization Somewhat small. I suggest introducing "Randomness in TCS" and removing this one. \item(?) Hardness amplification Small subtopic. I suggest removing. \item(!!) Hardness of approximation Large and important topic, keep. \item() Interactive proofs \item() PCP These two are essentially the same and almost solely used for "hardness of approximation". They are however large enough to justify a separate subtopic so I suggest merging these two into just "Proof systems". Questions about MA may very well go in here as well.
(see next post for cont)