IRR: Theoretical Computer Science

Theoretical Computer Science

What differentiates the sub-area from the other programmes on the Informatics MSc portfolio?

Theoretical Computer Science (TCS) is the use of mathematical thinking and techniques to understand computer science. It ranges from logical, even philosophical, questions such as ‘what is computation?’, to quite practical questions such as ‘how can we know whether our algorithm is the fastest possible for this problem?’. 

Are there go-to sources to find reviews and perspectives on these research topics. i.e. are there any good review journals that are worth browsing to get topic overviews.

The recording of the semesters and workshop organized at the Simon Institute for the Theory of Computing https://simons.berkeley.edu/ are a great place to look for tutorials for beginners and at the same discussions on rapidly growing areas of research.

What are the key journals or conferences in the field for finding high quality research papers in these topics 

Algorithms and Complexity: 

• STOC (http://acm-stoc.org)  

• FOCS (http://ieee-focs.org/) 

• Journal of the ACM (https://dl.acm.org/journal/jacm)  (applies to every subheading here)

• SIAM Journal on Computing (https://www.siam.org/publications/journals/siam-journal-on-computing-sicomp)

• ICALP track A (https://eatcs.org/index.php/international-colloquium)

• Theoretical Computer Science A (https://www.journals.elsevier.com/theoretical-computer-science)

Logic, Semantic and Concurrency:

• LiCS (https://lics.siglog.org/)

• Theoretical Computer Science  B (https://www.journals.elsevier.com/theoretical-computer-science)

• Logical Methods in Computer Science (https://lmcs.episciences.org/)

• Mathematical Structures in Computer Science (https://www.cambridge.org/core/journals/mathematical-structures-in-computer-science)

• CONCUR (https://link.springer.com/conference/concur)

• Information and Computation (https://www.journals.elsevier.com/information-and-computation)

• FoSSaCS (https://dblp.org/db/conf/fossacs/index.html)

• ICALP track B (https://eatcs.org/index.php/international-colloquium)

Programming Languages and Foundations:

• PACMPL (POPL,ICFP,OOPSLA) (https://dl.acm.org/journal/pacmpl)

• PLDI (https://sigplan.org/Conferences/PLDI)

• PROGRAMMING (https://programming-journal.org/)

• ECOOP (https://ecoop.org)

• ESOP (https://dblp.org/db/conf/esop/index.html)

• JFP (https://www.cambridge.org/core/journals/journal-of-functional-programming)

Verification, Testing, and Model Checking:

• CAV (https://i-cav.org/)

• ITP (https://itp-conference.github.io/)

• JAR (https://www.springer.com/journal/10817)

• QEST: Quantitative Evaluation of Systems www.qest.org

• Performance Evaluation

• ACM Transactions of Modelling and Simulation 

Are there any particular high profile or rapidly growing research areas in the programme that you would suggest might be worth looking at for potential IRR themes. 

Algorithms and Complexity: 

• High dimensional expanders 

Programming Languages and Foundations:

• Algebraic Effects and Handlers

• Program Synthesis

• Smart Contracts

• Gradual Typing

Verification, Testing, and Model Checking:

• Compiler Verification

• Specification and verification of processor architectures

• Use of quantitative evaluation/verification with machine learning in a variety of different ways (verification of the ML/using ML to make the verification more efficient/….)