What Oded (Goldreich) says complexity theory is (From his complexity page): http://www.wisdom.weizmann.ac.il/~oded/cc-over.html IBM Almaden Research Center 2010 Non-Uniform ACC Circuit Lower Bounds Ryan Williams ---------------------------------- Sensitivity conjecture (Huang's proof) https://arxiv.org/abs/1907.00847 knuth's proof https://www.cs.stanford.edu/~knuth/papers/huang.pdf N. Nisan, M. Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complexity, 4 (1992), 46227 D. Rubinstein, Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), 297. ---------------------------------------------------- 3n circuit lower bound https://golovnev.org/papers/rdq.pdf https://www.nist.gov/publications/better-3n-lower-bound-circuit-complexity-explicit-function 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 Quantum Computation Scott's blog aboput 2 provers with infinite entanglement https://www.scottaaronson.com/blog/?p=4512 Vidicks post: https://mycqstate.wordpress.com/2020/01/14/a-masters-project/ Quantum Supremacy Fine-grained complexity A nice, though quite long survey paper can be found at, https://drops.dagstuhl.de/opus/volltexte/2019/10243/pdf/LIPIcs-STACS-2019-4.pdf Other papers and cites: 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 Sunflower theorem S. Lovett and J. Zhang. DNF sparsification beyond sunflowers. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 454 https://homes.cs.washington.edu/~anuprao/pubs/sunflower.pdf Coding for Sunflowers Anup RaoUniversity of Washington anuprao@cs.washington.edu January 8, 2020 Tantau-color-coding-FPT https://arxiv.org/pdf/1509.06984.pdf Paper on FTP of K-coloring. https://www.semanticscholar.org/paper/Linear-Kernels-in-Linear-Time%2C-or-How-to-Save-k-in-Chor-Fellows/dc88f60aab597ee7cc18fc615bbf15e7788537f5 A book written by committee and an overview of FTP idea, theory and practice: (Chapter 13 is Nadya's talk) Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Micha Pilipczuk and Saket Saurabh Exacthttps://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf exponential algorithms for NP-hard problems by Gerhard Woeginger https://www.win.tue.nl/~gwoegi/papers/exact.pdf Open problems around exact algorithms Author links open overlay panelGerhard J.Woeginger https://reader.elsevier.com/reader/sd/pii/S0166218X0700128X?token=E3CA7780E042DBC25F4050CB69A0B299B8738CE883FA1DE2D8245EA85994C7EF13646A38884345B8EC6DEAECEB81C617 Lecture slides - Some simple tricks to design exact algorithms Fedor V. Fomin http://fileadmin.cs.lth.se/cs/Personal/Andrzej_Lingas/fomin.pdf Kratsch Bad algorithms - slides on exponential algorithms http://community.dur.ac.uk/acid.2010/Kratsch.pdf Paper by Rajesh Chitnis, Fedor V. Fominb, Daniel Lokshtanovb, Pranabendu Misrac, M. S. Ramanujan, on Faster Exact Algorithms for Some Terminal Set Problems at https://sites.cs.ucsb.edu/~daniello/papers/exactMultiwayCutJ.pdf D. Kratsch, H Muller, I Todinca Feedback vertex set on AT-free graphs, Discrete Applied Mathematics 156 (10) (2008) 1936-1947