Author name cluster

William Gasarch

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2016 Journal Article

On the sizes of DPDAs, PDAs, LBAs

Richard Beigel
William Gasarch

There are languages A such that there is a Pushdown Automata (PDA) that recognizes A which is much smaller than any Deterministic Pushdown Automata (DPDA) that recognizes A. There are languages A such that there is a Linear Bounded Automata (Linear Space Turing Machine, henceforth LBA) that recognizes A which is much smaller than any PDA that recognizes A. There are languages A such that both A and A ‾ are recognizable by a PDA, but the PDA for A is much smaller than the PDA for A ‾. There are languages A 1, A 2 such that A 1, A 2, A 1 ∩ A 2 are recognizable by a PDA, but the PDA for A 1 and A 2 are much smaller than the PDA for A 1 ∩ A 2. We investigate these phenomena and show that, in all these cases, the size difference is captured by a function whose Turing degree is on the second level of the arithmetic hierarchy. Our theorems lead to infinitely-many-n results. For example: for-infinitely-many-n there exists a language A n recognized by a DPDA such that there is a small PDA for A n, but any DPDA for A n is very large. We look at cases where we can get all-but-a-finite-number-of-n results, though with much smaller size differences.

Details DOI

I&C Journal 2013 Journal Article

Limits on the computational power of random strings

Eric Allender
Luke Friedman
William Gasarch

How powerful is the set of random strings? What can one say about a set A that is efficiently reducible to R, the set of Kolmogorov-random strings? We present the first upper bound on the class of computable sets in P R and NP R. The two most widely-studied notions of Kolmogorov complexity are the “plain” complexity C ( x ) and “prefix” complexity K ( x ); this gives rise to two common ways to define the set of random strings “R”: R C and R K. (Of course, each different choice of universal Turing machine U in the definition of C and K yields another variant R C U or R K U.) Previous work on the power of “R” (for any of these variants) has shown: • BPP ⊆ { A: A ⩽ tt p R }. • PSPACE ⊆ P R. • NEXP ⊆ NP R. Since these inclusions hold irrespective of low-level details of how “R” is defined, and since BPP, PSPACE and NEXP are all in Δ 1 0 (the class of decidable languages), we have, e. g. : NEXP ⊆ Δ 1 0 ∩ ⋂ U NP R K U. Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to R K U. We show: • BPP ⊆ Δ 1 0 ∩ ⋂ U { A: A ⩽ tt p R K U } ⊆ PSPACE. • NEXP ⊆ Δ 1 0 ∩ ⋂ U NP R K U ⊆ EXPSPACE. Hence, in particular, PSPACE is sandwiched between the class of sets polynomial-time Turing- and truth-table-reducible to R. As a side-product, we obtain new insight into the limits of techniques for derandomization from uniform hardness assumptions.

Details DOI

I&C Journal 2003 Journal Article

Some connections between bounded query classes and non-uniform complexity

Amihood Amir
Richard Beigel
William Gasarch

Let A(x) be the characteristic function of A. Consider the function C A k (x 1, …, x k )=A(x 1)⋯A(x k ). We show that if C A k can be computed in polynomial time with fewer than k queries to some set X then A∈P/poly. A generalization of this result has applications to bounded query classes, circuits, and enumerability. In particular we obtain the following. (1) Assuming Σ3 p ≠Π3 p, there are functions computable using f(n)+1 queries to SAT that are not computable using f(n) queries to SAT, for f(n)=O(logn). (2) If C A k, restricted to length n inputs, can be computed by an unbounded fanin oracle circuit of size s(n) and depth d(n), with k−1 queries to some set X, then A can be computed with an unbounded fanin (non-oracle) circuit of size n O(k) s(n) and depth d(n)+O(1). (3) Assuming that PH≠Σ4 p ∩Π4 p, and ϵ<1, #SAT is not 2 n ϵ -enumerable.

Details DOI

TCS Journal 2003 Journal Article

When does a random Robin Hood win?

William Gasarch
Evan Golub
Aravind Srinivasan

A certain two-person infinite game (between “Robin Hood” and the “Sheriff”) has been studied in the context of set theory. In certain cases, it is known that for any deterministic strategy of Robin Hood's, if the Sheriff knows Robin Hood's strategy, he can adapt a winning counter-strategy. We show that in these cases, Robin Hood wins with “probability one” if he adopts a natural random strategy. We then characterize when this random strategy has the almost-surely winning property. We also explore the case of a random Sheriff versus a deterministic Robin Hood.

Details DOI

TCS Journal 1996 Journal Article

Frequency computation and bounded queries

Richard Beigel
William Gasarch
Efim Kinber

There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: F a A (x 1, …, x a ) = A(x 1)…A(x a ). We are interested in the complexity (in terms of the number of queries) of approximating F a A. Let b ⩽ a and let f be any function such that F a A (x 1, …, x a ) and f(x 1, …, x a ) agree on at least b bits. For a general set A we have matching upper and lower bounds on f that depend on coding theory. These are applied to get exact bounds for the case where A is semirecursive, A is superterse, and (assuming P ≠ NP) A = SAT. We obtain exact bounds when A is the halting problem using different methods.

Details DOI