CRACS - Indexed Articles in Journals

Permanent URI for this collection

http://localhost:4000/handle/123456789/123

Browse

Browsing CRACS - Indexed Articles in Journals by Author "Andreia Sofia Teixeira"
  • Item
    Distinguishing Two Probability Ensembles with One Sample from each Ensemble
    ( 2016) Luís Filipe Antunes ; Buhrman,H ; Matos,A ; Souto,A ; Andreia Sofia Teixeira
    We introduced a new method for distinguishing two probability ensembles called one from each method, in which the distinguisher receives as input two samples, one from each ensemble. We compare this new method with multi-sample from the same method already exiting in the literature and prove that there are ensembles distinguishable by the new method, but indistinguishable by the multi-sample from the same method. To evaluate the power of the proposed method we also show that if non-uniform distinguishers (probabilistic circuits) are used, the one from each method is not more powerful than the classical one, in the sense that does not distinguish more probability ensembles. Moreover we obtain that there are classes of ensembles, such that any two members of the class are easily distinguishable (a definition introduced in this paper) using one sample from each ensemble; there are pairs of ensembles in the same class that are indistinguishable by multi-sample from the same method.
  • Item
    One-Way Functions Using Algorithmic and Classical Information Theories
    ( 2013) Luís Filipe Antunes ; Matos,A ; Alexandre Miranda Pinto ; Souto,A ; Andreia Sofia Teixeira
    We prove several results relating injective one-way functions, time-bounded conditional Kolmogorov complexity, and time-bounded conditional entropy. First we establish a connection between injective, strong and weak one-way functions and the expected value of the polynomial time-bounded Kolmogorov complexity, denoted here by E(K-t (x vertical bar f (x))). These results are in both directions. More precisely, conditions on E(K-t (x vertical bar f (x))) that imply that f is a weak one-way function, and properties of E(K-t (x vertical bar f (x))) that are implied by the fact that f is a strong one-way function. In particular, we prove a separation result: based on the concept of time-bounded Kolmogorov complexity, we find an interval in which every function f is a necessarily weak but not a strong one-way function. Then we propose an individual approach to injective one-way functions based on Kolmogorov complexity, defining Kolmogorov one-way functions and prove some relationships between the new proposal and the classical definition of one-way functions, showing that a Kolmogorov one-way function is also a deterministic one-way function. A relationship between Kolmogorov one-way functions and the conjecture of polynomial time symmetry of information is also proved. Finally, we relate E(K-t (x vertical bar f (x))) and two forms of time-bounded entropy, the unpredictable entropy H-unp, in which "one-wayness" of a function can be easily expressed, and the Yao(+) entropy, a measure based on compression/decompression schema in which only the decompressor is restricted to be time-bounded.
  • Item
    Sophistication vs Logical Depth
    ( 2017) Luís Filipe Antunes ; Bauwens,B ; Souto,A ; Andreia Sofia Teixeira
    Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program that is shortest within some precision. We show that the Busy Beaver function of the sophistication of a string exceeds its logical depth with logarithmically bigger precision, and that logical depth exceeds the Busy Beaver function of sophistication with logarithmically bigger precision. We also show that sophistication is unstable in its precision: constant variations can change its value by a linear term in the length of the string.