All reports by Author Stephen A. Fenner:

__
TR15-177
| 9th November 2015
__

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf#### Bipartite Perfect Matching is in quasi-NC

Revisions: 2

__
TR15-021
| 5th February 2015
__

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf#### Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games

__
TR13-019
| 31st January 2013
__

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf#### On Two-Level Poset Games

__
TR08-078
| 15th April 2008
__

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer#### Universal Quantum Circuits

__
TR08-053
| 27th March 2008
__

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

__
TR04-071
| 11th August 2004
__

Marcus Schaefer, Stephen A. Fenner#### Simplicity and Strong Reductions

__
TR02-036
| 30th May 2002
__

Stephen A. Fenner#### PP-lowness and a simple definition of AWPP

__
TR99-003
| 18th December 1998
__

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim#### Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>>

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf

We consider the complexity of determining the winner of a finite, two-level poset game.

This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.

We give a simple formula allowing one to compute the status ...
more >>>

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer

Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... 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 >>>

Marcus Schaefer, Stephen A. Fenner

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>

Stephen A. Fenner

We show that the counting classes AWPP and APP [Li 1993] are more robust

than previously thought. Our results identify asufficient condition for

a language to be low for PP, and we show that this condition is at least

as weak as other previously studied criteria. Our results imply that

more >>>

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

It is shown that determining whether a quantum computation

has a non-zero probability of accepting is at least as hard as the

polynomial time hierarchy. This hardness result also applies to

determining in general whether a given quantum basis state appears

with nonzero amplitude in a superposition, or whether a ...
more >>>