Computability | EPFL Graph Search

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power. Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation. Problems A central idea in computability is that of a (computational) problem, which is a task whose computability can be explored. There are two key types of problems:

A decision problem fixes a set S, which may be a set of strings, natural numbers, or oth

Optimal Computational Split-state Non-malleable Codes

Divesh Aggarwal, Divya Gupta

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently. The central goal in the split-state model is to construct high rate non-malleable codes against all functions with only two states (which are necessary). Following a series of long and impressive line of work, constant rate, two-state, non-malleable codes against all functions were recently achieved by Aggarwal et al. [2]. Though constant, the rate of all known constructions in the split state model is very far from optimal (even with more than two states). In this work, we consider the question of improving the rate of splitstate non-malleable codes. In the "information theoretic" setting, it is not possible to go beyond rate 1/2. We therefore focus on the standard computational setting. In this setting, each tampering function is required to be efficiently computable, and the message in the tampered codeword is required to be either the original message m or a "computationally" independent one. In this setting, assuming only the existence of one-way functions, we present a compiler which converts any poor rate, two-state, (sufficiently strong) non-malleable code into a rate-1, two-state, computational non-malleable code. These parameters are asymptotically optimal. Furthermore, for the qualitative optimality of our result, we generalize the result of Cheraghchi and Guruswami [10] to show that the existence of one-way functions is necessary to achieve rate > 1/2 for such codes. Our compiler requires a stronger form of non-malleability, called augmented non-malleability. This notion requires a stronger simulation guarantee for non-malleable codes and simplifies their modular usage in cryptographic settings where composition occurs. Unfortunately, this form of non-malleability is neither straightforward nor generally guaranteed by known results. Nevertheless, we prove this stronger form of non-malleability for the two-state construction of Aggarwal et al. [3]. This result is of independent interest.

Springer Int Publishing Ag2016

Perturbation analysis for the Darcy problem with log-normal permeability

Francesca Bonizzoni, Fabio Nobile

We study the single-phase flow in a saturated, bounded heterogeneous porous medium. We model the permeability as a log-normal random field. We perform a perturbation analysis, expanding the solution in Taylor series. The series is directly computable in the case of a random field parametrized by a finite number of random variables. On the other hand, in the case of an infinite dimensional random field, suitable equations satisfied by the derivatives of the stochastic solution can be derived. We give a theoretical upper bound for the norm of the residual of the Taylor expansion which predicts the divergence of the series as the polynomial degree goes to infinity. We provide a formula to compute the optimal degree for the Taylor polynomial and the maximum achievable accuracy of the perturbation approach. Our theoretical findings are confirmed by numerical experiments in the simple case where the permeability field is described using one random variable

2014

Optimal Computational Split-state Non-malleable Codes

Divesh Aggarwal, Divya Gupta

Springer Int Publishing Ag2016