15 citations · 81 across the 23 of their papers we have counts for
9 papers · 1 filter
Compression Complexity
Stephen Fenner, Lance Fortnow
The Kolmogorov complexity of x, denoted C(x), is the length of the shortest program that generates x. For such a simple definition, Kolmogorov complexity has a rich and deep theory…
Bipartite Perfect Matching is in quasi-NC
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
We show that the bipartite perfect matching problem is in quasi-NC. That is, it has uniform circuits of quasi-polynomial size , and depth. Previousl…
Combinatorial Game Complexity: An Introduction with Poset Games
Stephen A. Fenner, John Rogers
Poset games have been the object of mathematical study for over a century, but little has been written on the computational complexity of determining important properties of these…
The complexity of some regex crossword problems
Stephen A. Fenner
In a typical regular expression (regex) crossword puzzle, you are given two nonempty lists and of regular expressions over some alphabet, and your…
Functions that preserve p-randomness
Stephen A. Fenner
We show that polynomial-time randomness (p-randomness) is preserved under a variety of familiar operations, including addition and multiplication by a nonzero polynomial-time compu…
Universal Quantum Circuits
Debajyoti Bera, Stephen Fenner, Frederic Green +1
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 quant…
The central nature of the Hidden Subgroup problem
S. A. Fenner, Y. Zhang
We show that several problems that figure prominently in quantum computing, including Hidden Coset, Hidden Shift, and Orbit Coset, are equivalent or reducible to Hidden Subgroup fo…
A Physics-Free Introduction to the Quantum Computation Model
Stephen A. Fenner
This article defines and proves basic properties of the standard quantum circuit model of computation. The model is developed abstractly in close analogy with (classical) determini…
Gales and supergales are equivalent for defining constructive Hausdorff dimension
Stephen A. Fenner
We show that for a wide range of probability measures, constructive gales are interchangable with constructive supergales for defining constructive Hausdorff dimension, thus genera…