A recursive enumerator for a function $h$ is an algorithm $f$ which enumerates for an input $x$ finitely many elements including $h(x)$. $f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$ is among the first $k(n)$ elements enumerated by $f$. If there is a $k(n)$-enumerator for ... 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 >>>

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 >>>

Prior results show that most bounded query hierarchies cannot contain finite gaps. For example, it is known that P_(m+1)-tt^SAT = P_m-tt^SAT implies P_btt^SAT = P_m-tt^SAT and for all sets A

• FP_(m+1)-tt^A = FP_m-tt^A implies FP_btt^A = FP_m-tt^A
• P_(m+1)-T^A = P_m-T^A implies P_bT^A = ... more >>>

We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MODm gates at level one. We show that the fan-in of the AND gates can be reduced to O(log n) in the case where m is unbounded, and ... 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 >>>

The classes of languages accepted by nondeterministic polynomial-time Turing machines (NP machines, in short) that have restricted access to an NP oracle --- the machines can ask k queries to the NP oracle and the answer they receive is the number of queries in the oracle language modulo a number ... more >>>

Identify a string x over {0,1} with the positive integer whose binary representation is 1x. We say that a self-reduction is k-local if on input x all queries belong to {x-1,...,x-k}. We show that all k-locally self-reducible sets belong to PSPACE. However, the power of k-local self-reductions changes drastically between ... 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 >>>

We classify the univariate functions that are relativizable closure properties of GapP, solving a problem posed by Hertrampf, Vollmer, and Wagner (Structures '95). We also give a simple proof of their classification of univariate functions that are relativizable closure properties of #P. more >>>

We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS [R. Floyd & R. Beigel, The Language of Machines]. 3-SAT is equivalent to (2,3)-SSS while the other problems ... more >>>