All reports by Author William Gasarch:

__
TR10-139
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Limits on the Computational Power of Random Strings

Revisions: 1

__
TR10-138
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions

__
TR08-053
| 27th March 2008
__

Stephen A. Fenner, William Gasarch, Brian Postow#### The complexity of learning SUBSEQ(A)

__
TR04-120
| 22nd November 2004
__

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis#### Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a

__
TR03-087
| 10th December 2003
__

Richard Beigel, Lance Fortnow, William Gasarch#### A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

__
TR01-019
| 2nd March 2001
__

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet#### The Communication Complexity of Enumeration, Elimination, and Selection

__
TR00-024
| 16th May 2000
__

Amihood Amir, Richard Beigel, William Gasarch#### Some Connections between Bounded Query Classes and Non-Uniform Complexity

__
TR96-051
| 1st October 1996
__

Richard Beigel, William Gasarch, Ming Li, Louxin Zhang#### Addition in $\log_2{n}$ + O(1)$ Steps on Average: A Simple Analysis

__
TR95-036
| 5th July 1995
__

Richard Beigel, William Gasarch, Efim Kinber#### Frequency Computation and Bounded Queries

Eric Allender, Luke Friedman, William Gasarch

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>

Eric Allender, Luke Friedman, William Gasarch

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at ... more >>>

Stephen A. Fenner, William Gasarch, Brian Postow

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, ...
more >>>

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

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

Richard Beigel, Lance Fortnow, William Gasarch

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

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

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

Amihood Amir, Richard Beigel, William Gasarch

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

Richard Beigel, William Gasarch, Ming Li, Louxin Zhang

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.

Richard Beigel, William Gasarch, Efim Kinber

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