Announcement of the 33rd British Colloquium for Theoretical Computer Science

The 33rd BCTCS will be hosted by the School of Computer Science, University of St Andrews, from the 26th to the 28th of April 2017. The purpose of BCTCS is to provide a forum in which researchers in theoretical computer science can meet, present research findings, and discuss developments in the field. It also aims to provide an environment in which PhD students can gain experience in presenting their work, and benefit from contact with established researchers.

The scope of the colloquium includes all aspects of theoretical computer science, including algorithms, complexity, cryptography, formal methods, game theory, machine learning, languages, logics and quantum computation. Both computer scientists and mathematicians are welcome to attend, as are participants from outside of the UK.

This year the colloquium will feature the following invited speakers

LMS Keynote Lecture in Discrete Mathematics

Professor László Babai, University of Chicago

Confirmed Speakers
Perdita Stevens, University of Edinburgh
Conor McBride, University of Strathclyde
Felix Fischer, University of Glasgow
Edwin Brady, University of St Andrews
Mehrnoosh Sadrzadeh, Queen Mary University of London

Registration is *now open*, and you can find more information at https://bctcs2017.cs.st-andrews.ac.uk/

PhD students are especially encouraged to offer a talk.

As an additional event, there will be a Scottish Combinatorics Meeting at the School of Mathematics in St Andrews on the 24th and 25th of April. If you would like to take part in the meeting, please contact the organisers directly.

The organisers hope to welcome you to St Andrews in April.

Type-Driven Development of Communicating Systems using Idris

Speaker: Jan de Muijnck-Hughes

Abstract

Communicating protocols are a cornerstone of modern system design.
However, there is a disconnect between the different tooling used to design, implement and reason about these protocols and their implementations.
Session Types are a typing discipline that help resolve this difference by allowing protocol specifications to be used during type-checking to ensure that implementations adhere to a given specification.

Idris is a general purpose programming language that supports full-dependent types, providing programmers with the ability to reason more precisely about programs.
This talk introduces =Sessions=, our implementation of Session Types in Idris, and demonstrates =Sessions= ability to design and realise several common protocols.

=Sessions= improves upon existing Session Type implementations by introducing value dependencies between messages and fine-grained channel management during protocol design and implementation.
We also use Idris’ support for EDSL construction to allow for protocols to be designed and reasoned about in the same language as their implementation.
Thereby allowing for an intrinsic bond to be introduced between a protocol’s implementation and specification, and also with its verification.

Using =Sessions=, we can reduce the existing disconnect between the tooling used for protocol design, implementation, and verification.

 

 

 

Event details

  • When: 23rd February 2017 13:00 - 15:00
  • Where: Cole 1.33b
  • Format: Colloquium, Seminar, Talk

SACHI Seminar – The Collaborative Design of Tangible Interactions in Museums

Title: The Collaborative Design of Tangible Interactions in Museums

Abstract: Interactive technology for cultural heritage has long been a subject of study for Human-Computer Interaction. Findings from a number of studies suggest that, however, technology can sometime distance visitors from heritage holdings rather than enabling people to establish deeper connections to what they see. Furthermore, the introduction of innovative interactive installations in museum is often seen as an interesting novelty but seldom leads to substantive change in how a museum approaches visitor engagement. This talk will discuss work on the EU project “meSch” (Material EncounterS with Digital Cultural Heritage) aimed at creating a do-it-yourself platform for cultural heritage professionals to design interactive tangible computing installations that bridge the gap between digital content and the materiality of museum objects and exhibits. The project has adopted a collaborative design approach throughout, involving cultural heritage professionals, designers, developers and social scientist. The talk will feature key examples of how collaboration unfolded and relevant lessons learned, particularly regarding the shared envisioning of tangible interaction concepts at a variety of heritage sites including archaeology and art museums, hands-on exploration centres and outdoor historical sites.

