School of Computer Science

Jessie Kennedy (Edinburgh Napier): Visualization and Taxonomy (School Seminar)

Abstract:

This talk will consider the relationship between visualization and taxonomy from two perspectives. Firstly, how visualization can aid understanding the process of taxonomy, specifically biological taxonomy and the visualization challenges this poses. Secondly, the role of taxonomy in understanding and making sense of the growing field of visualization will be discussed and the challenges facing the visualization community in making this process more rigorous will be considered.

Speaker Bio:

Jessie joined Edinburgh Napier University in 1986 as a lecturer, was promoted to Senior Lecturer, Reader, and then Professor in 2000 Thereafter she held the post of Director of the Institute for Informatics and Digital Innovation from 2010-14 and is currently Dean of Research and Innovation for the University.

Jessie has published widely, with over 100 peer-reviewed publications and over £2 million in research funding from a range of bodies, including EPSRC, BBSRC, National Science Foundation, and KTP, and has had 13 PhD students complete. She has been programme chair, programme committee member and organiser of many international conferences, a reviewer and panel member for many national and international computer science funding bodies, and became a Member of EPSRC Peer Review College in 1996 and a Fellow of the British Computer Society.

Jessie has a long-standing record of contribution to inter-disciplinary research, working to further biological research through the application of novel computing technology.

Her research in the areas of user interfaces to databases and data visualisation in biology contributed to the establishment of the field of biological visualisation. She hosted the first biological visualisation workshop at the Royal Society of Edinburgh in 2008, was an invited speaker at a BBSRC workshop on Challenges in Biological Visualisation in 2010, was a founding member of the International Symposium in Biological Visualisation – being Programme Chair in 2011, General Chair in 2012 and 2013 – and steering committee member since 2014.

She has been keynote speaker at related international conferences and workshops, such as VIZBI, the International Visualisation conference and BioIT World, and is currently leading a BBSRC network on biological visualisation.

Her research in collaboration with taxonomists at the Royal Botanic Gardens, Edinburgh, produced a data model for representing differing taxonomic opinions in Linnaean classification. This work led to collaboration on a large USA-funded project with ecologists from six US universities and resulted in a data standard for the exchange biodiversity data that has been adopted by major global taxonomic and biodiversity organisations.

Event details

  • When: 7th November 2017 14:00 - 15:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

Barnaby Martin (Durham): The Complexity of Quantified Constraints (School Seminar)

Abstract:

We elaborate the complexity of the Quantified Constraint Satisfaction Problem, QCSP(A), where A is a finite idempotent algebra. Such a problem is either in NP or is co-NP-hard, and the borderline is given precisely according to whether A enjoys the polynomially-generated powers (PGP) property. This reduces the complexity classification problem for QCSPs to that of CSPs, modulo that co-NP-hard cases might have complexity rising up to Pspace-complete. Our result requires infinite languages, but in this realm represents the proof of a slightly weaker form of a conjecture for QCSP complexitymade by Hubie Chen in 2012. The result relies heavily on the algebraic dichotomy between PGP and exponentially-generated powers (EGP), proved by Dmitriy Zhuk in 2015, married carefully to previous work of Chen.

Event details

  • When: 24th October 2017 14:00 - 15:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

Maja Popović (Humboldt-Universität zu Berlin): (Dis)similarity Metrics for Texts (School Seminar)

Abstract:
Natural language processing (NLP) is a multidisciplinary field closely related to linguistics, machine learning and artificial intelligence. It comprises a number of different subfields dealing with different kinds of analysis and/or generation of natural language texts. All these methods and approaches need some kind of evaluation, i.e. comparison between the obtained result with a given gold standard. For tasks dealing with text generation (such as speech recognition or machine translation), a comparison between two texts has to be carried out. This is usually done either by counting matched words or word sequences (which produces a similarity score) or by calculating edit distance, i.e. a number of operations needed to transform the generated word sequence into a desired word sequence (which produces a “dissimilarity” score called “error rate”). The talk will give an overview of advantages, disadvantages and challenges related to this type of metrics mainly concentrating on machine translation (MT) but also relating to some other NLP tasks.

