^May June – 2009 ^July

The problem of carrying out cryptographic computations when the participating parties are rational in a game-theoretic sense has recently gained much attention. One problem that has been studied considerably is that of rational secret sharing. In this setting, the aim is to construct a mechanism (protocol) so that parties behaving rationally have incentive to cooperate and provide their shares in the reconstruction phase, even if each party prefers to be the only one to learn the secret. Although this question was only recently asked by Halpern and Teague (STOC 2004), a number of works with beautiful ideas have been presented to solve this problem. However, they all have the property that the protocols constructed need to know the actual utility values of the parties (or at least a bound on them). This assumption is very problematic because the utilities of parties are not public knowledge. We ask whether this dependence on the actual utility values is really necessary and prove that in the basic setting, rational secret sharing cannot be achieved without it. On the positive side, we show that by somewhat relaxing the standard assumptions on the utility functions, it is possible to achieve utility independence. In addition to the above, observe that the known protocols for rational secret sharing that do not assume simultaneous channels all suffer from the problem that one of the parties can cause the others to output an incorrect value. (This problem arises when a party gains higher utility by having another output an incorrect value than by learning the secret itself; we argue that such a scenario is not at all unlikely.) We show that this problem is inherent in the non-simultaneous channels model, unless the actual values of the parties' utilities for this attack is known, in which case it is possible to prevent this from happening.

This is a joint work with Yehuda Lindell.

Predicting secondary structures of RNA molecules is a classic example of a biological problem which is solved via the usage of computational tools. The original algorithms for the RNA folding problem (dating back to the late 70's) solve it in O(n^3) time and O(n^2) space complexities (where n denotes the length of the input sequence, and can get up to several hundreds). While these complexities are reasonable for the processing of a single input, they are inadequate for modern analysis of genome-wide data, which may include several billions of input sequences. Recently, the running time was improved to O(nZ), where Z is a sparsity parameter that satisfies n < Z < n^2. In the talk, new results will be presented, which reduce the space complexity to O(Z), and the time complexity to O(LZ), where L is a sparsity parameter that satisfies L < n. The presented techniques extend to a family of RNA folding algorithms, which include more sophisticated problem variants with higher time and space complexities, as well as to algorithms from other fields, such as parsing sentences with a given probabilistic context free grammar.

The path packing problem for graphs is defined as follows: given a supply graph G=(N,E), and a demand graph (T,S), what is the maximal number of edge-disjoint paths with the end-pair in S in G? The problem is considered under two assumptions: (1) the node degrees in NT T are even, and (2) the demand graph satisfies condition defined by A. Karzanov in his 1989 paper. For any demand graph violating the above condition, the problem is known to be NP-hard even under (1), and only a few cases satisfying (1) and (2) have been solved. The talk will address the relation between the path packing problem and an auxiliary flow problem and will contain a short survey of results achieved in my dissertation. No special background in graph theory! is required.