TCSA Day 2010

• Theoretical Computer Science Amsterdam (TCSA) Day

• Friday October 29, 2010
  10:00-17:00
  at CWI, Science Park 123, 1098 XG Amsterdam. Directions to CWI
  in the Euler-room (=room Z009); take the entrance to the left of the revolving door which is CWI's main entrance

Schedule

• 09:30 coffee
• 10:00-10:45 Jan Rutten (CWI): Behavioural differential equations -- a concrete framework for coinductive definitions
• 10:45-11:15 coffee
• 11:15-12:00 Pieter Adriaans (UvA): Facticity and meaningful information
• 12:00-12:45 Ulle Endriss (UvA): Complexity of judgment aggregation
• 12:45-14:00 lunch (not organised)
• 14:00-14:45 Harry Buhrman (CWI): Position-based quantum cryptography: impossibility and constructions
• 14:45-15:30 Piet Rodenburg (UvA): Structuring partial algebras
• 15:30-16:00 tea
• 16:00-16:45 Jan Willem Klop (VU): Defining, transforming and comparing infinite streams

Abstracts

• 10:00-10:45 Jan Rutten (CWI): Behavioural differential equations -- a concrete framework for coinductive definitions
  
  Abstract: Coinduction has come to play an ever more important role in theoretical computer science, for the specification of and reasoning about infinite data structures and, more generally, automata with infinite behaviour. In this talk, we shall focus on a recently introduced formalism for coinductive definitions: behavioural differential equations, with which one specifies behaviour in terms of initial outputs and behavioural derivatives (next state operators). Our emphasis will be on the elementary calculus of streams (infinite sequences), of which we shall discuss the basic theory, developed in close analogy to mathematical analysis. As an application area, we will discuss a coinductive calculus of periodic stream operators (joint work with Milad Niqui (CWI)). Using this calculus, we will give a new and transparent proof of Moessner's theorem using coinduction. This theorem (from 1951 - 1952) gives a suprising construction for the stream of powers n^k of the natural numbers (such as 1,8,27,64, ... for k=3) out of the stream of natural numbers by an alternating process of stream sampling and taking partial sums.


• 11:15-12:00 Pieter Adriaans (UvA): Facticity and meaningful information
  
  Abstract: In my introductory course in learning theory I often make the remark that the most informative television broadcast is pure white noise. Yet we do not consider such a channel to be very interesting. So the notion of meaningful information or 'interestingness' is not well covered by the standard definitions. The well-known formal definitions of the notion of information (notably Kolmogorov complexity and Shannon Information) all have the counter intuitive consequence that datasets with the highest entropy contain a maximal amount of information. A number of authors have made useful proposals in the past decennia to improve this situation. To name a few: Sophistication (Koppel 1988, Anthunes, Fortnow 2007), Logical Depth (Bennet 1988), effective complexity (Gell-Mann, Lloyd 2003), Meaningful Information (Vitanyi 2003), Self-dissimilarity (Wolpert, Mcready 2007), Computational Depth (Antunes et al. 2006). In a number of recent publications and lectures I have proposed the notion of facticty (Adriaans 2009) to model meaningful information. Basically it is the length of the model code in the context of a variant of two-part code optimization in Kolmogorov complexity. In my lecture I argue that this is the right definition and I analyze some of the more puzzling consequences of this definition, notably the existence of factic processes that create meaningful information.


• 12:00-12:45 Ulle Endriss (UvA): Complexity of judgment aggregation
  
  Abstract: Aggregating the judgments of a group of agents regarding a set of interdependent propositions, expressed in propositional logic, can lead to inconsistent outcomes. This paradox of judgment aggregation has recently sparked a good deal of interest in Legal Theory, Philosophy, Economics, and Computer Science. I will start with a short introduction to judgment aggregation and then report on our ongoing work aimed at better understanding this problem domain from a computational point of view. Specifically, we have analysed the computational complexity of several problems that naturally arise in the context of judgment aggregation: computing a collective judgment, strategic manipulation, and deciding whether a given class of aggregation problems can be guaranteed not to lead to paradoxical outcomes. I will also explain how this work fits into the broader research agenda on Computational Social Choice (COMSOC) currently being pursued at the ILLC.
  This is joint work with Umberto Grandi and Daniele Porello.


• 14:00-14:45 Harry Buhrman (CWI): Position-based quantum cryptography: impossibility and constructions
  
  Abstract: We study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure position-verification is possible at all. That is, we show a generic attack that breaks any position-verification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.
  This is joint work with Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner


• 14:45-15:30 Piet Rodenburg (UvA): Structuring partial algebras
  
  Abstract: In Typability in Partial Applicative Structures (with I. Bethke; to appear in the Journal of Logic, Language and Information; preliminary version at arxiv/0901.0188 under the title Typability in partial groupoids) conditions are established under which an algebra with a single, partial, binary operation can be given a simple type structure. In this talk, I will consider the problem of adding type structure to partial algebras with more operations.


• 16:00-16:45 Jan Willem Klop (VU): Defining, transforming and comparing infinite streams
  
  Abstract: We discuss two topics in infinite sequences (or streams). The first topic is how to define streams in a uniform framework, that we call Pure Stream Format (PSF). Specifically we concentrate on proving well-definedness of such specifications - an issue known in computer science as productivity. We single out a restricted class of specifications, still expressive enough to encompass automatic streams, morphic streams, and more. For specifications in this restricted format we can automatically decide productivity. The second topic is concerned with an attempted classification of infinite streams, by means of finite state transducers (FSTs), leading to a notion of 'degree of stream' that is analogous to the well-known Turing degrees of unsolvability in mathematical logic. (In fact FSTs correspond to context expressions in PSF.) We mention initial results in the form of some elementary properties of this partial order of stream degrees, concluding with our favourite conjecture about the degree of the Thue-Morse sequence.
  This is joint work with Clemens Grabmayer (UU), Joerg Endrullis (VU) and Dimitri Hendriks (VU)