Upcoming Deadlines for the EATCS Awards

The deadline for submitting nominations for the EATCS Award 2013 and the Presburger Award 2013 is December 31. You have a little longer to propose papers for the Gödel Prize 2013 (deadline for nomination: 11 January 2013), which is jointly awarded with SIGACT.

I hope that you will take the time to send in nominations for those awards and to honour the work of some of the many outstanding researchers in TCS.

Xavier Leroy Receives Microsoft Research: 2012 Verified Software Milestone Award

Xavier Leroy of the Paris-Rocquencourt research center of INRIA, France, is the recipient of the 2012 Microsoft Research Verified Software Milestone Award. The award is given in recognition of Xavier's role as architect of the CompCert C Verified Compiler as well as his leadership of the development team.

The formal presentation of the Award will be made to Xavier at POPL 2013, which will take place in Rome, January 23-25, 2013.

The full award citation can be accessed here.  Its executive summary reads: 

"Microsoft Research is delighted to celebrate the advances made by Dr Leroy in the vital field of software verification. Compilers are the basis for all the software we generate, and by ruling out compiler-introduced bugs, the CompCert project has taken a huge leap in producing strengthening guarantees for reliable critical embedded software across platforms. We congratulate Dr Leroy on his significant achievement in winning this Award." 

Congratulations to Xavier for this  important recognition of his long-term work on CompCert.

Call for post-doctoral research positions at the Warsaw Center of Mathematics and Computer Science

I just received this call from Bartek Klin. Since it might be of interest to readers of this blog, I decided to post it. Warsaw is a hotbed for TCS research. Follow the links below for more details.

-----------------

Call for post-doctoral research positions at the Warsaw Center of Mathematics and Computer Science.

Warsaw Center of Mathematics and Computer Science (WCMCS) is a joint project of two scientific units: the Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw (MIMUW), and the Institute of Mathematics of the Polish Academy of Sciences (IMPAN). The Center is built on the long-standing cooperation between the two units, in both teaching and research. The Center was designated as a Leading National Research Center (Krajowy Naukowy Osrodek Wiodacy, KNOW) by the Polish Ministry of Science and Higher Education in July 2012. The award comes with a substantial grant which will provide financing of the Center for the next five years. The grant will be used for enhancing the research potential of both participating institutions; this includes financing post-doctoral positions.

The post-doctoral research positions at the WCMCS are aimed at young researchers who have just received their PhD. Successful candidates will be employed as an adiunkt (assistant professor) at one of the following institutions, as indicated in the candidate’s application:
* the Faculty of Mathematics, Informatics and Mechanics at the University
of Warsaw, http://www.mimuw.edu.pl; or
* the Warsaw branch of the Mathematical Institute of the Polish Academy of
Sciences, http://www.impan.pl

The positions are for 6-12 months, with a possible extension to at most 18 months, altogether. The salary will be 7000 PLN per month, before taxes. In addition, the holder of the position will be eligible for financial support to participate in scientific meetings.

The position comes with a teaching load of up to 60 hours per semester. At least 3/4 of the position’s duration should be between October 1 and June 30.

The applicant should have defended their PhD not earlier than 4 years before the planned beginning of the position. This period can be prolonged by the parental leave.

The candidate applying for a post-doc position at the WCMCS should submit the following documents:
* a cover letter of application addressed to the Board of WCMCS,
indicating the institution (MIMUW or IMPAN) and the period of his/her
employment,
* a CV including a list of publications, and copies of 5 best papers, at
most,
* a document that confirms holding the PhD Degree or information about the
expected date of obtaining such a degree,
* a research plan including a collaboration scheme with researchers from
MIMUW or IMPAN.

All documents should be sent as pdf files to the following e-mail address: wcmcs.postdoc@mimuw.edu.pl In addition, the applicant should ask at most two senior researchers to send their letters of support to the same e-mail address. The deadline for application is December 10, 2012.

A successful candidate can take his or her job immediately after the announcement of the results of the selection and not later than 8 months after that moment. If the candidate has no PhD degree while submitting, before starting the work he or she should present a document that confirms holding the degree.

More information about WCMCS at http://www.wcmcs.edu.pl

Jean van Heijenoort: Kaleidoscope

Yesterday, an email message on the FOM mailing list alerted me to the availability of a special issue of the journal Logica Universalis in celebration of the centenary of the birth of Jean van Heijenoort. I could not resist reading the contribution entitled Jean van Heijenoort: Kaleidoscope by  Anita Burdman Feferman. This 15-page piece is a wonderful read and paints the picture of a personality who must have been truly (much) larger than life. How often does one meet a logician who was a personal secretary to Leon Trotsky from 1932 to 1939, and from then until 1947, an American Trotskyist activist? Not to mention that he also had a love affair with Frida Kahlo to boot and that he was killed by his wife in an act of passion.

The book Politics, Logic, Love: The Life of Jean van Heijenoort by
Anita Burdman Feferman is now firmly on my list of things to read. (You can read a review here.)

Guide for Application to Obtain an Italian National Scientific Qualification

The new recruiting process for  full and associate professor positions in Italian universities is based on a two phase process. Candidates must first obtain the so-called Abilitazione, and then apply for a position at an Italian university. See here for more details.

In order to facilitate international participation in the first stage of this process, the University of Rome "La Sapienza" has created a guide and a series of video tutorials to help researchers who are not fluent in Italian or familiar with Italian rules apply.

For what they are worth (i.e. nothing), here are two considerations off the top of my head. 

1. First of all, kudos go to "La Sapienza" for producing this supporting material. I am not aware of other Italian institutions that are taking this step and/or who have search committees that are actively looking for foreign applicants. (If you are, please post a comment.)
2. There is probably something not quite right with a system that needs to be explained using four videos on YouTube :-)

Having said so, I sincerely hope that this new Italian process for recruiting university professors, based on scientific qualification criteria, will help the top Italian CS departments to become even stronger than they already are and that it will offer a ray of hope to young Italian academics. It will also be interesting to see how many non-Italians will apply for the abilitazione. 

Call for nominations: Gödel Prize 2013

The Call for Nominations for the 2013 Gödel Prize has been posted (pdf). Nominations for the award should be submitted to the Chair of the Award Committee, Sanjeev Arora - goedelchair@gmail.com. The deadline for nominations is January 11, 2013.

Any research paper or series of papers by a single author or by a team of authors is deemed eligible if

• the paper was published in a recognized refereed journal no later than December 31, 2012;
• the main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 2000.

The Award Committee consists of  Krzysztof R. Apt (CWI Amsterdam and University of Amsterdam), Sanjeev Arora, Chair (Princeton University), Josep Díaz (Universitat Politècnica de Catalunya), Giuseppe Italiano (Università di Roma Tor Vergata), Daniel Spielman (Yale University), and Éva Tardos (Cornell University). On behalf of the TCS community, I thank the committee members for their important service.

Let me close with a message to the "volume B community". Perhaps the logic/semantics/programming languages community should think strategically, look at the most prominent journal papers meeting the eligibility requirements and drum up the strongest possible support for those. Feel free to look at your crystal ball and suggest candidates for nomination using comments to this post.

