Design Frontiers in Parallel Languages: The Role of Determinism

Constraints can be a source of inspiration; their role in creative art forms is well-recognized, with poetry as the quintessential example.  We argue that the requirement of determinism can play the same role in the design of parallel programming languages. This talk describes a series of design explorations that begin with determinism as the constraint, introduce the concept of monotonically-changing concurrent data structures (LVars), and end in some interesting places—flirting with the boundaries to yield quasideterminism, and revealing synergies between parallel effects, such as cancelation and memoization, when used in a deterministic context.

Our goal is for guaranteed-deterministic parallel programming to be practical and efficient for a wide range of applications. One challenge is simply to integrate the known forms of deterministic-by-construction parallelism, which we overview in this talk: Kahn process networks, pure data-parallelism, single assignment languages, functional programming, and type-effect systems that enforce limited access to state by threads. My group, together with many others around the world, are developing libraries such as LVish and Accelerate that add these capabilities to the programming language Haskell. It is early days yet, but already possible to build programs that mix concurrent, lock-free data structures, blocking data-flow, callbacks, and GPU-based data-parallelism, without ever compromising determinism or referential transparency.

Event details

  • When: 12th June 2014 14:00 - 15:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

Computational Social Choice: an Overview by Edith Elkind, University of Oxford

ABSTRACT
In this talk, we will provide a self-contained introduction to the field of computational social choice – an emerging research area that applies tools and techniques of computer science (most notably, algorithms, complexity and artificial intelligence) to problems that arise in voting theory, fair division, and other subfields of social choice theory. We will give a high-level overview of this research area, and mention some open problems that may be of interest to mathematicians and computer scientists.

Event details

  • When: 15th April 2014 - 15:00
  • Where: Maths Theatre B
  • Series: School Seminar Series
  • Format: Seminar

Doing Research in the Wild – Paul Marshall, UCL

Abstract: There has been
significant growth in interest in ‘research in the wild’ as an approach to
developing and understanding novel technologies in real world contexts.
However, the concept remains underdeveloped and it is unclear how it differs
from previous technology deployments and in situ studies. In this talk, I will
attempt an initial characterisation of research in the wild. I will discuss
some of the benefits of studying novel technologies in situ as well as some of
the challenges inherent in encouraging and studying sustained use.

Bio: Paul Marshall is a lecturer in interaction design in the UCL
Interaction Centre. His research interests focus on understanding how
ubiquitous computing technologies are used in everyday contexts such as the
home, in education or in public spaces. Prior to joining UCL he worked as a
post doc at the University of Warwick (2010-11) researching participatory
design approaches in healthcare and at the Open University (2006-10) where he
ran ethnographic and laboratory studies of shareable interfaces and sensory
extension devices. He completed a PhD project on learning with tangible
interfaces as part of the Equator project at the University of Sussex, and
prior to that a BSc (Hons) in psychology at the University of Edinburgh.

Event details

  • When: 1st April 2014 14:00 - 15:00
  • Where: Maths Theatre B
  • Series: School Seminar Series

Cigna: Technology enabling Health & Well being provision across the Globe

Cigna – a global health services company is dedicated to helping those we serve to improve their health and well being. Cigna provides globally connected healthcare services with access to a global network of clinical providers through leveraging the use of pioneering and innovative technology. Find out how you can get engaged and join the team driving innovation in Healthcare!

Maths Lecture Theatre B
Time: 14:00 to 15:00
Date: Tuesday 4th March

Event details

  • When: 4th March 2014 14:00 - 15:00
  • Where: Maths Theatre B
  • Series: School Seminar Series
  • Format: Seminar

Cybersecurity for Critical Infrastructure

Cybersecurity for Critical Infrastructure, or ‘how to break into a nuclear power station for fun & profit’

Dr Richard Gold, Cisco Systems, UK

Cyber Security for Critical Infrastructures such as the power grid, oil & gas pipelines and dams has become a hot topic since the Stuxnet malware attack against the nuclear enrichment centrifuges in Iran. However, due to intrinsic issues with the field of Critical Infrastructure (a.k.a., ICS or SCADA), it is difficult to deploy standard IT security solutions “as is” to these systems. In this talk I discuss the problems associated with deploying effective security processes in Critical Infrastructures, the various types of security holes which these system contain and a step-by-step approach to exploiting a Critical Infrastructure installation. Thinking from the attacker’s perspective allows us to get an insight into how these systems are vulnerable and how a potential attacker might exploit them.