Biography: Dr. Luigina Ciolfi is Reader in Communication at Sheffield Hallam University. She holds a Laurea (Univ. of Siena, Italy) and a PhD (Univ. of Limerick, Ireland) in Human-Computer Interaction. Her research focuses on understanding and designing for human situated practices mediated by technology in both work and leisure settings, particularly focusing on participation and collaboration in design. She has worked on numerous international research projects on heritage technologies, nomadic work and interaction in public spaces. She is the author of over 80 peer-reviewed publications, has been an invited speaker in ten countries, and has advised on research policy around digital technologies and cultural heritage for several European countries. Dr. Ciolfi serves in a number of scientific committees for international conferences and journals, including ACM CHI, ACM CSCW, ACM GROUP, ECSCW, COOP and the CSCW Journal. She is a member of the EUSSET (The European Society for Socially Embedded Technologies) and of the ACM CSCW Steering Groups. Dr. Ciolfi is a senior member of the ACM. Full information on her work can be found at http://luiginaciolfi.com

Event details

  • When: 31st January 2017 14:00 - 15:00
  • Where: Cole 1.33a
  • Format: Seminar

Seminar: Jacob Howe on Propagation and Reification

Jacob Howe, Senior Lecturer at City University London, and sabbatical visitor, will be giving a seminar to the AI Research Group at 2pm on Thursday 15th December in JC 1.33a.

The title and abstract are:

Propagation and Reification: SAT and SMT in Prolog

This talk will describe how a watched literal DPLL based Satisfiability (SAT)
solver can be succinctly coded in 20 lines of Prolog. The extension of
this solver to an Satisfiability Modulo Theories (SMT) solver will be discussed with a particular focus on
the case where the theory is that of rational-tree constraints, and its
application in a reverse engineering problem.

Event details

  • When: 15th December 2016 14:00 - 15:00
  • Where: Cole 1.33a
  • Format: Seminar

Talk: Using cost models of algorithmic skeletons

Abstract:

 The increasing importance of parallelism has motivated the creation of better abstractions for writing parallel software, including structured parallelism using nested algorithmic skeletons. Such approaches provide high-level abstractions that avoid common problems, such as race conditions, and often allow strong cost models to be defined. However, choosing a combination of algorithmic skeletons that yields good parallel speedups for a program on some specific parallel architecture remains a difficult task. In order to achieve this, it is necessary to simultaneously reason both about the costs of different parallel structures and about the semantic equivalences between them. This paper presents a new type-based mechanism that enables strong static reasoning about these properties. We exploit well-known properties of a very general recursion pattern, hylomorphisms, and give a denotational semantics for structured parallel processes in terms of these hylomorphisms. Using our approach, it is possible to determine formally whether it is possible to introduce a desired parallel structure into a program without altering its functional behaviour, and also to choose a version of that parallel structure that minimises some given cost model.

Event details

  • When: 13th December 2016 16:00 - 17:00
  • Where: Honey 103 - GFB
  • Format: Talk

Seminar: Alice Toniolo on Computational Argumentation

Alice Toniolo, a new lecturer in Computer Science at St Andrews, will be giving a seminar to the Artificial Intelligence Research Group on Thursday 1st December 2016, 2pm, in JC 1.33a. All are welcome.

Computational argumentation: an overview of current reasoning and dialogue models and their applications

Abstract: Argumentation is the process of arriving at a decision for a controversial standpoint. Computational models of argumentation aim to imitate the human decision-making process by modelling reason for or against certain decisions and extract justifiable options. This talk will draw from philosophical studies to present the core concepts of argumentation theory in AI through a range of abstract, logical and dialogical models. I will focus on the potential of argumentation-based models employed by software agents to support reasoning and dialogue in the presence of incomplete, inconsistent and uncertain information. An application of argumentation-based reasoning is presented in the context of intelligence analysis. The agent-based tool discussed, called CISpaces (Collaborative Intelligence Spaces), employs argumentation to help analysts make sense of information in collaboration and provenance to establish the credibility of hypotheses.

Event details

  • When: 1st December 2016 14:00 - 15:00
  • Where: Cole 1.33a
  • Format: Seminar

SACHI Seminar: Roderick Murray-Smith, University of Glasgow

rod-head

Title: Control Theoretical Models of Pointing