As the new president of the EATCS until ICALP 2014, I am taking a sabbatical from issuing nominations in order to avoid any possible conflict of interest.

John Cleese on creativity

Recently, I posted a link to a lecture on creativity in computer science by one of my PhD students. After having done so, I was struck by the thought that, at some point, I had watched an excellent, and very funny, lecture by John Cleese on creativity. Here it is, in case any of my readers wants to have a look.

Call for nominations: Presburger Award 2013

The call for nominations for the EATCS Presburger Award 2013 is out. The Presburger Award is given to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers.

Scientists nominated for the award have to be at most 35 years old at the time of the deadline of nomination, which is the 31st of December 2012. This means that  the date of birth of researchers nominated for the Presburger Award 2013 should be in 1977 or later.

The award committee for 2013 consists of Monika Henzinger (chair), Antonin Kucera (who is one of the vice-presidents of the EATCS) and Peter Widmayer.

I hope that you will sharpen your pencils and nominate your favourite young TCS researcher for this award.

Call for nominations: EATCS Award 2013

The call for nominations for the EATCS Award 2013 is about to be published officially. However, you can already see it here.

I hope that you will consider submitting a nomination. There are many colleagues out there who would be worthy of this honour, but they can only receive the award if someone nominates them. (I know that this is a triviality, but sometimes people do not send in nominations for their favourite candidates and then wonder why they did not get the prize :-))

Expect more calls for nominations over the next few days.

Lecture on creativity by one of my PhD students

Last week, Eugen-Ioan Goriac, who is a third-year PhD student of mine, delivered a lecture on creativity as part of the Research Methodology course that I am running at Reykjavik University.

Eugen has made a video of his lecture available on YouTube. Here it is, in case it might be of interest to some of my readers.

Enjoy it!

The Feit-Thompson theorem checked in Coq!

The Feit-Thompson Theorem  is a key result in the theory of finite groups. Its original proof is 255 pages long and is perhaps the first example of a very long and highly complex proof in group theory.

At 5:46 p.m. on September 20, Georges Gonthier sent an email to his colleagues at the Microsoft Research-Inria Joint Centre in Paris announcing the completion of a six-year effort to prove the Feit-Thompson Theorem in the Coq proof assistant. The mail read, in full: “This is really the End.”

You can read more about this work here and here. 

Congratulations to Georges and his coworkers on this monumental achievement!

Invitation to becoming a member of the Italian Committees for professorships

The letter below will be sent to some mailing lists soon. I am posting it here since it is in the interests of the TCS community as a whole to be well represented in this exercise. Despite being amongst the signatories of this letter, I have no academic position in Italy. I am simply an interested observer of academic life in my home country.

Dear colleagues,

The recruitment system for academic staff at Italian universities has recently been changed. The new procedure requires that academics attain the so-called National Scientific Qualification in order to take up a position in an Italian university at the level of associate or full professor. The qualification is granted by National Committees, one for each group of disciplines. All committees are made up of five members, four affiliated to Italian universities and one affiliated to a foreign university located in an OECD country. Members from foreign universities must hold a position equivalent to that of a full professor.

We think that it would be very useful for our research community if you submitted a candidacy to become a foreign member of the National Committee. If you are interested in doing so, you can register your candidacy at

https://abilitazione.cineca.it/ocse/index.php?lang=EN

by September 24.

To submit your candidacy, you will have to include a curriculum vitae, the list of scientific publications, the selected disciplinary fields, the number of citations received by your work and your h-index. As part of this process, you will be asked to select one or more Italian Scientific fields from a scroll-down menu (choose at least 01/B1 - Informatics) and some ERC Scientific fields. (There is a scroll-down menu for that too.)

Based on this information, the Italian national agency for the evaluation of universities and research Institutes (ANVUR) will select at least four possible foreign members for each scientific group. The foreign member of each committee will then be randomly selected among those in the lists. The committee will be in service for two years, during which two rounds of evaluations will be carried out. Names and CVs of the selected candidates will be published on the ANVUR website. Members of the evaluation groups will receive an honorarium of 16,000 € for the whole period, plus expenses.

We hope that you will consider submitting your candidacy.

All the best,
Luca Aceto, Rocco De Nicola, Mariangiola Dezani-Ciancaglini

Research Methodology in Computer Science

Our autumn semester starts on Monday and I will be teaching the Research Methodology course for master students in computer science and software engineering. This is a 15-week course and I am looking forward to the challenge of keeping the students interested and busy over 30 course sessions. (I have taught short courses on this topic at master and PhD level at different institutions, but this is a substantially larger endeavour.)

At the end of the course, my students are expected to be able to

• Explain research, research methodologies, and research in Computer Science; 
• Select a research subject and conduct a research project;  
• Write technical reports, papers, theses, and proposals effectively;  
• Give good presentations;  
• Read and review a technical paper properly; 
• Explain professional ethics: allocation of credit, authorship issues, conflict of interest and misconduct in science.

I am compiling a list of resources available on the web related to these aspects of our job and will make them available in due course. What publicly available presentations, videos and essays would you recommend that I include? Are there any courses similar to this one that you think I should look at?

CadiaPlayer GGP Champion Again!

I am proud to announce that the general-game-playing agent CadiaPlayer, developed at my own department by Yngvi Björnsson, Hilmar Finnsson, Stefán Freyr Guðmundsson and Stephan Schiffel, won this year's General Game Playing competition hosted at the AAAI conference, thereby reclaiming the title it lost in 2009.  On its road to the title it defeated among others the winners from the previous two years. As a winner of the competition CadiaPlayer also played an exhibition match consisting of three games against a human player --- Chris Welty from IBM --- and won convincingly.

With this title CadiaPlayer has become the most victorious GGP agent ever, and the only agent so far to win the competition three times.

Congratulation to the CadiaPlayer team!

PhD positions at IMT Lucca (reprise)

