Theoretical computer science

Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the theoretical areas precisely. The ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History of computer science While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of neural networks and parallel distributed processing were established. In 1971, Stephen Cook and, working independently, Leonid Levin, proved that there exist practically relevant problems that are NP-complete – a landmark result in computational complexity theory. With the development of quantum mechanics in the beginning of the 20th century came the concept that mathematical operations could be performed on an entire particle wavefunction. In other words, one could compute functions on multiple states simultaneously. This led to the concept of a quantum computer in the latter half of the 20th century that took off in the 1990s when Peter Shor showed that such methods could be used to factor large numbers in polynomial time, which, if implemented, would render some modern public key cryptography algorithms like RSA insecure. Modern theoretical computer science research is based on these basic developments, but includes many other mathematical and interdisciplinary problems that have been posed, as shown below: Algorithm An algorithm is a step-by-step procedure for calculations.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (59)

Related people (38)

Related concepts (139)

Related courses (56)

Related lectures (213)

Related MOOCs (5)

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

MATH-381: Mathematical logic

Branche des mathématiques en lien avec le fondement des mathématiques et l'informatique théorique. Le cours est centré sur la logique du 1er ordre et l'articulation entre syntaxe et sémantique.

PHYS-512: Statistical physics of computation

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and

Distributed Computation I

Explores distributed computation between two parties in a distant setting.

Quantum Computation Delegation

Covers the concept of quantum computation delegation and the relationship between MIP and RE, addressing common FAQs and discussing helpful materials and interactions with quantum devices.

PhD Program in Computer Science: EDIC Overview

Gives an overview of the EPFL doctoral program in Computer Science, emphasizing its international recognition and alumni success.

Numerical Analysis for Engineers

Ce cours contient les 7 premiers chapitres d'un cours d'analyse numérique donné aux étudiants bachelor de l'EPFL. Des outils de base sont décrits dans les chapitres 1 à 5. La résolution numérique d'éq

Numerical Analysis for Engineers

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimizat

EPFL2022

Disentangling Light- and Temperature-Induced Thermal Effects in Colloidal Au Nanoparticles

Majed Chergui, Lijie Wang, Davood Zare

We present temperature-dependent (from room temperature to 80 degrees C) absorption spectra of Au/SiO2 core-shell nanoparticles (NPs) (core diameter: similar to 25 nm) in water in the range from 1.5 t

AMER CHEMICAL SOC2022

Identifiability and Generalizability from Multiple Experts in Inverse Reinforcement Learning

Volkan Cevher, Luca Viano, Paul Thierry Yves Rolland, Boris Nikolov

While Reinforcement Learning (RL) aims to train an agent from a reward function in a given environment, Inverse Reinforcement Learning (IRL) seeks to recover the reward function from observing an expe

2022

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and .