Speaker: Rod Murray-Smith, University of Glasgow
http://www.dcs.gla.ac.uk/~rod/

Abstract: I will talk about two topics:

1. (Joint work with Jörg Müller & Antti Oulasvirta) I will present an empirical comparison of four models from manual control theory on their ability to model targetting behaviour by human users using a mouse: McRuer’s Crossover, Costello’s Surge, second-order lag (2OL), and the Bang-bang model. Such dynamic models are generative, estimating not only movement time, but also pointer position, velocity, and acceleration on a moment-to-moment basis. We describe an experimental framework for acquiring pointing actions and automatically fitting the parameters of mathematical models to the empirical data. We present the use of time-series, phase space and Hooke plot visualisations of the experimental data, to gain insight into human pointing dynamics. We find that the identified control models can generate a range of dynamic behaviours that captures aspects of human pointing behaviour to varying degrees. Conditions with a low index of difficulty (ID) showed poorer fit because their unconstrained nature leads naturally to more dynamic variability. We report on characteristics of human surge behaviour in pointing. We describe trade-offs among the models. We conclude that control theory offers a promising complement to Fitts’ law based approaches in HCI, with models providing representations and predictions of human pointing dynamics which can improve our understanding of pointing and inform design.

2. Casual control. How and why we can design systems to work at a range of levels of engagement.

Biography: Roderick Murray-Smith is a Professor of Computing Science at Glasgow University, in the “Inference, Dynamics and Interaction” research group and the Head of the Information, Data and Analysis Section. He works in the overlap between machine learning, interaction design and control theory. In recent years his research has included multimodal sensor-based interaction with mobile devices, mobile spatial interaction, Brain-Computer interaction and nonparametric machine learning. Prior to this he held positions at the Hamilton Institute, NUIM, Technical University of Denmark, M.I.T., and Daimler-Benz Research, Berlin, and was the Director of SICSA, the Scottish Informatics and Computing Science Alliance. He works closely with the mobile phone industry, having worked together with Nokia, Samsung, FT/Orange, Microsoft and Bang & Olufsen. He was a member of Nokia’s Scientific Advisory Board and is a member of the Scientific Advisory Board for the Finnish Centre of Excellence in Computational Inference Research. He has co-authored three edited volumes, 22 journal papers, 16 book chapters, and 88 conference papers.

Event details

  • When: 18th November 2016 13:00 - 14:00
  • Where: Cole 1.33b
  • Format: Seminar

DLS: Distributed Systems and Sensing by Prof. Julie McCann

DISTINGUISHED LECTURE SERIES

Semester 1

TITLE:

Distributed Systems and Sensing

by

Julie McCann

jm

7th November 2016

Lower and Upper College Halls

 

Introduction

By Professor Simon Dobson

School of Computer Science

University of St Andrews

The first of this academic year’s distinguished lectures will be given by Professor Julie McCann, Imperial College, London on Monday 7th November 2016 at Lower and Upper College Halls.

 

Overview

Chirping, self-organising, adaptive and intelligent tiny computers are beginning to enter both the market and people’s homes, performing various monitoring and control duties. From Google’s self-drive cars to the walls of modern office blocks, these simple devices are talking to each other in highly intelligent ways, mimicking the collective behaviour of insect colonies, for example, to overcome individual failures or changes in the local environment.

 

 

 Biography

Prof Julie A. McCann is a Professor of Computer Systems in Imperial College London (IC), where she leads the Adaptive Embedded Systems Engineering Research Group, she is Director for the Imperial wide Centre for Smart Connected Futures, Co-Director of the Intel Collaborative Research Institute for Sustainable Cities and she is CI for the NEC Smart Water Systems Lab and many other substantive projects with industry and academia with a focus on networking and sensing infrastructures to support environments such as smart cities, water and gas networks etc. She is CI on the EPSRC energy/water/food nexus WefWebs project where her focus is on precision farming and wine making.

