Prof. Elkind joined the Oxford Computer Science Department in 2013. In 2014 she was awarded an ERC Starting Grant. Prior to coming to Oxford she was an Assistant Professor at Nanyang Technological University (Singapore). Prof Elkind obtained her PhD from Princeton University in 2005, and was a postdoctoral research fellow at the University of Warwick, University of Liverpool and Hebrew University of Jerusalem, as well as a lecturer at University of Southampton.
The goal is to provide students with tools to classify the computational problems they face according to their worst-case complexity as well as with methods to deal with computationally intractable problems. During this module, the students will learn about fundamental limits of computation and be exposed to several formal models of computation.
SKILLS:
- Algorithms
- Game theory
- Voting
- Auctions
- Cooperation
DATE: 22 May - 9 June, 2017
DURATION: 3 Weeks
LECTURES: 3 Hours per day
LANGUAGE: English
LOCATION: Barcelona, Harbour.Space Campus
COURSE TYPE: Offline
WHAT YOU WILL LEARN
ABOUT EDITH
HARBOUR.SPACE
The module familiarizes the students with fundamental notions of computability and complexity, starting with basics such as formal languages, Turing machines and the class NP, and then exploring various measures of complexity. Understanding limits of computation is an integral part of computer science education.
EDITH ELKIND
HARBOUR.SPACE UNIVERSITY
DATE: 22 May – 9 June, 2017
DURATION: 3 Weeks
LECTURES: 3 Hours per day
LANGUAGE: English
LOCATION: Barcelona, Harbour.Space Campus
COURSE TYPE: Offline
COMPLEXITY THEORY
BIBLIOGRAPHY
COURSE OUTLINE
Session 1
Finite automata and regular languages:
Definition of a finite automaton, formal languages, examples of languages that can be recognized by a finite automaton, regular languages, closure under regular operations.
Session 2
Non-determinism; equivalence between regular expressions and NFA:
Definition of a non-deterministic finite automaton, examples of languages that can be recognized by a non-deterministic finite automaton, equivalence between DFA and NFA, regular expressions, pumping lemma.
Session 3
Pushdown automata and context-free grammars:
Definitions of context-free grammars and pushdown automata, examples, equivalence between context-free languages and languages recognizable by PDA, pumping lemma for PDA, role of determinism.
Session 4
Turing machines:
Definition of a Turing machine, examples of Turing machines, non-determinism, Church-Turing thesis, equivalence of different variants of Turing machines.