Speaker bio:
Maja Popović graduated at the Faculty of Electrical Engineering, University of Belgrade and continued her studies at the RWTH Aachen, Germany, where she obtained her PhD with the thesis “Machine Translation: Statistical Approach with Additional Linguistic Knowledge”. After that, she continued her research at the DFKI Institute and thereafter at the Humboldt University of Berlin, mainly related to various approaches for evaluation of machine translation. She has developed two open source evaluation tools, (i) Hjerson, a tool for automatic translation error classification, and (ii) chrF, an automatic metric for machine translation evaluation based on character sequence matching.

Event details

  • When: 29th September 2017 13:00 - 14:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

Ott: Effective Tool Support for the Working Semanticist

ACM SIGPLAN has judged Ott: Effective Tool Support for the Working Semanticist, by Peter Sewell, Francesco Zappa Nardelli, Scott Owens, Gilles Peskine, Thomas Ridge, Susmit Sarkar, and Rok Strniša, to be the recipient of the Most Influential ICFP Paper Award for 2017. From the citation:

“Over the past ten years, ICFP researchers have benefitted tremendously from the open-source tool and the effective design space exploration that it promotes.”

n-Queens Completion is NP-Complete

Update, 2021

Over the years since we published this research, many people have approached us having solved the n queens puzzle, either for one n like 8 or 1000, or having written an algorithm to solve it for different sizes.  Unfortunately this is not a major result in Computer Science and does not make one eligible to claim the $1M Clay prize. Many have been disappointed by this so we want to clarify why  this is the case. 

It is true that work on this problem could potentially result in the award but only if some exceptionally difficult conditions are met.

  • EITHER prove mathematically that NO possible algorithm could solve the n queens completion problem in polynomial time;
  • OR prove that there is an algorithm which is guaranteed to solve every instance of the n queens completion problem in polynomial time. Note that in this case the algorithm has to work on the completion version of the problem studied in our paper, not placing queens on an empty board; the algorithm has to give the correct answer on every possible instance given to it; and there has to be a mathematical proof that the algorithm’s runtime is bounded above by some polynomial in the size of the board.  However fast a given algorithm runs when tested, this is not sufficient because there are an infinite number of possible tests available, so a mathematical proof is required.
  • AND in either case, prove this at a level that is published in a respected academic source and is widely accepted by research experts as correct.

We are delighted that our work has led so many people to be interested in the problem of solving problems like the n queens puzzle that fascinates us.  But we also apologise for any impression we gave, unintentionally, that a solution to the n queens puzzle could lead to the award of the prize except under the extremely strenuous conditions listed above.

Ian Gent, 10 May 2021

Original Post from 2017:

Ian Gent, Christopher Jefferson and Peter Nightingale have shown that a classic chess puzzle is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30, 2017.

The n-Queens puzzle is a classic chess problem: given a chessboard of size n by n, can you place n queens so that no two queens attack each other?  That is, can you place the queens with no two queens are on the same row, column, or diagonal? The n-Queens puzzle has long been known to be simple to solve:  you can solve the problem for all n except 2 and 3, and solutions for all other n can be described in a few lines.  This very simplicity has led to repeated

Peter Nightingale and Ian Gent at Falkland Palace, Wednesday, 17 August 2017.
©Stuart Nicol Photography, 2017

controversy in Artificial Intelligence (AI). The n-Queens puzzle is often used as a benchmark problem, but good results on the problem can always be challenged because the problem is so simple to solve without using AI methods.