Likewise, her NERC FUSE project designed and deployed a now patented sensing infrastructure for floodplain monitoring in Oxfordshire. Her research centres on highly decentralized and self-organizing scalable embedded frugal computing systems where one avoids a single point of failure to produce truly scalable solutions. She is a Fellow of the British Computer Society and is the Associate Editor for ACM Transactions on Adaptive Autonomic Systems (TAAS), has been General and Technical chair for the IEEE International Conference on Self-Adaptive and Self-Organising systems (SASO) and IEEE SECON 2016, SMARTCOMP 2017 and has been on the programme committee for IEEE INFOCOM, ACM UBICOMP and many more. Julie has presented her work in A* conferences and keynoted at the Indian Science Conclave Congregation of Nobel Prize Winners, for the encouragement of disadvantaged kids into science and computing in 2008.

 

 

 

Programme:   Monday 7th November 2016

 
     
 

09:15 – 09:30

 

Introduction:

 
  By Professor Simon Dobson  
 

09:30 – 10:30

 

Lecture 1:

 
  Professor Julie McCann will initially talk through how Wireless Sensor Networks are being used today and what other sciences will impact this subject leading to the ability to have Programmable Matter.  
 

10:30 – 11:00

 

Coffee Break

 
    Refreshments served
 

11:00 – 12:00

 

Lecture 2:

 
  In her second talk she will come very much down to earth and discuss how such systems are programmed today in terms of the hardware stack that composes them and the protocols that allow them to collaborate.  
 

12:00 – 14:00

 

Lunch Break

 
  Free time  
 

14:00 – 15:00

 

Lecture 3:

 
  Prof McCann will introduce some of the challenges that still remain, such as scaling this technology to larger dimensions but to also make them more resilient as well as secure etc. and the challenges that control adds to the system.  
 

15:00 – 15:30

 

 

Q & A Session:

 

 
  Open forum

 

 
   

 

 

Event details

  • When: 7th November 2016 09:15 - 16:00
  • Where: Lower College Hall
  • Series: Distinguished Lectures Series
  • Format: Distinguished lecture

SACHI Seminar – Dr Rebecca Fiebrink: Goldsmiths University of London

rebeccafiebrink

Title: Designing Real-time Interactions Using Machine Learning

Abstract: Supervised learning algorithms can be understood not only as a set of techniques for building accurate models of data, but also as design tools that can enable rapid prototyping, iterative refinement, and embodied engagement— all activities that are crucial in the design of new musical instruments and other embodied interactions. Realising the creative potential of these algorithms requires a rethinking of the interfaces through which people provide data and build models, providing for tight interaction-feedback loops and efficient mechanisms for people to steer and explore algorithm behaviours.

In this talk, I will discuss my research on better enabling composers, musicians, and developers to employ supervised learning in the design of new real-time systems. I will show a live demo of tools that I have created for this purpose, centering around the Wekinator software toolkit for interactive machine learning. I’ll discuss some of the outcomes from 7 years of creating machine learning-based tools and observing people using these tools in creative contexts. These outcomes include a better understanding how machine learning can be used as a tool for design by end users and developers, and how using machine learning as a design tool differs from more conventional application contexts.

Biography: Dr. Rebecca Fiebrink is a Lecturer at Goldsmiths, University of London. Her research focuses on designing new ways for humans to interact with computers in creative practice, including on the use of machine learning as a creative tool. Fiebrink is the developer of the Wekinator system for real-time interactive machine learning (with a new version just released in 2015!), a co-creator of the Digital Fauvel platform for interactive musicology, and a Co-I on the £1.6M Horizon 2020-funded RAPID-MIX project on Real-time Adaptive Prototyping for Industrial Design of Multimodal Expressive Technology. She is the creator of a MOOC titled “Machine Learning for Artists and Musicians,” which launched in 2016 on the Kadenze platform. She was previously an Assistant Professor at Princeton University, where she co-directed the Princeton Laptop Orchestra. She has worked with companies including Microsoft Research, Sun Microsystems Research Labs, Imagine Research, and Smule, where she helped to build the #1 iTunes app “I am T-Pain.” She holds a PhD in Computer Science from Princeton University.

Event details

  • When: 1st November 2016 14:00 - 15:00
  • Where: Cole 1.33b
  • Format: Seminar