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

Peter Nightingale and Ian Gent at Falkland Palace, Wednesday, 17 August 2017.
©Stuart Nicol Photography, 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.

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 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

First ever Computer Science Ball

We would like to cordially invite all staff, students, and alumni to this historic CS event in the making. As you know, other schools in St Andrews have their own annual ball e.g. chem-ball, physics-ball, bull-and-bear (economics) ball etc. For a while, we have wanted our own CS ball – and thanks to a team of keen MSc students and sponsorship from the School of Computer Science – the ball is finally happening!

The tickets available from https://www.eventbrite.co.uk/e/first-ever-cs-ball-smurfalicious-blue-ball-tickets-35035549271 are priced at £39.95, which includes:

  • Full 3 course dinner (starter, main, dessert) with 4 options each to choose from – including vegan/vegetarian/pescaterian options and adjustments for Halal etc.
  • A glass of champagne or a non-alcoholic mocktail
  • A Ceilidh till midnight
  • Return transport by coach from St Andrews to The Old Manor Hotel

The ball will strengthen our sense of fellowship, between all staff and students, and not least as a school. But as you all know very well, we are not just a school, we are a family – the St Andrews #csfamily. Hope to see many of you there!

FAQ:

https://www.smurf.com/

Info and files provided by Shyam Reyal

Computer Science: June Graduation 2017

Congratulations to our Senior Honours Class of 2017, MSci Honours students and our PhD students Dr Anne-Marie Mann, Dr Ildiko Pete, Dr Yuchen Zhao and Dr Michael Mauderer, who graduated on Wednesday. Students were invited to a reception in the School prior to the ceremony, to celebrate their achievement with staff, friends and family. We echo the sentiments expressed by our Head of School, Professor Steve Linton, during his Graduation address.

“For what you have achieved here, we are so proud of you. For what you will achieve, we wait eagerly and will always be proud. And wherever you are, we hope you will always regard St Andrews as a place you can call home.”

Our graduates will indeed move on to a wide variety of interesting and challenging employment and further study opportunities, and we wish them all well with their future careers.


Images courtesy of Annemarie Paton and Ryo Yanagida.

Lecturer/Senior Lecturer in Computer Science

The School of Computer Science is looking to recruit new academics as part of a large on-going expansion of our academic staff. We wish to appoint two new Lecturers/Senior Lecturers (depending on experience) to join our vibrant teaching and research community that is ranked amongst the top venues for Computer Science education and research worldwide.

You will be a scholar with a growing international research reputation in Computer Science and a commitment to delivering high quality teaching within the broad field of Computer Science and its applications. The successful candidate will be expected to have a range of interests, to be active in research publication that strengthens or complements those in the School and to be capable of teaching the subject to undergraduate and taught postgraduate students who come to us with a wide range of backgrounds.

Candidates should hold a PhD in a cognate discipline. Excellent teaching skills and an interest in promoting knowledge exchange are essential. You should also have some familiarity with grant seeking processes in relation to research councils and other sources.

Informal enquiries can be directed to Professor Steve Linton (hos-cs@st-andrews.ac.uk) or Dr Dharini Balasubramaniam (dot-cs@st-andrews.ac.uk).

Applications are particularly welcome from women, who are under-represented in Science posts at the University. You can find out more about Equality & Diversity at https://www.st-andrews.ac.uk/hr/edi/.

The University of St Andrews is committed to promoting equality of opportunity for all, which is further demonstrated through its working on the Gender and Race Equality Charters and being awarded the Athena SWAN award for women in science, HR Excellence in Research Award and the LGBT Charter; http://www.st-andrews.ac.uk/hr/edi/diversityawards/. The School endorses the Athena SWAN charter and is actively working towards recognition.

We encourage applicants to apply online, however if you are unable to do this, please call +44 (0)1334 462571 for an application pack.

Please quote ref: AC2116SB

Closing Date: 23 June 2017

Associate Lecturers in Computer Science

The School of Computer Science is looking to recruit new academics as part of a large on-going expansion of our academic staff. We wish to appoint two new Associate Lecturers to join our vibrant teaching and research community that is ranked amongst the top venues for Computer Science education and research worldwide.

Associate Lecturers provide the backbone of our teaching capability, focusing more on the delivery of high-quality taught programmes while still having opportunities for research. You will be committed to innovation and delivery of high quality teaching within the broad field of Computer Science and its applications. The successful candidate will be expected to be capable of teaching the subject to undergraduate and taught postgraduate students who come to us with a wide range of backgrounds. The Associate Lecturer comes with an Education focussed academic promotion track to Lecturer, Senior Lecturer, Professor.

Excellent teaching skills and an interest in promoting knowledge exchange are essential. A PhD in a cognate discipline is an advantage, as is industrial or other experience. We are especially interested in individuals wanting to experiment and innovate in improving our student experience.

Informal enquiries can be directed to Professor Steve Linton – hos-cs@st-andrews.ac.uk or Dr Dharini Balasubramaniam dot-cs@st-andrews.ac.uk

Applications are particularly welcome from women, who are under-represented in Science posts at the University. You can find out more about Equality & Diversity at https://www.st-andrews.ac.uk/hr/edi/.

The University of St Andrews is committed to promoting equality of opportunity for all, which is further demonstrated through its working on the Gender and Race Equality Charters and being awarded the Athena SWAN award for women in science, HR Excellence in Research Award and the LGBT Charter; http://www.st-andrews.ac.uk/hr/edi/diversityawards/. The School endorses the Athena SWAN charter and is actively working towards recognition.

We encourage applicants to apply online, however if you are unable to do this, please call +44 (0)1334 462571 for an application pack.

The University is committed to equality of opportunity.

The University of St Andrews is a charity registered in Scotland (No SC013532).

Please quote ref: AO1501AC

Closing Date: 23 June 2017