I am happy to post a revised version of the call for PhD positions at IMT Lucca that I received today from Alberto Lluch Lafuente and Rocco De Nicola. Distribute the announcement as you see fit.

 
The Institute for Advanced Studies IMT Lucca - Italy (http://www.imtlucca.it/) announces 36 PhD scholarships providing about €13,600 EUR gross yearly plus accommodation and full board. Deadline for application is September 26, 2012.

IMT Lucca (Italy) is an Institute for Advanced Studies and an International Graduate School that acts as a research university with the aim of forming human capital in disciplines characterized by their high potential for concrete application. IMT strives to reach the fusion of theoretical comprehension and practical relevance.

PhD programs are taught exclusively in English. The PhD Program includes a Track in Computer, Decision and Systems Science with a specific Curriculum in Computer Science. The track is coordinated by Rocco De Nicola and aims at preparing researchers and professionals with a wide knowledge of the theoretical foundations of computer science and informatics, control systems and optimization, image analysis, and management science.

The curriculum in Computer Science focuses on languages, models, algorithms, and verification methods for modern distributed systems. PhD students following the curriculum in Computer Science will perform their activities in collaboration with the SysMA research unit (http://sysma.lab.imtlucca.it/) on system modelling and analysis. This research unit focuses on formal languages, models, methodologies and tools to support the development of correct software systems with high quality in terms of predictability, security, efficiency, usability, re-usability, maintainability, and modularity.

We hope that you might consider applying

http://www.imtlucca.it/phd/call_for_applications/

If you are not personally interested, please help us signaling these opportunities to colleagues and collaborators. For further information please contact Alberto Lluch Lafuente or Rocco De Nicola.

Samson Abramsky discusses the legacy of Turing

Readers of this blog might be interested in this podcast by the Royal Society in which Samson Abramsky discusses the legacy of Turing. Samson is one of the editors of The foundations of computation, physics and mentality: the Turing legacy, a special issue of Philosophical Transactions of the Royal Society A devoted to "the richness of Alan Turing’s intellectual legacy in the modern conception of computation."

Enjoy!

Random thoughts on conference presentations

1. When giving an invited talk at a general TCS conference, do not assume that everyone in the audience is interested in the technicalities of your subject. Focus on the main message, tell the story of the ideas and why you think they are important. Give everyone something to take home. 
2. Do not assume that you do not need to introduce the setting for your work because someone else has done it before or on an earlier conference day. Not everyone will have attended the talks where the background and motivation were presented.
3. Do not run over time.
4. Never speak with your hands on your mouth, even if it feels good :-)
5. Do not let your voice drop to an inaudible level as your sentence progresses. Dare to speak slowly and loudly.
6. Ask yourself: How many slides do I really need for a 20-minute talk? Most of us will only use a few, and those should convey the message of the talk at a suitable level of abstraction.
   

The advice we give others is the advice we ourselves need.

ICALP 2012: Days 3-5

At long last, here are some of my notes from the main events that took place during the last three days of ICALP 2012. There were several excellent talks at Track B (which is the one I attended) and I hope to find the time to discuss some of my favourite papers at some point.

Day 3 was given the best of starts by Gilles Dowek's invited talk entitled A theory independent Curry-de Bruijn-Howard isomorphism. (The slides are here and the abstract is here.) IMHO, Gilles pitched his talk at precisely the right level for a general conference in TCS like ICALP and my impression was that he gave each attendee something to take home, regardless of their area of expertise.

Gilles introduced the seminal Curry-de Bruijn-Howard isomorphism, which was in fact originally proposed by Brouwer, Heyting, and Kolmogorov, who suggested to de fine constructive proofs as algorithms. He surveyed the principles behind the plethora of existing proof processing systems and the principles that led to the development of the universal proof checker Dedukti. Oversimpliying, Dedukti is based on what Gilles called Hilbert and Ackermann’s paradise: one logic and many theories. The logic is the lambda-Pi-calculus proposed by Harper, Honsell and Plotkin. However, theories are represented using rewrite systems, rather than using axioms. Indeed, according to Gilles, "Axioms suck!" (from the point of view of efficiency).

Overall, I enjoyed the talk by Gilles a lot. It was a pity that it was not as well attended as it should have been.

At the start of day 4, Dan Spielman gave an excellent talk on using graph theory to solve linear equations. The talk was entitled Algorithms, Graph Theory, and the Solution of Laplacian Linear Equation and the Laplacian was the main character in the story that Dan recounted with verve and clarity. For further reading on this topic, Dan himself suggested this article by Erica Klarreich at the Simon's Foundation. In passing, Dan also described a method for obtaining "obscenely accurate solutions to a problem by solving a simpler one". 


I had had the pleasure to hear Dan deliver a talk on smoothed analysis when he was a co-recipient of the Gödel Prize 2008 in Reykjavík and I watched the video of his talk at the latest ICM. IMHO, the invited talk at ICALP 2012 confirmed him yet again as one of the very best speakers around. 


Day 4 at ICALP 2012 was also devoted to the awards of the Gödel Prize 2012 and of the EATCS Award. As you surely know already, the Gödel Prize went to three seminal papers in the field of Algorithmic Game Theory. Christos Papadimitriou delivered a talk on behalf of the recipients of the Gödel Prize, who were all . present at the conference apart from Noam Nisam. Christos explained the intellectual roots of the concept now known as the price of anarchy and of algorithmic mechanism design. Moreover, he asked the question: What makes an idea spread? His answer was that an idea spreads if it gives young researchers an opportunity to show how smart they are! 


Christos concluded his talk by being a prophet of doom. (I am using his own words here.) He reminded the people in the audience that, for people like me, the "Hello World" program was Max, a program for finding the largest entry in an array of integers, say. The world has changed. Computation has changed. The inputs to our programs are selfish agents who are interested in the outcome of our computation. Vickrey is the new Max :-)

The EATCS Award went to Moshe Vardi (laudatio), who delivered a presentation entitled  A Logical Revolution. In the talk, Moshe described how logic has one from irrelevance to relevance in our field. The key lessons in this rise of logic are the importance of algorithms, heuristics and tools. One of the key insights is that one should not be scared of worst-case complexity: It always barks, but it does not always bite! Efficient in the field of logic in computer science means exponential. "Exponential is the new polynomial." 

Both award presentations were excellent and were given a long round of applause from a packed audience. 


The last invited talk at ICALP 2012 was delivered by Kohei Honda. Kohei´s talk was entitled Session types and distributed computing. It described the origins of the notion of session type and how sessions types find application in the NSF Ocean Observation Initiative. This represents one of the most impressive applications of notions from concurrency theory outside computer science. Kohei is also one of the prime movers behind the programming language Scribble. His talk was a fitting finale to an excellent ICALP conference.

Thanks again to Artur Czumaj and his team for arranging an excellent conference in the beautiful setting of the University of Warwick.

ICALP 2012: First two days

ICALP 2012 is taking place at the University of Warwick. The programme is action packed, with many highlights and prizes. There are three tracks with 123 selected papers (71 for track A, 30 for track B and 22 for track C) out of 432 submissions (248 for track A, 105 for track B and 79 for track C). The acceptance rate was therefore around 28.5%. In addition, there are five invited talks and on day two David Harel delivered a Turing talk.

The conference is being attended by 210 participants (146 regular and 64 students).

There is so much going on that it is hard to give a detailed report on the scientific activities. I will thus limit myself to a few short remarks on some of the highlights of the first two days of the conference.

