Programme of colloquia with abstracts for the Autumn 2009 semester

29 September 2009

Dr Paul Leyland, CEPIA Technologies, United Kingdom

RSA Security and Integer Factorisation: The Thirty Years’ War from 1990 to 2020

Abstract: The RSA public-key cryptosystem was invented in 1977. It came into widespread use about ten years later. The security of RSA depends critically on integer factorisation being a difficult problem in practice. Those who factor integers have been working very hard to reduce the practical difficulty of factoring, not always to the approval of those who use RSA to protect valuable information. This talk covers the history of the tension between these two communities over the last twenty years, and suggests that a resolution should be forthcoming in the next decade.

6 October 2009

RNDr. Radka Svobodová Vařeková, Ph.D., National Centre for Biomolecular Research, Siemens Corporate Technology & Research

R&D projects and their implementation in companies

Abstract: The field of industrial research and innovation projects is currently a much-discussed topic. One reason for this is the increase in subsidy support for R&D projects compared with previous years. Another is the growing need for innovation, which is gradually becoming an essential prerequisite for companies to maintain their competitiveness. An example of this is the activities within the forthcoming CERIT project. In my lecture, I will focus specifically on industrial research and practical experience in this field. First, I will describe the motivation behind launching a research project and the project’s initiation phase. I will then outline my experiences of implementing grant-funded projects within the company and of collaborating with universities. In the second part of the lecture, I will describe examples of two research projects and provide information about them.

13 October 2009

Doc. Ing. Lukáš Sekanina, Ph.D., FIT VUT, Brno

Synthesis of polymorphic logic networks

Abstract: This lecture will introduce the field of polymorphic electronics, which is based on the existence of so-called polymorphic gates. It will describe a polymorphic NAND/NOR gate developed at the Faculty of Information Technology, Brno University of Technology, which changes its logical function depending on the supply voltage level. The main part of the lecture will be devoted to the problem of synthesising polymorphic logic networks. Synthesis algorithms based on both conventional methods and an evolutionary approach will be discussed. Finally, selected applications of polymorphic electronics will be demonstrated.

20 October 2009

Dr Sang-il Oum, KAIST, Daejeon, Korea

Maximum number of complete subgraphs in a given graph

Abstract: A clique in a graph is a set of vertices that are all pairwise adjacent. We are interested in the maximum possible number of cliques in a graph. In general, a graph with n vertices can have at most 2^n cliques, obviously. We will show that if we restrict to a graph with no K_r- minor, then such a graph can have at most O(n) cliques. Indeed, this result is not new; several researchers have already discovered the same bound. The previous best bound was 2^(c r sqrt(log r)) n. We have improved this to 2^(c log log r) n. We also examined other classes of graphs. As a corollary, we obtained a hypergraph generalisation of the theorem by Thomason and Kostochka (independently) concerning the maximum number of edges in a graph with no K_r minor. This talk is based on joint work with Fedor Fomin and Dimitrios Thilikos on the relationship between tree-width and rank- width for planar graphs and H-minor-free graphs.

27 October 2009

Doc. Damas Gruska, Ph.D., Faculty of Mathematics, Physics and Informatics, KU, Bratislava

Information Flow and the Security of Computer Systems

Abstract: The issue of security in hardware and software systems has several dimensions. These range from the design of algorithms that are provably difficult to break, through implementation issues, to maintenance and the human factor. A specific security risk is the existence of information flow between private and public data or actions. Attacks exploiting such information flow have proven to be exceptionally effective and can be used to compromise systems employing algorithms and techniques otherwise considered highly robust.

In this lecture, we will focus on the fundamental principles of security for hardware and software systems based on the absence of information flow. We will present several formalisations of information flow for different types of attackers (varying in the level of detail with which they can observe or communicate with the targeted system) and for different security requirements. We will address both qualitative and quantitative expressions of information flow.

The first part of the lecture will be devoted to a broader view of the overall problem and the basic approaches to solving it, whilst in the second part of the lecture we will present several proposals for new solutions to the problems.

3 November 2009

Prof. Wolfgang Slany, Graz University of Technology

Why game programming skills are important for children and what can be done about it

Abstract: Computer games with an explicit educational aim are well known for usually being rather unpopular amongst the intended audience :-). On the other hand, Neal Stephenson’s science-fiction classic “Snow Crash” is said to have been one of the inspirations for the creation of “Second Life", a highly successful massive multi-player online game-like thing that sets itself apart by allowing players, amongst other things and motivated by the book’s story, to write computer programmes that can be executed within the environment. Stephenson’s other book, which is particularly popular amongst women, *The Diamond Age, or A Young Lady’s Illustrated Primer — A Propaedeutic Enchiridion in which is told the Tale of Princess Nell and her various Friends, Kin, Associates, &c.” (currently 346 Amazon customer reviews) follows the upbringing of a girl from a very young age to adulthood, one of the highlights being the teaching of computer science to the teenage girl. This book notably served as one of the inspirations for the ongoing One Laptop Per Child (XO-OLPC) movement, which has so far distributed roughly 1.5 million rugged, low-power subnotebook computers with mobile ad-hoc networking capabilities to young children, mostly in the developing world. One piece of software pre-installed on these laptops is a programming environment for children aged 8 and above. Scratch has been developed as part of the Lifelong Kindergarten project at the MIT Media Lab. To date, more than 550,000 programmes have been uploaded by more than 83,000 contributors (mostly, though not exclusively, children, out of more than 367,000 registered members). Harvard University is even using Scratch to introduce programming to its first-year students! Most of the programmes written are games. Variants allow users to programme multi-player network games and to programme for Second Life, and a version for mobile phones is currently being developed.

I will talk about my own experiences in relation to the above.

10 November 2009