Event details

  • When: 18th February 2014 14:00 - 15:00
  • Where: Maths Theatre B
  • Series: School Seminar Series
  • Format: Seminar

Evaluation of Network Resilience and Survivability: Analysis, Simulation, Tools, and Experimentation by James P. G. Sterbenz, ITTC, University of Kansas

As the Internet becomes increasingly important to all aspects of society, the consequences of disruption are increasingly severe. Thus it is critical to increase the resilience and survivability of the future networks in general, and the Internet in particular. We define resilience as the ability of the network to provide desired service even when the network is challenged by attacks, large-scale disasters, and other failures. Resilience subsumes the disciplines of survivability, fault-tolerance, disruption-tolerance, traffic-tolerance, dependability, performability, and security. After an introduction to the disciplines and challenges to network resilience, this presentation will discuss analytical, simulation, and experimental emulation techniques for understanding, evaluating, and improving the resilience of the Future Internet. This includes a multilevel state-space based approach that plots network service delivery against operational state that is the basis for both mathematical- and simulation-based analysis, and graph-theoretic complex-system approaches that embed fundamental properties such as redundancy and diversity into all aspects of network structure, mechanism, and protocols. A set of tools to help in this analysis has been developed: KU-LoCGen (Location and Cost-Constrained Topology Generation), KU-TopView (Topology Viewer), and KU-CSM (Challenge Simulation Module). Plans to experimentally evaluate resilience include using the international programmable testbed GpENI: Great Plains Environment for Network Innovation. A new composable, cross-layered resilient transport protocol (ResTP) and geodiverse multipath routing protocol (GeoDivRP) are being developed.

Event details

  • When: 28th January 2014 14:00 - 15:00
  • Where: Maths Theatre B
  • Series: School Seminar Series
  • Format: Seminar

Evolution of our existing institutional research information infrastructure : a facilitator for Open Science?

Anna Clements, Head of Research Data and Information Services, University of St Andrews.

Open Science’ seems to be one of the hottest topics around with organisations and funders from the G8 downwards stressing the importance of open data in driving everything from global innovation through to more accountable governance; not to mention the more direct possibility that non-compliance could result in research grant income drying up.
Here at St Andrews we have had an institutional research information system (CRIS) since 2006 which has evolved in tandem with the rapidly changing research policies and slower cultural shifts towards more and more open access to research outputs, outcomes and impact. But, we now face, perhaps, the biggest challenge so far in determining the extent to which Institutional infrastructure and services can support this transition to an ‘open by default’ culture. I will argue that this challenge cannot be met without researchers engaging with the debate and driving the agenda forward with the support services here at St Andrews – there is a joint responsibility very clearly articulated in the EPSRC policy framework on research data. So there will be some suggestions on what we could do by building on our existing infrastructure, including examples of best practice from elsewhere, but also an invitation to the audience for suggestions on how to respond to this incessant and increasing clamour for access to research outputs and, in particular, research data.

Event details

  • When: 19th November 2013 14:00 - 15:00
  • Where: Purdie Theatre C
  • Series: School Seminar Series

Intellectual Property – What, why, and how?

Dr Alan Boyd and Dr Nicholas Malden, D Young & Co LLP (Patent Attorneys)
Intellectual Property – What, why, and how?
In many technological fields, especially computer science, output isn’t a physical object that can be sold, but is an idea or an expression of an idea that comes from your mind. But how can industry take advantage of such ideas or expressions, and what’s to stop a competitor from simply copying your hard work and benefiting from it at your expense? In this talk, we’ll take you through the basics of Intellectual Property (IP) and look at how it can be used by a computer scientist, its importance to new start-ups and large multinationals alike, and also introduce you to the patent attorney profession. We’ll give you a chance to try your hand at writing a patent claim, and we’ll give a prize to the best one!

Event details

  • When: 5th November 2013 14:00 - 15:00
  • Where: Purdie Theatre C
  • Series: School Seminar Series
  • Format: Seminar

The Interaction of Representation and Reasoning by Professor Alan Bundy, University of Edinburgh

These lectures will take place in Lower College Hall, North Street. The lectures will discuss the close relationship between how knowledge and problems may be represented and how people and computers use these representations to guide their reasoning about the problems.

Prof Steve Linton, Prof Alan Bundy and Prof Ian Sommerville

Prof Steve Linton, Prof Alan Bundy and Prof Ian Sommerville
Distinguished lectures, 27th November 2013