• The first two invited talks were delivered by Stefano Leonardi (Sapienza University of Rome) and Berthold Vöcking (RWTH Aachen). Both speakers focussed on algorithmic aspects of auctions. Stefano's talk was entitled On Multiple Keyword Sponsored Search Auctions with Budgets, while the talk by Berthold dealt with Randomised Mechanisms for Multi-Unit Auctions. 
• Leslie Ann Goldberg delivered a very inspiring talk on her joint paper with Mark Jerrum The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation), which received the best paper award for track A. Leslie brilliantly conveyed her enthusiasm for this amazing polynomial even to a layman like me, and gave us a glimpse of the rich mine of information that the Tutte polynomial contains about a graph. (W. T. Tutte also figured prominently during the very instructive excursion to Bletchley Park we enjoyed yesterday.)
• Manfred Kufleitner presented his joint work with Volker Diekert, Klaus Reinhardt and Tobias Walter that received the best paper award for Track B. Their truly remarkable result settles a long-standing open problem in formal language theory and may be found in the paper Regular Languages are Church-Rosser Congruential.  
• Tuesday saw an excellent Turing talk by David Harel on three strands of his research over the years that have been influenced by Turing's work.  I enjoyed it a lot and I finally got a chance of hearing David Harel deliver one of his trademark talks. 
• The Presburger award went to Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs). Venkat gave a talk that highlighted the web of connections that arise in his work and how tools from one area can find application in another one. He ended his talk was quoting the title of a talk by Avi Widgerson, namely "Depth through breadth". Mikkel Thorup gave a heartfelt presentation, describing Mihai Patrascu's work and personality. Several participants took photos for the Cheers to Mihai! web site. 
• The EATCS general assembly lasted until 8.50pm. Kurt Mehlhorn gave a very entertaining and thought-provoking report from the PC chairs. He said, amongst other things, that the submission data show that Track A researchers like to work in pairs or triples, Track B people like to work in pairs and that Track C papers are typically co-authored by a group of people. 
• ICALP 2014 will be held at the IT University in Copenhagen with Thore Husfeldt as general chairs. SWAT 2014 will take place just before ICALP and you will be able to enjoy the Copenhagen Jazz Festival too!

The conference is being organized by Artur Czumaj and his team. Kudos to them for having done a truly excellent job. Thanks to all of them!

I will try to post a telegraphic report on the rest of the conference as soon as I have a little time. I hope that other ICALP participants will share their opinions on the conference and their short reports as comments to my quarter-baked posts. 

LICS Test-of-Time Awards 2012

Prakash Panangaden has informed me that the LICS Test-of-Time Award for 2012 has gone to the following two papers:

• Thomas A. Henzinger, Xavier Nicollin, Joseph Sifakis and Sergio Yovine. Symbolic Model Checking for Real-Time Systems. 
• Jean-Pierre Talpin and  Pierre Jouvelot. The type and effect discipline.

The first article has received a huge number of citations for a LICS paper (1172 according to Google Scholar). It develops a thorough theory of symbolic model checking for timed CTL over finite automata with real-valued clocks.  It presents an algorithm that computes the set of states that satisfy a formula symbolically as a fixed point of a functional on state predicates, without constructing the state space. For this purpose, the authors introduce T_mu, a mu-calculus on computation trees over real-numbered time that has been studied by other researchers in further developments, and investigate its expressive power relative to that of timed CTL. Overall, this has been an influential contribution for the fragment of the CAV community dealing with real-time systems.

The second paper has been recognized an an important contribution to the theory of types and has received 331 citations  according to Google Scholar. The type and effect discipline is a framework for reconstructing the principal type and the minimal effect of expressions in implicitly-typed polymorphic functional languages that support imperative constructs.

Congratulations to the award recipients!

PhD Positions at IMT Lucca

IMT Lucca has issued its call for applications for admission to the IMT Ph.D. Program beginning in January 2013. Readers of this blog (or their students) might be interested in the track called Computer, Decision, and Systems Science, whose director is Rocco De Nicola.

The raw data about this call for PhD applications are as follows:

• 36 Ph.D. positions are covered by scholarships in the gross amount of 13,638.47€ /year.
• A limited number of additional positions without scholarships may also be offered.
• Ph.D. students will have tuition fees waived.
• Ph.D. students who are granted a scholarship have free accommodation in shared double rooms in the School residence halls (with the exception of students whose permanent residence is within 30km of IMT).
• Ph.D. students will have free access to the canteen services.
• Ph.D. students are covered by insurance against any accident and/or injury that may occur while they carrying out their Ph.D. activities.

For more information about IMT, I encourage you to look at their excellent recruitment video. IMT is growing and promises to become a hotbed of research at the intersection of computer science, control theory, economics and statistical physics. At least, the level of ambition is high.

Let me add, as icing on the cake, that Lucca is a lovely little town, which is close to many other beautiful Italian cities. Encourage good students to apply for the advertised positions!

Best paper awards at ICALP 2012

The preliminary version of the detailed programme for ICALP 2012 is now available here. While skimming through the programme, I learnt that the best paper awards for the conference will go to the following papers:

• Leslie Ann Goldberg and Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation). Best paper for Track A. 
• Volker Diekert, Manfred Kufleitner, Klaus Reinhardt and Tobias Walter. Regular Languages are Church-Rosser Congruential. Best paper for Track B.
• Piotr Krysta and Berthold Vöckin. Online Mechanism Design (Randomized Rounding on the Fly). Best paper for Track C.

The best student papers are:

• Anastasios Zouzias. A Matrix Hyperbolic Cosine Algorithm and Application. Co-recipient of the best student paper for Track A.   
• Shelby Kimmel. Quantum Adversary (Upper) Bound. Co-recipient of the best student paper for Track A. 
• Yaron Velner. The Complexity of Mean-Payoff Automaton Expression. Best student paper for Track B.
• Leonid Barenboim. On the Locality of NP-Complete Problems. Best student paper for Track C.

Congratulations to all the award recipients!

The scientific programme for ICALP 2012 looks really action packed. The invited speakers are:

• Gilles Dowek (INRIA Paris)
• Kohei Honda (Queen Mary London)
• Stefano Leonardi (Sapienza University of Rome)
• Daniel A. Spielman (Yale)
• Berthold Vöcking (RWTH Aachen)
• Alan Turing talk: David Harel (The Weizmann Institute of Science)

During the conference, there will be presented three special awards: EATCS/ACM SIGACT Gödel Prize 2012, EATCS Award 2012, and EATCS Presburger Award 2012.

• EATCS and ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) awarded the Gödel Prize 2012 to three groups of researchers for their contributions to understanding how selfish behavior by users and service providers impacts the behavior of the Internet and other complex computational systems. The papers were presented by Elias Koutsoupias and Christos H. Papadimitriou, Tim Roughgarden and Éva Tardos, and Noam Nisan and Amir Ronen.
• The Presburger Award Committee 2012, consisting of Monika Henzinger, Antonin Kucera, and Stefano Leonardi (chair), has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs) as joint recipients of the 2012 EATCS Presburger Award for young scientists. (pdf)
• The EATCS Awards Committee consisting of Leslie Ann Goldberg, Friedhelm Meyer auf der Heide and Eugenio Moggi (chair), has unanimously decided to give the 2012 EATCS Award to Moshe Vardi (Rice University). (pdf)

The main conference will be preceded by a series of workshops taking place on Sunday, July 8.

Accepted papers at ICALP 2012

The list of papers that have been selected for the three tracks of ICALP 2012 is now available. The preliminary programme is also on line. This looks like an action-packed ICALP, with a plethora of interesting invited talks, award sessions and good-looking papers. I look forward to the conference.

EATCS and Presburger Awards for 2012

It is award time for the EATCS.

The EATCS Award for 2012 will go to Moshe Vardi. (The award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.) You can read the laudatio here.

The Presburger Award Committee 2012 has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs, New York) as joint recipients of the 2012 EATCS Presburger Award for young scientists. See here for the details.

