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