10.00 1. Title: The Interaction of Representation and Reasoning

Abstract: Successful reasoning is dependent on appropriate representation of both knowledge and of successful methods of reasoning. A change of representation can change an intractable problem into an easy one. Failures of reasoning can suggest changes of representation. Reasoning failures can, for instance, take the form of proofs of false conjectures, failures to prove true conjectures or inefficient inference. I will illustrate these interactions by drawing on work in my research group.

11.30 2. Title: Theory Evolution in Physics

Abstract: We investigate the problem of automatically repairing a faulty Physics theory when it conflicts with experimental evidence. We introduce novel strategies for fault diagnosis and for representation repair. Diagnosis and repair are composed into general-purpose repair plans. We will illustrate this with two such plans, where theory and experiment conflict over (a) the value and (b) the dependence of a function, respectively. We represent both physical concepts and the repair plans using higher-order logic. This is because many physical concepts are most naturally represented as higher-order functions and because polymorphic higher-order functions are required to enable the repair plans to be applied to diverse situations.

14.00 3. Title: Reformation: A Domain-Independent Algorithm for Theory Repair

Abstract: We describe and invite discussion on work in progress on reformation, a new algorithm for the automated repair of faulty logical theories. A fault is revealed by a reasoning failure: either the proof of a false theorem or the failure to prove a true conjecture. Repair suggestions are systematically extracted via analysis of the attempted unification of two formulae. These suggestions will either block an unwanted but successful unification or unblock a wanted but failed unification attempt. In contrast to traditional belief revision and abduction mechanisms, the repairs are to the language of the theory as well as to the deletion or addition of axioms.

Professor Alan Bundy

Professor Alan Bundy is Professor of Automated Reasoning in the School of Informatics at the University of Edinburgh. Professor Bundy is a world-leader in the area of artificial intelligence called Mathematical Reasoning and has held more than 50 research grants in this area since the 1970s , has published more than 200 research papers and has been awarded the 2007 IJCAI Award for Research Excellence and Herbrand Award for Distinguished Contributions to Automated Deduction. He is a Fellow of the Royal Society, A Fellow of the Royal Society of Edinburgh, a Fellow of the Royal Academy of Engineers and, in 2012, was awarded a CBE for services to computing science. As well as his research work, Professor Bundy has played an active role in the British Computer Society and has been instrumental in supporting changes to the computer science curriculum in schools.

Slides:

Event details

  • When: 27th November 2013 10:00 - 16:00
  • Where: Lower College Hall
  • Series: Distinguished Lectures Series

Some Limits of Language: A Perspective from Formal Grammars and Languages by Prof Arvind Joshi, School of Engineering and Applied Science, University of Pennsylvania, USA

Limits of language can be studied from various perspectives such as morphology, syntax, and semantics, among others. At the syntactic level, one direction that has been pursued very actively is via the theory of formal languages, beginning with the so-called Chomsky hierarchy. In this hierarchy, the finite state languages (regular languages) and the context free languages (CFL) have been studied very extensively, leading to many important results relevant to syntax as well as parsing. At the same time, inadequacy of these two classes of grammars (languages) for capturing natural languages has been well documented by now.
A careful look at the pumping lemma for context free languages led to the discovery of the so-called tree adjoining grammars (TAG) and to the notion of mildly context sensitive languages (MCSL), which has served as a framework for showing equivalences among other systems (such as Combinatory Categorial Grammars, CCG and Head Grammars (HG), for example). This has led to a deeper understanding of the limits of language, more specifically, by trying to provide an answer to the question: how far do we need to be beyond CFL to achieve syntactic adequacy.
I will try to describe some of this recent work by a number of researchers in the past few years.

Aravind Joshi did his undergraduate work in India and his graduate work at the University of Pennsylvania in Electrical Engineering, while simultaneously attending some courses in Linguistics at the same University. Since 1961 he has been a faculty member in the Department of Computer and Information Science and the Department of Linguistics. At present, he is a Professor of Computer and Cognitive Science and a Member of the Institute for Research in Cognitive Science.
Besides working on some problems in the mathematics of language, at present, he is involved in a project on discourse annotation, jointly with Bonnie Webber (Edinburgh U.) and Rashmi Prasad (U. Wisconsin), for creating the Penn Discourse Treebank (PDTB).

Event details

  • When: 15th October 2013 14:00 - 15:00
  • Where: Purdie Theatre C
  • Series: School Seminar Series
  • Format: Seminar