Congratulations to all the recipients of the two awards! 

Fifth Talk in the Alan Turing Year at Reykjavík University

The fifth talk in the Alan Turing Year at Reykjavík University was delivered this afternoon by my colleagues Yngvi Björnsson and Kristinn R. Thórisson. The talk was entitled Alan Turing's Contributions to Artificial Intelligence: Can Machines Think? and has been organized in collaboration with CADIA and IIIM. This was a thought-provoking and very enjoyable scientific event. In case you are interested the audio and the slides of the talk are here in .avi format. (Note: For technical reasons only the audio of Kristinn's presentation is available.)

In his presentation, Yngvi introduced the field of AI, its subbranches (applied AI, strong AI and cognitive AI) and highlighted Turing's main contributions to the field. On the other hand, Kristinn presented a critique of the Turing Test. Kristinn is a firm supporter of strong AI and his position on this matter can be summarized as follows. (I hope that I am not misrepresenting his views too much.)

1. The standard divide-and-conquer approach that we use in science to understand phenomena is not going to help us understand "intelligence", at least not if applied in the same way as has been done so far in AI, namely by using it in a reductionist way to remove features that are central to the phenomenon of intelligence.
2. The Turing Test was a very premature attempt at devising a test for the phenomenon of intelligence that forced upon much constructionist AI research the view that "intelligence is X, where X is some very simple manifestation of natural intelligence."

Overall, I left the talk with plenty to muse on, assuming I will have the time and the brains for this activity.

Reading material:

• “Computing machinery and intelligence” by Alan Turing (1950) (hosted by Hugh Loebner)
• The Turing test entry in the Stanford Encyclopedia of Philosophy.

PC-chair-authored papers at conferences

Perhaps it is just me, but I feel that there has been an increase in the number of papers (co-)authored by PC chairs selected for presentations at conferences. This seems to happen mostly at "specialist" conferences. I have noticed a similar trend for special issues of journals, to which guest editors are often allowed to submit contributions. In that case, the submission is handled by a member of the editorial board as an ordinary paper submitted to the journal.

Is it just me? If not, do you think that this is a good development?

Assistant professor position at Chalmers University of Technology

I have been asked to spread the news about this position. It looks like a very exciting opportunity for an ambitious young scientist.

We're looking for a talented and ambitions Assistant Professor in Information and Communication Technology at Chalmers University of Technology, Gothenburg, Sweden.

The position includes at least 80% research time and prestigious
status of Area of Advance at Chalmers:
http://www.chalmers.se/en/areas-of-advance/ict/Pages/default.aspx

The area of security is well in scope of the position. Please, help
spread the word!

Application deadline: May 1, 2012

Further info and application link:
http://web1.reachmee.com/i003/chalmers/se/vacdetail.aspx?commadseqno=502&postback%20=%20vacancies.aspx

J.E. Littlewood's take on "research strategy"

I really enjoyed reading the post Are You Working too Hard?, watched the linked videos and read some of the accompanying material from Uri Alon's web site. Whenever I stumble across this kind of material, I tend to go back to one of my favourite sources of inspiration related to the academic's art of work, namely the delightful piece The Mathematician's Art of Work by J.E. Littlewood. In that piece, "with a good deal of diffidence", Littlewood tries to give "some practical advice about research and the strategy it calls for."  Here is a summary of his advice.

• On days free for research, Littlewood recommends working at most five hours with breaks about every hour (for walks perhaps). Littlewood claims that without breaks one acquires the habit of slowing down unconsciously.
• Either work all out or rest completely. It is too easy to fritter a whole day away with the intention of working but never getting properly down to it.
• For a week without teaching duties, take one afternoon and the following day off. The day off should stay the same each week. 
• Take three weeks of holiday at the beginning of each vacation. This period is necessary and sufficient for recovering from the severest mental fatigue. 
• Morning work is far better than work done at other times of the day. From a certain point onwards, following severe concussion in 1918, Littlewood never worked after 6.30pm.
• Try to end your day's work in the middle of something; in a job of writing out, stop in the middle of a sentence. This will help warming up the morning after. 
• An ominous symptom of overwork is an obsession with the importance of work, and filling every moment to that end.

How would your work pattern compare to these pieces of advice? In my case, the answer would not be pretty and I feel that the same applies to many of my closest colleagues. The obsession with the importance of work has been there for a while and ........

Accepted papers for LICS 2012

The list of accepted papers for LICS 2012 is now out.

The first thing to note is that the PC for LICS 2012 has selected 61 submissions for presentation at the conference. By way of comparison, there were 37 papers that were presented at LICS 2011 (modulo counting mistakes I might have made.) This increase in the number of selected papers follows one of the changes that LICS 2012 promised to implement:

In response to concerns about LICS becoming overly selective with a too-narrow technical focus, the program committee will employ a merit-based selection with no a priori limit on the number of accepted papers.

Does this higher number of selected papers imply a "decrease in the quality of the conference programme", whatever that may mean? I have not read the papers yet, but a quick look at the list of selected papers and a brief look at the introduction of some of those available on line seem to indicate that this installment of LICS will be at least as strong as the others. Time will tell. My gut feeling is that this will be a very exciting conference.

I hope that someone attending the conference will be willing to send me a report for this blog. Let me know if you are interested in sending me a short report from LICS 2012.

Holding LICS in Croatia will be an interesting experiment. LICS 2012 will be hosted by the University of Dubrovnik, in Dubrovnik, which is a lovely town along the Adriatic sea. The location and the quality of the conference programme should entice many colleagues to attend the event. Unfortunately, the early registration fee looks pretty hefty to me: $450 for ACM, IEEE or ASL members and $600 for non-members are a lot of money at a time when travel money is scarce. (By way of comparison, the registration fee for ICALP 2011 in expensive Zurich was roughly €334.)

Last, but not least, it will be interesting to see which papers will receive the LICS Test-of-Time Award for 2012. Do you have any predications you'd like to share in the comment section?

Endre Szemerédi has been awarded the Abel Prize for 2012

Timothy Gowers just announced that  Endre Szemerédi has been awarded the Abel Prize for 2012. The citation reads:

"for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory."

This is a truly major day for discrete mathematics and TCS.  Look at  the Abel Prize web site and at the written version of the talk by Timothy Gowers,  addressed to a general audience, for more details.

ICE-TCS Annual Report for 2011

The ICE-TCS annual report for 2011 is now available. The main aims of our small centre are to establish TCS as a visible research area in Iceland, to attract students to it and to organize high quality TCS events in the country. We have been at it since 2005 and we hope to keep going.

Third Talk in the Alan Turing Year at Reykjavík University

The third talk in the Alan Turing Year at Reykjavík University was delivered last Thursday by Bjarni V. Halldórsson and dealt with Alan Turing's work on mathematicalbiology. (The event was organized jointly with the Icelandic Mathematical Society.) The audio of the talk is here in .avi format. The slides for the talk are here in .pdf format. Enjoy. 