Doc. RNDr. Václav Matyáš, M.Sc., Ph.D., RNDr. Marek Kumpošt, Ph.D., FIMU, Brno

How much is privacy worth?

Abstract: This lecture presents the results of two experiments (from 2006 and 2009), the aim of which was to determine how much value people place on their private information. To ensure that the data obtained was as little influenced as possible by directly asking people the price they would pay for providing private information, both experiments were conducted in a way that concealed the true intention. In the first experiment, we investigated the price people would pay for information about their current location — the location would have been determined using a mobile phone. In the second case, we focused on the price people would pay for information relating to the use of tools for online communication (sending emails or using instant messaging) — information on the use of these types of online communication would be collected using specialised software developed by us. In both cases, we asked participants what financial compensation they would require if they were to take part in the proposed experiment. Both studies were carried out in collaboration with our international partners (universities) as part of the FIDIS (Future of Identity in the Information Society) project.

24 November 2009

Jan Obdržálek, MSc, PhD, FIMU, Brno

Parameterised complexity, or the Hamiltonian cycle in linear time

Abstract: For many years, a well-established pattern has applied to computational complexity: If we can prove that a particular problem is NP-complete, there is no need to concern ourselves further with its complexity – a deterministic computation then runs in time that is exponential in the size of the input. Further research then turned towards heuristics, approximation and stochastic algorithms. However, it gradually became apparent that not all ‘hard’ problems are hard for the same reasons. In particular, it is often possible to find linear/polynomial algorithms for NP-complete problems if we restrict the set of input instances on the basis of some fixed parameter k. This fixed parameter may be either the size of the object being sought (e.g. find a vertex cover of size k), or the ‘structural complexity’ of the input (e.g. graphs with tree-width k). The study of parameterised problems is the subject of the theory of parameterised complexity.

In this lecture, we will first focus on the basic concepts of parameterised complexity. We shall then present linear/polynomial algorithms for NP-complete problems on tree-like graphs (where the parameter k measures this similarity) and, finally, we shall present some new results for problems on directed graphs.

1 December 2009

Prof. RNDr. Luděk Kučera, DrSc., KAM, Faculty of Mathematics and Physics, Charles University, Prague

ALGOVIZE, or a stroll through the landscape of algorithms

Abstract: The aim of this lecture is to introduce Algovize, a collection of applets created by the author for his lecture ‘Algorithms and Data Structures’ at the Faculty of Mathematics and Physics, Charles University. The philosophy behind Algovize is not merely to create animations of algorithms – of which there are many available on the internet, and which merely show what happens during the calculation – but, above all, to use visual means to explain the underlying algorithmic idea – in other words, to visualise why the calculation is performed in this way. Looking back, it is possible to identify a number of approaches that can lead to this goal, such as visualising algorithms in such a way that invariants from correctness and complexity proofs are made clear, animations of mathematical proofs (e.g. existence proofs are often algorithms that can be animated), emphasising logically important facts through graphical means, and so on. The focus of algorithm visualisation is thus shifting away from software productivity, with the cognitive and psychological aspects of scientific activity and teaching in the field of computer science becoming paramount.

8 December 2009

Prof. RNDr. Jiří Wiedermann, DrSc., Institute of Informatics, Czech Academy of Sciences

Amorphous Computing Systems

Abstract: Under various guises, the concept of amorphous computing systems first emerged in science fiction literature, cf. the 1957 novel *The Black Cloud* by the astrophysicist Sir Fred Hoyle; or the 1999 Hugo Award-winning novel *A Deepness in the Sky* by the mathematician and computer scientist Vernor Vinge, in which advanced amorphous computing systems appear in the form of ‘localisers’. Contemporary engineering efforts to construct such systems are exemplified, for instance, by the 2001 ‘smart dust’ project led by K.S.J. Pister (University of California). Real bacteria provide an example of such systems in nature. From a computational perspective, amorphous computing systems differ from classical ones in almost every respect: they consist of a set of simple processors or robots capable of communicating wirelessly over a limited distance. The processors are randomly distributed within a closed area or volume; in some applications they can move, either actively or passively (e.g., in a bloodstream). All processors are identical; they do not share a global clock and do not have unique identifiers. How can such systems compute? Do such systems possess universal computing power? Are finite automata suitable for such a task? We present a generic model of such systems. The processors are modelled as timed probabilistic finite-state automata. In a ‘macro-sized’ model, the automata communicate via a single-channel radio; in a ‘nano-sized’ model, via molecular communication. We outline the main ideas leading to the design of probabilistic communication protocols and to the emergence of communication networks, and highlight some open problems. Although families of all resulting systems possess universal computing power, it is not clear whether some of them can be simulated by a single universal machine.

15 December 2009

Dr József Kovács, MTA SZTAKI, Budapest

SZTAKI Desktop Grid in the CancerGrid and EDGeS EU projects

Abstract: SZTAKI Desktop Grid (SZDG) is an extension of BOINC designed to make it more flexible, versatile and scalable. MTA SZTAKI has developed various tools to facilitate the use of BOINC from several perspectives, such as application development, work unit generation, project management, security and so on. The talk will provide an overview of SZDG and detail the various extensions utilised in the CancerGrid and EDGeS EU projects. CancerGrid aims to provide an infrastructure to help chemists develop new compound libraries with a high content of anti-cancer leads. The CancerGrid infrastructure consists of the gUSE scientific gateway, a compound database, several workflow applications based on various chemoinformatics tools and a private SZDG that executes the different parts of the workflows. The EDGeS project aims to resolve interoperability issues between service grids (SG) and desktop grids (DG) by developing a gateway called 3Gbridge. Based on this bridge, a combined SG-DG infrastructure has been built and is being operated to run a wide range of different applications ported during the project.