Abstract
Kolmogorov complexity measures the amount of information in a string as the size of the shortest program that computes the string. The Kolmogorov structure function divides the smallest program producing a string in two parts: the useful information present in the string, called sophistication if based on total functions, and the remaining accidental information. We formalize a connection between sophistication (due to Koppel) and a variation of computational depth (intuitively the useful or nonrandom information in a string), prove the existence of strings with maximum sophistication and show that they are the deepest of all strings.

Abstract
Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and traditional Kolmogorov complexity. We show unconditionally how to probabilistically find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumption though fails if BPP = FewP = EXP. We also show that assuming good pseudorandom generators one cannot increase the depth of a string efficiently.

Abstract
The Kolmogorov structure function divides the smallest program producing a string in two parts: the useful information present in the string, called sophistication if based on total functions, and the remaining accidental information. We revisit the notion of sophistication due to Koppel, formalize a connection between sophistication and a variation of computational depth (intuitively the useful or nonrandom information in a string), prove the existence of strings with maximum sophistication and show that they encode solutions of the halting problem, i.e., they are the deepest of all strings.

Abstract
In the present paper, we answer a question raised in the paper Constructions and Bounds for Unconditionally Secure Non-Interactive Commitment Schemes, by Blundo et al., 2002, showing that there is a close relation between unconditionally secure commitment schemes and unconditionally secure authentication schemes, and that an unconditionally secure commitment scheme can be built from such an authentication scheme and an unconditionally secure cipher system. To investigate the opposite direction, we define optimal commitment systems and show that these must be resolvable design commitment schemes. Then, a proof is given that the resolvable design commitment schemes are a composition of an authentication system and a cipher system and the conclusion follows that this is the case for all optimal commitment systems. We also show how to build optimal schemes from transversal designs that are easy to build and can be more efficiently implemented than the proposal in the previously cited paper.

Abstract
We give the first characterization of Turing machines that run in polynomial-time on average. We show that a Turing machine M runs in average polynomial-time if for all inputs x the Turing machine uses time exponential in the computational depth of x, where the computational depth is a measure of the amount of "useful" information in x.

Abstract
Password sharing is a common security problem. Some application domains are more exposed than others and, by dealing with very sensitive information, the healthcare domain is definitely not exempt from this problem. This chapter presents a case study of a cross section of how healthcare professionals actually deal with password authentication in typical real world scenarios. It then compares the professionals' actual practice with what they feel about password sharing and what are the most frequent problems associated with it. Further, this chapter discusses and suggests how to solve or minimize some of these problems using both technological and social cultural mechanisms. © 2011, IGI Global.