The new work follows a challenge on Facebook on New Year’s Day, 2015, when a friend of Ian’s asked him how hard n-Queens is if some queens were already placed on the board.  It turns out, this version (dating from 1850) of the puzzle is only two years younger than the more famous n-Queens problem. The picture shows Peter (left) and Ian (right) with queens on the board at positions suggested by Nauck in 1850, the squares b4 and d5.  Can you put another 6 queens on the board so that the entire board is a solution of 8-Queens?  The general version with some number of queens preplaced on an n by n board is the n-Queens Completion puzzle.

 

With queens at b4 and d5, can you place 6 more queens to get a solution to the 8-queens puzzle? ©Stuart Nicol Photography, 2017

Ian, Christopher and Peter have shown that the n-Queens puzzle is in fact hard, not simple.  It belongs to the complexity classes NP-Complete and #P-Complete. Other NP-Complete problems include the “travelling salesperson problem”, finding cliques in graphs, and many other important problems, from scheduling to circuit layout. This puts n-Queens Completion at the centre of the most important theoretical problem in computer science — it has long been known that either all NP-complete problems are easy, or none of them are. Most computer scientists believe that this means there is no efficient algorithm possible for solving this problem, compared to the very simple techniques long known for n-Queens.
The importance of this work is that it provides researchers with a benchmark that can be used for evaluating AI techniques. Moreover, it helps to explain why so many AI techniques have been used on the n-Queens puzzle. Most techniques do most of their work with some queens partially placed, using some form of (hopefully intelligent) trial and error. In fact it turns out that many researchers – in order to solve a simple problem – have solved it by turning the simple problem of n-Queens into the hard problem of n-Queens Completion.
It does seem that AI researchers should not use n-Queens as a benchmark, but the very closely related n-Queens Completion puzzle is a valid benchmark. As well as the theoretical results, the paper shows how example instances can be generated which appear to be hard in practice. Some caution is still needed, though. It does seem to be quite hard to generate hard instances of n-Queens Completion.
The University has also issued an article on the same paper, under the title “Simple” chess puzzle holds key to $1m prize

MSc Poster Demo Session 2017

After a year of hard work, and an intensive summer dissertation, our MSc students submitted their dissertations last week and presented their project posters and artefacts.

The eventful poster demonstration session provides a great opportunity for students to meet with second markers, reflect upon their MSc experience and appreciate the diverse projects completed by their peers. This year, students organised a School sponsored CS Ball, to celebrate their achievement.

We wish them all, every success with future plans, and look forward to seeing them again at December Graduation.

Images courtesy of Saleem Bhatti and Xu Zhu.

Postgraduate Dinner at Fairmont Hotel

Postgraduate student, Paul Dobra organised an end of semester celebratory dinner at the Fairmont Hotel in April. The social event marked the end of teaching and provided a chance to relax before the commencement of dissertation. Paul supplied comments and shared some photos from the occasion.

“There are rather few occasions not to be happy when you are surrounded by friends and family. Even better so when your friends are like your family, and in true computer science spirit the end of the second semester finished in a grand style: enjoying the scenic view of the North Sea from the balcony of the Fairmont Hotel and Restaurant, approximately 60 postgraduates celebrated their friendship and the successful completion of deadlines. Consisting of a lavish three-course meal and blessed with amazing weather, the event was a reminder of the true, everlasting bonds that can be forged outside university.”

Images and text courtesy of Paul Dobra

Monads and Lenses – Dr James Cheney

Talk Title:  Monads and Lenses

Abstract:

Monads are an abstraction that can be used to mathematically model computational effects (among other things).  Lenses are an abstraction for bidirectional computation, a generalization of the view-update problem.  In this talk I will discuss ways to combine them and why it might be interesting to do so.

 

This talk is on joint work with Faris Abou-Saleh, Jeremy Gibbons, James McKinna and Perdita Stevens conducted as part of the recently-concluded project “A theory of least change for bidirectional transformations”.

Event details

  • When: 17th July 2017 13:00 - 14:00
  • Where: Cole 1.33a
  • Format: Colloquium, Seminar