Slides of the talk. [pdf]
Abstract: A new approach to private information retrieving protocol construction is proposed. Using proposed approach a new PIR scheme is described. All significant parameters of proposed scheme are analyzed and compared to existing solutions [3, 4]. As the result of the comparison, the following conclusions can be made:
References:
Slides of the talk. [pdf]
Abstract: A cellular automaton on a group is a transformation of configurations (i.e., functions from the group to a finite alphabet) which is continuous in the product topology and commutes with translations. Such features allow a finitary local description of the global dynamics: how much the latter's properties are linked to those of the underlying group, is a topic of great interest.
It is well known from group theory that a subgroup of finite index of Zd, the group of d-tuples of integers, is isomorphic to Zd: which allows to define normality of d-dimensional configurations analogously to normality of real numbers. In general, however, it is not so: for example, a subgroup of index 2 of the free group on two generators is free on three generators.
We introduce a definition of normality for configurations over arbitrary groups which, under suitable conditions, still ensures that the set of normal configurations has full measure. We then expand the result by Bartholdi about amenable groups being those where surjective cellular automata are measure-preserving, and prove that on every non-amenable group there exists a surjective cellular automaton such that the counterimage of a set of full measure is a null set.
(Joint work with Pierre Guillon and Jarkko Kari.)
Slides of the talk. [pptx]
Abstract: tba
(With contributions from Luciano Garcia-Bańuelos, Fabrizio Maggi and Massimiliano de Leoni.)
Slides of the talk. [pdf]
Abstract: Attribute grammars are an extension of context-free grammars with attributes and semantic equations. For attribute evaluation to be well-defined on all parse trees for all interpretations of attribute types and semantic functions, the grammar must be without attribute dependency cycles. As a step in developing a framework for attribute grammars in the Agda dependently typed programming language, we have formalized Knuth's algorithm for circularity checking of attribute dependencies. We have formalized positions and paths in parse trees and proved several structural properties about them. We have implemented a terminating circularity checking function and proved that it is sound and complete (if the check says yes, then one parse tree with a cycle of attribute dependencies is exhibited; if some such parse tree exists, then the check says yes).
(Joint work with Tarmo Uustalu.)
Slides of the talk. [pdf]
Abstract: Ordinary functional programming deals with values, which can be duplicated and discarded at will. Functional programming with linear types, on the other hand, deals with stateful objects, which can neither be duplicated nor discarded. Both paradigms can be combined within a single language, and their interaction can be modeled by a symmetric lax monoidal adjunction.
In this talk, I show that a similar situation holds regarding functional reactive programming (FRP). We can combine ordinary functional programming and FRP and model their interaction by a symmetric lax monoidal adjunction as well. An analogous construction for linear types then leads to a variant of FRP that deals with mutable state and interacts naturally with ordinary FRP.
Slides of the talk. [pdf]
Abstract: Valiant's theory of #P-completeness and recent advances in parameterized complexity theory tell us that it is unlikely that polynomial-time algorithms exist for many natural subgraph counting problems on graphs. A canonical such problem is the problem of counting the perfect matchings in a graph, and the related matrix permanent problem. Yet, the last five years or so have seen a fair number of improved exact and parameterized algorithms for subgraph counting. This talk will give an overview of advances in the area from two perspectives: (a) counting spanning subgraphs such as perfect matchings, and (b) counting small subgraphs such as cliques or paths parameterized by the number of vertices in the subgraph.
Slides of the talk. [pdf]
Abstract: The known security proofs for hash tree time-stamping assume collision-resistance (CR). An asymptotically optimally tight proof has the security loss formula t'/δ' ≈ 14 sqrt(C) (t/δ)1.5, where t'/δ' is the time-success ratio of a collision-finder, t/δ is the ratio of a back-dating adversary and C is the size of the hash tree created in every time unit. Practical schemes use 256-bit hash functions that are just 2128-secure because of the birthday bound. For having a 280-secure time-stamping scheme, we have C ≤ 103 that is insufficient for global scale solutions. Due to tightness bounds for CR, practically relevant security proofs must use assumptions stronger than CR. We show that under the random oracle (RO) assumption, the security loss is independent of C. We establish a linear-preserving security reduction under the Pre-Image Awareness (PrA) assumption. We present a new slightly stronger assumption SPrA that leads to much tighter proofs. We also show that bounds on C are necessary -- based on any PrA/SPrA function, we construct a PrA/SPrA function that is insecure for unbounded time-stamping.
(Joint work with Ahto Buldas.)
Abstract: Secure multiparty computation (MPC) allows multiple parties to evaluate functions without disclosing the private inputs. Secure comparisons (testing equality and greater-than) are important primitives required by many MPC applications. We propose two equality tests for l-bit values with O(1) online communication that require O(l) respectively O(κ) total work, where κ is a correctness parameter.
Combining these with ideas of Toft, PKC '11, we obtain (i) a greater-than protocol with sublinear online complexity in the arithmetic black-box model (O(c) rounds and O(c l1/c) work online, with c=log l resulting in logarithmic online work). In difference to Toft, we do not assume two mutually incorruptible parties, but O(l) offline work is required, and (ii) two greater-than protocols with the same online complexity as the above, but with overall complexity reduced to O(log l(κ+loglog l)) and O(c l1/c(κ+log l)) ; these require two mutually incorruptible parties, but are highly competitive with respect to online complexity when compared to existing protocols.
(Joint work with Tomas Toft.)
Slides of the talk. [pdf]
Abstract: There are many problems whose solutions take the form of patterns that may be expressed using grammars (e.g., speech recognition, text processing, genetic sequencing, programming language development, etc.). Construction of these grammars is usually carried out by computer scientists working with domain experts. Grammar inference (GI) is the process of learning a grammar from examples, either positive (i.e., the pattern should be recognized by the grammar) and/or negative (i.e., the pattern should not be recognized by the grammar). This talk will present the application of grammar inference to software language engineering, including recovery of domain-specific language (DSL) specifications from example DSL programs and recovery of a meta-model from instance models which have evolved independently of the original meta-model.
Slides of the talk. [pdf]
Abstract: In this work we study the security definitions and methods for transformation-based outsourcing of linear programming. The recent attacks have shown the deficiencies of existing security definitions; thus we propose a stronger, indistinguishability-based definition of security of problem transformations that is very similar to IND-CPA security of encryption systems. We will study the realizability of this definition for linear programming and find that barring radically new ideas, there cannot exist transformations that are secure information-theoretically or even computationally. We conclude that for solving linear programming problems in privacy-preserving manner, cryptographic methods for securely implementing Simplex or some other linear programming solving algorithm are the only viable approach.
Slides of the talk. [pdf]
Abstract: The min-rank of a digraph was shown by Bar-Yossef et al. to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are studied. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete.
By contrast, the same question for graphs can be answered in polynomial time.
(Joint work with Son Hoang Dau and Yeow Meng Chee.)
Slides of the talk. [pdf]
Abstract: Distributed graph algorithms solve problems that are related to the structure of an unknown communication graph. Each node of the graph is a computer. Initially, each node is only aware of the edges incident to it, but it can learn more about the structure of the graph by exchanging messages with its neighbours. Eventually, each node has to stop and produce a local output. The local outputs constitute a solution of a graph problem: for example, if we study the vertex cover problem, each node produces one bit of local output, indicating whether it is part of the vertex cover.
We define that the running time of a distributed algorithm is the number of communication rounds until all nodes have stopped. The key question is which graph problems can be solved fast with a distributed algorithm. Our recent work has settled many open questions in this area; I will focus on two examples:
(1) There is a deterministic distributed algorithm that finds a maximal fractional matching in time O(Δ), where Δ is the maximum degree of the graph. We show that this is optimal: there is no such algorithm with running time o(Δ).
(2) On bipartite graphs, maximum matching and minimum vertex cover are dual problems; the size of a maximum matching equals the size of a minimum vertex cover. It is known that maximum matching on low-degree bipartite graphs can be approximated arbitrarily well with a very fast distributed algorithm, and it would be natural to expect that the same holds for the dual problem as well. However, we show that this is not the case: even if we study bipartite graphs of maximum degree 3, finding a 1.01-approximation of a minimum vertex cover requires at least logarithmic time.
(Joint work with Mika Göös and Juho Hirvonen.)
Slides of the talk. [pdf]
Abstract: Atoms of regular languages were introduced in 2011. An atom of a regular language L with n (left) quotients is a non-empty intersection of uncomplemented or complemented quotients of L, where each of the n quotients appears in a term of the intersection. Every regular language defines a unique nondeterministic finite automaton (NFA), átomaton, whose states are the atoms of the language.
In this talk we present a recent generalization of atoms, introducing partial atoms of an NFA N as non-empty intersections of complemented or uncomplemented right languages of the states of N. We define an NFA corresponding to N, partial átomaton, that uses partial atoms of N as its states. We present some properties of partial atoms and partial átomata, including their relationships to the atoms and the átomaton of the language.
(Joint work with Janusz Brzozowski.)
Slides of the talk. [pptx]
Abstract: Using so-called random oracles (an idealization of hash functions), there are very efficient constructions for zero-knowledge proofs, needing only a single message. In particular, these give us also efficient signature schemes.
Unfortunately, so far very little progress has been made to show that these protocols are also secure against adversaries with quantum computers. We show why this is the case: the constructions cannot, in general, be secure against quantum adversaries! We also present modified constructions that circumvent these impossibilities.
Caveat: This is work in progress, not all proofs exist yet, all may be wrong.
(Joint work with Andris Ambainis and Ansis Rosmanis.)
Slides of the talk. [pdf]
Abstract: We introduce update monads as a generalization of state monads. Update monads are compatible compositions of reader and writer monads given by a set and a monoid. Distributive laws between such monads are given by monoid actions.
We also discuss a dependently typed generalization of update monads. Unlike simple update monads, those cannot be factored into a reader and writer monad.
Dependently typed update monads arise from cointerpreting directed containers, by which we mean interpreting the opposite of the category directed containers into the category of set functors.
(Joint work with Danel Ahman.)
Slides of the talk. [pdf]
Abstract: The delay monad was introduced by Capretta in order to give a good representation of general recursive functions in type theory. It constitutes a constructive alternative to the maybe monad: every element of Delay X is a possibly infinite computation that returns a value from X. Restriction categories are an abstract axiomatic framework by Cockett and Lack for reasoning about partiality of functions. We show that the Kleisli category of the delay monad is a restriction category with certain additional structure, namely a Cartesian restriction category with meets, joins and iteration.
(Joint work with James Chapman and Tarmo Uustalu.)