This coming Thursday, Magnús M. Halldórsson will deliver a talk entitled The million dollar question: P vs. NP, and the legacy of Turing. I will post the audio of the talk as soon as it becomes available.

What does our job as academics consist of?

At this time of the year, my university produces its annual magazine. For good or for worse, typically I cannot resist the temptation to put pen to paper and to contribute one or two pieces to that publication. This year has been no exception, and I ended up writing a piece, aimed at students and the general public, that tries to explain what our jobs consist of. The reason for offering this specific contribution to the university magazine is that I have been feeling for a while that our students do not know what we do. And if they do not, what are the chances that anyone else will?

The result is Unveiling the Ivory Tower: The academic's art of work, just in case it may be of interest to any of my readers. 

Permanent Faculty Position in Computer Science, University of Camerino, Italy

Emanuela Merelli has asked me to distribute this announcement for a faculty position, which may be of interest to some readers of this blog.

Permanent Faculty Position in Computer Science
School of Science and Technology
University of Camerino

http://www.cs.unicam.it/home

The University of Camerino has opened a faculty permanent position at the level of Associate Professor in Computer Science for the School of Science and Technology.

We are interested in an lively and self-motivated candidate who is interested in working with existing faculty in one or more of the research areas within the Computer Science Division, in particular software engineering  and theoretical computer science. See
http://www.cs.unicam.it/home/component/content/section/2-research

for detailed information on the current research areas within the CS Unit.

Applicants should have published in international journals, had papers in proceedings of relevant conferences and given evidence of participation in international projects. The teaching language for some courses at Computer Science Division is English, hence applicants should have a track-record of teaching in English. Computer Science Associate Professor is expected to teach in the undergraduate, masters and PhD programs. Effective productivity and leadership in research, and interest in teaching are expected.

Applications must be sent, within 14 April 2012, to: Magnifico Rettore dell'Universita' di Camerino – Piazza Cavour 19/f, 62032 Camerino (MC).

See

http://www.unicam.it/servizi_online/cerca_bandi.asp

for detailed information.

Requirements for applicants: applications are welcome from candidates with the following qualifications:

a) candidates who received positive judgments according to “ Legge 210/1998” for the position corresponding to Associate Professor, candidates who were deemed fit for the position corresponding to Associate Professor according to “ Legge 210/1998” provided certification of fitness is still valid;

b) candidates who are already employed as associate professors in other universities i.e., since legislation “Legge 240/2010”;

c) scholars who are permanently employed in research or teaching activities at university level outside Italy in positions which are equivalent to those required in this call (according to ministerial equivalences).

Informal communication and discussions on any aspect related to the position are encouraged, and interested candidates are welcome to contact the chairman of the computer science division, Prof. Emanuela Merelli (emanuela.merelli@unicam.it), for further information.

The Computer Science Division of the School of Science and Technology at University of Camerino has about 500 students and 14 permanent staff members. The school offers undergraduate and graduate programs in computer science and the doctoral programme in Information Science and Complex Systems that currently hosts 18 PhD students. 

Situated up on the hill, Camerino, a beautiful little town of Central Italy with its medieval historical center hosts one of the most ancient university in Italy.

See

http://www.cs.unicam.it/home/component/content/category/15-living-in-camerino

for more information about living in Camerino.

Second Alan Turing Year Event at Reykjavik University

Last Friday, my colleague Ýmir Vigfússon delivered the second talk in the Alan Turing Year at Reykjavik University. His talk was entitled Alan Turing: The man who won the Battle of Britain and was organized jointly by ICE-TCS , the School of Computer Science at Reykjavik University and the Icelandic Mathematical Society.  In case anyone is interested, the audio of the talk, with the accompanying slides, is here in .avi format. I thoroughly enjoyed Ymir's talk and I strongly encourage my readers to listen to it. Thanks Ymir!

We plan to record all the talks in the series and to make them available on line here.

Faculty Position at IMT, Institute for Advanced Studies Lucca

Readers of this blog might be interested in this position, which has just been advertised. The call for applications states that:

Preference will be given to candidates performing research at the intersection between algorithms, theory and applications, and who are active in one or more of the following fields: analysis and modeling of massive data structures; graph theory and random structures; analysis and modeling of complex networks; machine learning; data mining; parallel and distributed computation.

Faculty Position
IMT Institute for Advanced Studies Lucca

IMT Institute for Advanced Studies Lucca  is an international Graduate School and Institute of Technology that strives to reach the fusion of theoretical comprehension and practical relevance. The following goals are at the core of IMT's mission statement:

* to establish itself as a research center that promotes cutting-edge research in key areas, structuring its Ph.D. Programs in close connection with research activity;
* to attract top students, researchers and scholars through competitive international selections;
* to contribute to technological innovation, economic growth and social development.

These objectives are met by means of the fundamental principles (the IMT Policy) adapted by the governing bodies of the Institute.

IMT has opened an international scouting procedure to recruit for a tenured faculty position in the following fields:

Computer Science and Engineering, Large Scale Data Mining, Graph Theory, Mathematical Statistics, Machine Learning

We will consider highly qualified candidates with a strong theoretical background in computer science, physics, statistics, information science, engineering, or mathematics, with an orientation towards research on processing huge amounts of complex data in the analysis of technical, socio economic or biological systems. Candidates must have an excellent record of high-impact international publications. They should have demonstrated remarkable ability in leading research groups, as well as experience in conducting/coordinating international projects.

Preference will be given to candidates performing research at the intersection between algorithms, theory and applications, and who are active in one or more of the following fields: analysis and modeling of massive data structures; graph theory and random structures; analysis and modeling of complex networks; machine learning; data mining; parallel and distributed computation.

Submit your confidential expression of interest at: http://www.imtlucca.it/faculty/positions/professors_positions/2011/application.php

Deadline is May 15th 2012.

