Comparing Notions of Computational Entropy

In the information theoretic world, entropy is both the measure of randomness in a source and a bound for the compression achievable for that source by any encoding scheme. But when we must restrict ourselves to efficient schemes, entropy no longer captures these notions well. For example, there are distributions with very low entropy that nonetheless look random for polynomial-bound algorithms. Different notions of computational entropy have been proposed to take the role of entropy in such settings. Results in Goldberg and Sipser (SIAM J. Comput. 20(3):524–536, 1991) and Wee (IEEE conference on computational complexity, pp. 29–41, 2004) suggest that when time bounds are introduced, the entropy of a distribution no longer coincides with the most effective compression for that source. This paper analyses three measures that try to capture the compressibility of a source, establishing relations and separations between them and analysing the two special cases of the uniform and the universal distribution m ^t over binary strings of a fixed size. It is shown that for the uniform distribution the three measures are equivalent and that for m ^t there is a clear separation between metric type entropy and the maximum compressibility of a source. Partially supported by KCrypt (POSC/EIA/60819/2004), the grant SFRH/BD/13124/2003 from FCT and funds granted to LIACC through the Programa de Financiamento Plurianual, FCT and Programa POSI.     

The hardness of the Expected Decision Depth problem

Given a function f over n binary variables, and an ordering of the n variables, we consider the Expected Decision Depth problem. Namely, what is the expected number of bits that need to be observed until the value of the function is determined, when bits of the input are observed according to the given order. Our main finding is that this problem is (essentially) #P-complete. Moreover, the hardness holds even when the function f is represented as a decision tree.     

Sophistication Revisited

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.     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.     

Randomness Buys Depth for Approximate Counting

We show that the promise problem of distinguishing n-bit strings of relative Hamming weight \({1/2 + \Omega(1/{\rm lg}^{d-1} n)}\) from strings of weight \({1/2 - \Omega(1/{\rm \lg}^{d - 1} n)}\) can be solved by explicit, randomized (unbounded fan-in) poly(n)-size depth-d circuits with error \({\leq 1/3}\) , but cannot be solved by deterministic poly(n)-size depth-(d+1) circuits, for every \({d \geq 2}\) ; and the depth of both is tight. Our bounds match Ajtai’s simulation of randomized depth-d circuits by deterministic depth-(d + 2) circuits (Ann. Pure Appl. Logic; ’83) and provide an example where randomization buys resources. To rule out deterministic circuits, we combine Håstad’s switching lemma with an earlier depth-3 lower bound by the author (Computational Complexity 2009). To exhibit randomized circuits, we combine recent analyses by Amano (ICALP ’09) and Brody and Verbin (FOCS ’10) with derandomization. To make these circuits explicit, we construct a new, simple pseudorandom generator that fools tests \({A_1 \times A_2 \times \cdots \times A_{{\rm lg}{n}}}\) for \({A_i \subseteq [n], |A_{i}| = n/2}\) with error 1/n and seed length O(lg n), improving on the seed length \({\Omega({\rm lg}\, n\, {\rm lg}\, {\rm lg}\, n)}\) of previous constructions.     

Computational depth: Concept and applications

We introduce Computational Depth, a measure for the amount of “nonrandom” or “useful” information in a string by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of Computational Depth:

•$•$

Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. We show that a Turing machine M runs in time polynomial on average over the time-bounded universal distribution if and only if for all inputs x, M uses time exponential in the basic computational depth of x.     

Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Reviewing bounds on the circuit size of the hardest functions

In this paper we review the known bounds for L(n), the circuit size complexity of the hardest Boolean function on n input bits. The best known bounds appear to be

     

Non-reducible descriptions for conditional Kolmogorov complexity

Assume that a program p$p$ on input a$a$ outputs b$b$. We are looking for a shorter program q$q$ having the same property (q(a)=b$q\left(a\right)=b$). In addition, we want q$q$ to be simple conditional to p$p$ (this means that the conditional Kolmogorov complexity K(q|p)$K\left(q\right|p)$ is negligible). In the present paper, we prove that sometimes there is no such program q$q$, even in the case when the complexity of p$p$ is much bigger than K(b|a)$K\left(b\right|a)$. We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively.     

On the P versus NP intersected with co-NP question in communication complexity

We consider the analog of the P versus NP∩co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation ¬f have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP∩co-NP.We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP∩co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982.     

The frequent paucity of trivial strings

A 1976 theorem of Chaitin can be used to show that arbitrarily dense sets of lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs, and it gives a tighter paucity bound.     

A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle

We prove a superlinear lower bound on the size of a bounded depth bilinear arithmetical circuit computing cyclic convolution. Our proof uses the strengthening of the Donoho–Stark uncertainty principle [D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM Journal of Applied Mathematics 49 (1989) 906–931] given by Tao [T. Tao, An uncertainty principle for cyclic groups of prime order, Mathematical Research Letters 12 (2005) 121–127], and a combinatorial lemma by Raz and Shpilka [R. Raz, A. Shpilka, Lower bounds for matrix product, in arbitrary circuits with bounded gates, SIAM Journal of Computing 32 (2003) 488–513]. This combination and an observation on ranks of circulant matrices, which we use to give a much shorter proof of the Donoho–Stark principle, may have other applications.     

Incompleteness,Complexity, Randomness and Beyond

Gödel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.     

The size and depth of layered Boolean circuits

We consider the relationship between size and depth for layered Boolean circuits and synchronous circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth . For synchronous circuits of size s, we obtain simulations of depth . The best known result so far was by Paterson and Valiant (1976) [17], and Dymond and Tompa (1985) [6], which holds for general Boolean circuits and states that , where C(f) and D(f) are the minimum size and depth, respectively, of Boolean circuits computing f. The proof of our main result uses an adaptive strategy based on the two-person pebble game introduced by Dymond and Tompa (1985) [6]. Improving any of our results by polylog factors would immediately improve the bounds for general circuits.     

Nearly-perfect hypergraph packing is in NC

Answering a question of Rödl and Thoma, we show that the Nibble Algorithm for finding a collection of disjoint edges covering almost all vertices in an almost regular, uniform hypergraph with negligible pair degrees can be derandomized and parallelized to run in polylog time on polynomially many parallel processors. In other words, the nearly-perfect packing problem on this class of hypergraphs is in the complexity class NC.     

Complexity of DNA sequencing by hybridization

In the paper, the question of the complexity of the combinatorial part of the DNA sequencing by hybridization, is analyzed. Subproblems of the general problem, depending on the type of error (positive, negative), are distinguished. Since decision versions of the subproblems assuming only one type of error are trivial, complexities of the search counterparts are studied. Both search subproblems are proved to be strongly NP-hard, as well as their uniquely promised versions.