The Foundations of Computer Science Research Group (FoCS) recently hosted world-renowned researchers in the areas of cryptography and algorithms at the AlgoUK workshop. The event, held on September 17-18 2019, attracted over 130 participants.
Adi Shamir (Weizman Institute), co-inventor of public key cryptography and Turing Award winner, talked about his recent work on understanding the fragile behaviour of machine learning systems. Madhu Sudan (Harvard), winner of the Nevanlinna and Gödel awards, talked about new constructions of "polarizing" codes for communication. Svetla Nikova (KU Leuven) talked about recent work on achieving security against powerful adversaries.
Other speakers at the two day event were Adrià Gascon (Google/The Alan Turing Institute), Mary Cryan (Edinburgh), Paul Goldberg (Oxford), Christian Ikenmeyer (Liverpool), Christian Konrad (Bristol), Daniel Paulusma (Durham) and Thomas Sauerwald (Cambridge).
Slides and abstracts for the talks are available at the workshop website, https://algouk.wixsite.com/warwick2019.
We are pleased to report that members of the department's Theory and Foundations research theme have had 7 papers accepted to the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, to be held in Salt Lake City, Utah, USA, January 5-8, 2019. SODA is the premier international conference on algorithms research, and the papers are:
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal by M. S. Ramanujan, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
- An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs by Sayan Bhattacharya, Janardhan Kulkarni
- Coarse-Grained Complexity for Dynamic Algorithms by Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
- Combinatorial Generation via Permutation Languages by Elizabeth Hartung, Hung P. Hoang, Torsten Mütze, Aaron Williams
- On the Power of Relaxed Local Decoding Algorithms by Tom Gur, Oded Lachish
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity by Alessandro Chiesa, Tom Gur, Igor Shinkar
- Sublinear time approximation of the cost of a metric k-nearest neighbor graph by Artur Czumaj, Christian Sohler
We are delighted to report that Dr Tom Gur has been awarded a Future Leaders Fellowship on Foundations of classical and quantum verifiable computing, funded by £892K from UK Research and Innovation. Professor Artur Czumaj, the head of the department's Theory and Foundations research theme, has commented:
We congratulate Tom and look forward to hosting this exciting project that he will lead. This prestigious award confirms the high international standing of research at Warwick in theoretical computer science and its rich interfaces with other fields.
The Department of Computer Science and the Department of Mathematics invite applications for a Professor in the core areas of the Theory and Foundations research group of the Department of Computer Science and of the Warwick Centre for Discrete Mathematics and its Applications (DIMAP): Discrete Mathematics, Algorithms and Complexity, Theoretical Computer Science, or in relevant areas on the interface of Computer Science and Mathematics.
The University of Warwick is one of the top research universities in the United Kingdom, renowned for its excellence in Mathematics and Theoretical Computer Science, home of the Centre for Discrete Mathematics and its Applications (DIMAP). The Departments of Computer Science and of Mathematics, and DIMAP are committed to research excellence and we seek candidates with an internationally leading research profile who will provide academic leadership.
Closing date: September 1, 2019.
The official announcement (including full details of the selection criteria for this role and instructions of how to apply) can be found at https://www.jobs.ac.uk/job/BUB374/professor-72048-079.
The 4th AlgoUK workshop will take place in Warwick Sept 17 - 18, 2019.
AlgoUK is a series of UK-wide workshops, combining a UK Theory Day with a one day workshop focusing on some applications of algorithms and complexity or applied area relevant to algorithms and complexity.
Every network workshop is open to every algorithms and complexity researcher in the UK and the network itself is intended to support the whole community. There are limited funds available to assist with attendance at AlgoUK’s workshops.
The Warwick AlgoUK workshop's web page is available at https://algouk.wixsite.com/warwick2019.
The Department is welcoming our new Assistant Professor Dr. Torsten Mütze, who will be associated with the Division of Theory and Foundations (FoCS) and the Centre for Discrete Mathematics and its Applications (DIMAP).
Before joining Warwick, Torsten held postdoctoral researcher positions at TU Berlin, Georgia Institute of Technology, and ETH Zürich. He obtained his PhD in Computer Science from ETH Zürich in 2011, under the guidance of Angelika Steger.
The Department of Computer Science has multiple Assistant Professor, Associate Professor or Reader vacancies in Computer Science, with the closing date on June 17, 2019.
The call is open to candidates working in all areas of Computer Science including those related to Theory and the FoCS group (and also DIMAP) research focus. If you are interested in joining one of the best Theory groups in Europe you're welcome to apply!
- algorithmic aspects of game theory and economics,
- approximation algorithms,
- automata and formal languages,
- computational complexity,
- cryptography and quantum computing,
- discrete mathematics, combinatorics, and their applications,
- graph and network algorithms,
- logic and games,
- online and dynamic algorithms,
- parallel and distributed algorithms,
- parameterized complexity and structural graph theory,
- random structures and randomized algorithms,
- sublinear and streaming algorithms,
- string algorithms.
The group has strong ties with the Centre for Discrete Mathematics and its Applications (DIMAP), established in 2007 jointly with Warwick Mathematics Institute and Warwick Business School. Together with DIMAP, the group is one of the leading theory groups in Europe, with regular publications in top
international conferences and journals in theoretical computer science.
The Department of Computer Science at Warwick offers an excellent research environment. It was ranked 1st in the UK for scientific output and 2nd overall in the latest UK research assessment in Research Excellence Framework (REF) in 2014.
The university campus is located on the border of two counties, West Midlands and Warwickshire, is about one hour train ride from London, and 15 minutes from Birmingham International Airport.
The applicants interested in theoretical computer science are expected to have a strong background in discrete mathematics, algorithms, or related topics with undergraduate and/or Master's degrees in Computer Science, Mathematics, or related disciplines. The position(s) will be fully funded, and the successful applicant(s) will be receiving a stipend at rate in line with current Research Councils UK rates.
If you are interested in this opening, please apply online by 31 March 2019 following the guidelines on the following page. Please indicate clearly your interest in Theory and Foundations and mention one of the group members as a potential supervisor.
You are encouraged to informally contact group members you might want to work with prior to that.
Permanent members of the group:
- Sayan Bhattacharya
- Dmitry Chistikov
- Graham Cormode
- Artur Czumaj (group leader)
- Charilaos Efthymiou
- Matthias Englert
- Tom Gur
- Marcin Jurdzinski
- Dan Kral
- Ranko Lazic
- Mike Paterson
- Ramanujan Sridharan
- Alex Tiskin
Centre for Discrete Mathematics and its Applications: https://warwick.ac.uk/fac/cross_fac/dimap/