Visit the Institute on YouTube (http://www.youtube.com/watch?v=q4gE-_2RrB8).

Nicolaas Govert de Bruijn (1918-2012)

I recently heard from MohammadReza Mousavi that Nicolaas Govert de Bruijn passed away on the 17th of February. In his long and productive life, de Bruijn gave contributions to several areas of mathematics and to theoretical computer science. Examples of his contributions are the De Bruijn sequence, De Bruijn's theorem, the De Bruijn–Erdős theorem in graph theory, the De Bruijn notation for terms in the λ calculus and his pioneering work on the project Automath, which was aimed at designing a language for expressing complete mathematical theories in such a way that a computer can verify the correctness of proofs in those theories. (Automath can be seen as the predecessor of type theoretical proof assistants such as the well known Nuprl and Coq.)

To celebrate de Bruijn's 90th birthday, TU/e organized a festive event.  Quoting from the web site for that event:

A number of colleagues, friends and admirers of Dick de Bruijn, from all over the world, wrote a personal letter as a birthday present for his 90th birthday, on July 9, 2008. The collection of these letters can be downloaded here.

Dick de Bruijn's lecture at the day of the symposium has been recorded on film. This film can be seen via this link.

Addendum: One of the letters in the above-mentioned collection is from Donald Knuth. In the letter, Knuth says that de Brujin coined the word "multiset" in a letter addressed to him from 1968. Knuth's letter also mentions the work of three of my former colleagues and ICE-TCS members: Anders Claesson, Mark Dukes and Sergey Kitaev.

ERC Advanced Investigator Grant to Dale Miller

Even though this is not really news any more, I am happy to report that  Dale Miller has been awarded one of the prestigious Advanced Investigators Grants by the ERC for the project ProofCert: Broad Spectrum Proof Certificates. This is a 2.2 million euro grant (about 3 million USD) for the five years 2012-2016. A news item pertaining to this award is here and the list of all awards for 2011 is available from this link.

The following excerpt is taken from the proposal’s abstract.

The ProofCert proposal aims at building a foundation that will allow a broad spectrum of formal methods—ranging from automatic model checkers to interactive theorem provers—to work together to establish formal properties of computer systems. This project starts with a wonderful gift to us from decades of work by logicians and proof theorist: their efforts on logic and proof has given us a universally accepted means of communicating proofs between people and computer systems. Logic can be used to state desirable security and correctness properties of software and hardware systems and proofs are uncontroversial evidence that statements are, in fact, true. The current state-of-the-art of formal methods used in academics and industry shows, however, that the notion of logic and proof is severely fractured: there is little or no communication between any two such systems. Thus any efforts on computer system correctness is needlessly repeated many time in the many different systems: sometimes this work is even redone when a given prover is upgraded. In ProofCert, we will build on the bedrock of decades of research into logic and proof theory the notion of proof certificates. Such certificates will allow for a complete reshaping of the way that formal methods are employed.

More technical details are available from the project's web page.

It is good to see that the ERC is actively supporting researchers of Dale's calibre in carrying out this kind of work. I look forward to seeing the outcome of this five-year project.

First Alan Turing Year event at Reykjavík University

Last Thursday, I kicked off  the Alan Turing Year at Reykjavik University  by delivering a talk for the general public entitled Alan Turing: The Father of Computer Science (organized jointly by ICE-TCS , the School of Computer Science at Reykjavik University and the Icelandic Mathematical Society).  In case anyone is interested, the audio of the talk, with the accompanying slides, is here in .avi format.

We plan to record all the talks in the series and to make them available on line here. 

It is not easy to give a talk for a general audience. In enjoyed the experience, but I was mightily relieved when the talk was over :-)

The Alan Turing Year at Reykjavik University is part of the Alan Turing Year, a centenary celebration of the life and work of Alan Turing.

What is a good research environment?

On January 27, I will be giving a ten-minute presentation at a town-hall meeting that will take place at Reykjavik University on the theme "What is a good research environment?". I roughly know what I am going to say, but I am curious to hear what would be the items on my readers' wish list when they think about a good research environment.

• What do you look for in a research environment you would be happy to work in? 
• What are the best aspects of your current research environment?
• What would you improve in your current research environment?

Two PhD fellowships at Reykjavík University in Design of Ad-Hoc Wireless Networks

I am very happy to post the following announcement of two Ph.D. fellowships on behalf of my colleague, and work-space neighbour, Magnús M. Halldórsson. I trust that it will be of interest to some of the readers of this blog and/or their students. The project "Design of Ad-Hoc Wireless Networks", which has Magnus as PI and sees the participation of ICE-TCS members Pradipta Mitra, Eyjólfur Ásgeirsson, Henning Úlfarsson and Ymir Vigfusson, has just been awarded a three-year excellence grant  by The Icelandic Research Fund.



Design of Ad-Hoc Wireless Networks

School of Computer Science, Reykjavik University

Two Ph.D. fellowships



Applications are invited for two Ph.D. fellowships at the School of Computer Science (SCS), Reykjavik University. The positions are part of a three-year research project funded by a grant-of-excellence by the Icelandic Research Fund, under the direction of Magnús M. Halldórsson.

Aim of the project

The aim of this project is to elucidate fundamental properties of wireless networks, broadly construed. Our focus is on general provable properties that hold for arbitrary configurations and are independent of situation-specific characteristics. We explore realistic models of interference, with the aim of bridging some of the gap between theoretical and applied research. We will also investigate practical protocols to disseminate information in general networks.



Some of the aspects of the projects include:

· Spectrum management, including game theory and spectrum auctions, and cognitive radio.

· Analysis of increasingly realistic models of wireless communication, including shadowing and obstacles, mobility, and network coding.

· Installation of a comprehensive wireless testbed, and the implementation of empirical confirmation studies.

· Resolution of fundamental open questions on wireless scheduling and capacity, and the design of communication primitives.

· Creating and evaluating protocols for information dissemination in combined wired and wireless networks.

· Devising practical systems and implementing applications for general networks.



The mode of operation of the project is three-pronged:

· Designing and implementing systems and kernel primitives.

· Conducting empirical studies in a wireless testbed, along with simulations studies.

· Designing and analysing algorithms with provable performance bounds.





Research environment

The research group consists of faculty members from three schools at Reykjavik University and collaborators at TU Aachen and ETH Zurich. The group includes Ýmir Vigfússon, Henning Úlfarsson and Pradipta Mitra (SCS), Eyjólfur Ásgeirsson (School of Science and Engineering) and Sverrir Ólafsson (School of Business and School of Science and Engineering). The project director is Magnús M. Halldórsson (SCS). Our primary collaborators are Berthold Vöcking (TU Aachen) and Roger Wattenhofer (ETH Zurich); we also collaborate with other world-class researchers in Europe, N-America, and Asia. The research group website is http://alnet.ru.is/sinr.html.


The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). ICE-TCS has currently 14 permanent members, five postdoctoral researchers and three Ph.D. students. For more information about ICE-TCS, its members and its activities, see http://www.icetcs.ru.is/.

Qualification requirements

Applicants for the Ph.D. fellowships should have a MSc degree in Computer Science, or closely related fields, and have a solid background in the analysis of algorithms and a good understanding of networking. One of the studentships is expected to be systems-oriented, for which an experience with systems design and implementation is essential. The other will be focused on algorithmic analysis, for which mathematical competence is crucial.

Remuneration

Each Ph.D position provides a stipend of 250,000 ISK (roughly 1600€[1]) per month before taxes, for three years, starting as early as possible and no later than September 2012.

Application details

By Friday, 15 February 2012, interested applicants should send their CV, including a list of publications where applicable, as a PDF document to mmh@ru.is, together with a transcript of their academic record, a 1-2 page statement outlining their suitability for the project and the names of two referees who can comment on the research potential of the candidate.

We will start reviewing applications as soon as they arrive, and will continue to accept applications until the positions are filled. However, we strongly encourage interested applicants to send in their applications as soon as possible.

About the School of Computer Science at Reykjavik University

