What Oded Goldreich says complexity theory is (From his complexity page): http://www.wisdom.weizmann.ac.il/~oded/cc-over.html Possible Topics and Papers 1. Fine Grained Complexity Getting exact bounds for concrete problems in P and NP https://cseweb.ucsd.edu/~russell/FGCA/ https://simons.berkeley.edu/programs/complexity2015 https://people.csail.mit.edu/virgi/6.s078/lecture1.pdf https://people.csail.mit.edu/virgi/6.s078/lecture2.pdf https://people.csail.mit.edu/virgi/6.s078/paperlist.html Course from Max Plank Institute 2. ASC (Automatically Scalable computation) How to Speed up Computation by Trading Time for Space isca-sub2015.pdf hotos13-paper2.pdf Video: https://www.devflix.watch/video/MHZDXC4zJ0c ASPLOS 2014 - 19th International Conference on Architectural Support for Programming Languages and Operating Systems https://dl.acm.org/doi/10.1145/2541940.2541985 3.Quantum Complexity i. Scott A's blog about the power of 2 provers with infinite entanglement https://www.scottaaronson.com/blog/?p=4512 Vidick's post: https://mycqstate.wordpress.com/2020/01/14/a-masters-project/ A readable paper is hard to find ii. Quantum Supremacy: Google's claim , IBM disagrees Algorithms which can be implemented on a QC and which achieve exponential speedup over classical implementations. 4. Fixed Parameter Tractability and other methods to speed up P-complete (hard to parallelize) problems Coloring: Bannach, Stockhusen and Tantau, 2015. Fast parallel fixed-parameter algorithms vis color coding. https://arxiv.og/abs/1509.06984 Flum and Grohe Parameterized Complexity Theory Springer, 2006 A nicely written paper on kernelization the coloring problem; Chor B., Fellows M., Juedes D. (2004) Linear Kernels in Linear Time, or How to Save k Colors in O(n2) Steps. In: Hromkovi J., Nagl M., Westfechtel B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg. Can be found at: https://www.semanticscholar.org/paper/Linear-Kernels-in-Linear-Time%2C-or-How-to-Save-k-in-Chor-Fellows/dc88f60aab597ee7cc18fc615bbf15e7788537f5 Circuit Complexity Consider Boolean circuits over the full binary basis. We prove a (3 +1/86)n lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the 3n -o(n) lower bound of Norbert Blum from 1984. A better-than-3n lower bound for the circuit complexity of an explicit function Magnus Gausdal Find1, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov 6. Sensitivity conjecture Conjecture: For every Boolean function f:{0,1}^N --> {0,1}, the sensitivity of f is the maximum of the number of bit, over all 2^n input strings, such that flipping them changes the value f. (The sensitivity is at most polynomially smaller than several other complexity measures of f, including block sensitivity, degree as a real polynomial, and classical and quantum query complexities. ) This conjecture can be proved from the following fact, recently proved by Hao Huang but a known implication since 1992. Let S be any subset of the n-dimensional Boolean hypercube, {0,1}^nn, which has size 2^(n-1)+1. Then there must be a point in S with at least n^c neighbors in S, here 0