Higman showed that if A is *any* language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. (The result we attribute to Higman is actually an easy consequence of his work.) Let s_1, s_2, s_3, ... be the standard lexicographic enumeration of all ... more >>>

Alice and Bob want to know if two strings of length $n$ are almost equal. That is, do they differ on at most $a$ bits? Let $0\le a\le n-1$. We show that any deterministic protocol, as well as any error-free quantum protocol ($C^*$ version), for this problem requires at least ... more >>>

We show that any 1-round 2-server Private Information Retrieval Protocol where the answers are 1-bit long must ask questions that are at least $n-2$ bits long, which is nearly equal to the known $n-1$ upper bound. This improves upon the approximately $0.25n$ lower bound of Kerenidis and de Wolf while ... more >>>

Normally, communication Complexity deals with how many bits Alice and Bob need to exchange to compute f(x,y) (Alice has x, Bob has y). We look at what happens if Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n and they want to compute f(x_1,y_1)... f(x_n,y_n). THis seems hard. We look at various ... more >>>

Let A(x) be the characteristic function of A. Consider the function F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be computed with fewer than k queries to some set X, then A can be computed by polynomial size circuits. A generalization of this result has applications to bounded query ... more >>>

We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two $n$-bit numbers in $\ceiling{\log_2{n}}+2$ steps on average. We simplify the analysis of Burks, Goldstine, and von Neumann in 1946 and (in more complete forms) of Briley and of Schay. more >>>

For a set A and a number n let F_n^A(x_1,...,x_n) = A(x_1)\cdots A(x_n). We study how hard it is to approximate this function in terms of the number of queries required. For a general set A we have exact bounds that depend on functions from coding theory. These are applied ... more >>>