The School of Computer Science at RU (http://en.ru.is/CS) has approximately 440 students at the undergraduate, masters and doctorate levels. The School is home to several strong research groups and the main research areas are algorithmics, artificial intelligence, combinatorics, concurrency theory, databases, human-computer interaction, natural language processing, engineering software systems, theoretical computer science and virtual environments.

The School of Computer Science at Reykjavik University has ties with several leading foreign universities, facilitating collaboration, as well as faculty and student exchanges. In particular, the School has a joint M.Sc. degree in Computer Science with the University of Camerino, Italy, and joint Ph.D. degree programs with KTH, Stockholm, Sweden, and Eindhoven University of Technology, Holland.

Information about Ph.D. studies at the School of Computer Science is available at
http://en.ru.is/departments/school-of-computer-science/ph.d-studies/



[1] Up-to-date Exchange Rate can be obtained from http://sedlabanki.is/?PageID=183

Merry Christmas, if it comes.....

From xkcd. My daughter would not be very happy with this Zeno behaviour :-)

Accepted papers for FOSSACS 2012

The list of accepted papers for FOSSACS 2012 is now available. The competition for the available slots was very hard, and several deserving submissions could not be selected for the conference.

On a personal note, the more I serve on PCs for competitive conferences, the more I have the feeling that the quality of the competition is increasing. The same holds true for grant applications, job applications, promotions and just about any other aspect of academic life.

News from the LICS Community

Here is some news I just discovered by looking at the web page for LICS 2012.

Highlights and changes for LICS 2012

1. Starting 2012, LICS is jointly organized by ACM and IEEE, and is cosponsored by ACM SIGACT and the IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing.
2. In response to concerns about LICS becoming overly selective with a too-narrow technical focus, the program committee will employ a merit-based selection with no a priori limit on the number of accepted papers.
3. LICS 2012 will continue the tradition of pre-conference tutorials that was initiated in 2011. This year, Jan Willem Klop will give a tutorial on term rewriting systems and Andre Platzer will give a tutorial on logics of dynamical systems.
4. Special Events and Invited Lectures: There will be an invited lecture by Robert J. Aumann, winner of the 2005 Nobel Prize in Economic Sciences, and a plenary session in honor of Alan Turing on the occasion of his centenary, with talks by Robert L. Constable, E. Allen Emerson (co-winner of 2008 A. M. Turing Award), Joan Feigenbaum, and Leonid Levin. 

These are very interesting developments for the LICS community, some of which should be of interest for the TCS community as a whole.

Development A above paves the way to the formation of an ACM Special Interest Group on Logic in CS, say a SIGLOG, about which I have heard reports in private conversations with key players in the LICS community. Such a special interest group would play an important role in the development of volume B TCS research in North America.

Development B is most interesting and might be a watershed event, if it pans out. LICS plays the role of FOCS/STOC for the volume B TCS community and I believe that all of TCS will be interested in observing the outcome of the LICS 2012 experiment. Typically, the quality of an average LICS submission is very high and this new policy might encourage even more submissions to the conference than usual. How will the PC handle these submissions? Will the conference move to parallel sessions? Will this development decrease the value of the "LICS currency"? Will other conferences follow the lead of LICS, if the experiment "succeeds"?

Time will tell. In any event, this is a courageous step taken by the LICS conference and I look forward to seeing how it will affect the conference and the LICS/TCS community.

Last, but not least, items C and D above look exciting. I have heard from several sources that the tutorials at LICS 2011 were a resounding success. (See here, here and here for the slides used by Prakash Panangaden, one of my favourite speakers, in his tutorial on Semantics. Albert Atserias gave a tutorial on Finite Model Theory.)

Standards for promotions

My department is developing its strategy for the next five years. As part of this strategy work, we are working on a "promotion strategy" and we are discussing standards for promotion to associate and full professor positions. Needless to say, there is a wide array of opinions amongst my colleagues on this point. In order to obtain a broad survey of current best practices, let me ask any reader out there:

• What does it typically take to be promoted to associate and full professorships at your institution? 
• What role does teaching performance play in such decisions? And how is it measured?
• What are the incentives to undergo a promotion process, apart from the obvious ones like tenure and possibly higher wages?

Thanks in advance!

Dr. Cimini, I presume

Last Friday, Matteo Cimini successfully defended his PhD thesis entitled Contributions to the Meta-theory of Structural Operational Semantics. Congratulations to Dr. Cimini! I expect that his thesis will be available on line soon, but, for the moment, you can read some of the papers that form the bulk of that tome.

A PhD is not enough, however. I wish Matteo the best of luck for his future career. 

EATCS ballot on the future of the publication of the ICALP proceedings

Today, the European Association for Theoretical Computer Science started a ballot on the future of the publication of the proceedings of ICALP. This is a very important decision for the EATCS, and for the ICALP community in general. As chairman of the publication committee of the EATCS, I urge all the members of the TCS community who have a right to vote as members of the EATCS, to give this matter serious thought and exercise their right to express an opinion on whether future ICALP proceedings should be published with Springer or with LIPIcs. Note that if you attended ICALP 2011, ESA 2011 or MFCS 2011, you have the right to vote since your registration fee probably included a one-year membership of the EATCS.

Note also that the result of the  ballot will only take effect if at least 25 % of the EATCS members participate. Otherwise, the proposal of the EATCS council to recommend to the EATCS membership to go along with Springer for the next four years will take effect automatically.

The ballot on the future of the publication of the ICALP proceedings, as well as all the supporting documentation,  can be found here.  I do hope that you will take time to consider this matter and vote as soon as possible.

Assistant Professor position in Modelling and Analysis of Concurrent Systems at IMT Lucca (deadline October 31st)

Perhaps this announcement will be of interest to some of the readers of this blog. IMT Lucca is an exciting place and there will definitely be some competition for the position. 


Addendum dated 7 October: This video issued by IMT Lucca gives an enticing introduction to that academic institution. Do have a look, if you are interested in applying for this position.

The IMT Institute for Advanced Studies Lucca invites applications for an Assistant Professor position in the areas of foundations and formal specification of concurrent (distributed, mobile, autonomic) systems; quantitative and qualitative modelling and analysis of concurrent systems and design and development of software tools to support their formal analysis; applications to socio economic systems.

IMT Lucca (http://www.imtlucca.it) is a public international Graduate School and Institute of Technology that acts as a research university with the aim of forming human capital in disciplines characterized by their high potential for concrete applications. IMT strives to reach the fusion of theoretical comprehension and practical relevance. 

The Assistant Professor will be a part of the Research Unit "System Modelling and Analysis" (SysMA, http://sysma.lab.imtlucca.it/) in the Computer Science and Applications area of the Institute, and will perform research activities, tutorship and mentoring of Ph.D. students, limited teaching of graduate courses and participation in the development of the research activities of the Institute. 

Appointment compensation packages will depend on the candidates and their records of accomplishment, but are competitive on an international level. Applicants must be able to teach graduate courses in English; knowledge of Italian is not required.

The deadline for application is October 31st, 2011 12:00 pm CET.

Interested candidates must apply before the deadline by filling in the online application form at http://www.imtlucca.it/faculty/positions under "Junior Faculty Recruitment Program". They will also be asked to submit a CV, a research paper (published or working) and the name and contact details of three referees.

For further information about the position, applicants can refer to 

http://www.imtlucca.it/faculty/positions/junior_faculty_recruitment_program.php#modelling_concurrent_systems

or can contact either Rocco De Nicola or Sara Olson: researchers.opening@imtlucca.it.