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