Source author record

Stephen A. Fenner

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Formal Languages and Automata Theory quant-ph

Catalog footprint

Research overview

4works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Combinatorial Game Complexity: An Introduction with Poset Games

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 games. In this introduction we develop the fundamentals of combinatorial game theory and focus for the most part on poset games, of which Nim is perhaps the best-known example. We present the complexity results known to date, some discovered very recently.

preprint2014arXiv

The complexity of some regex crossword problems

In a typical regular expression (regex) crossword puzzle, you are given two nonempty lists $R_1,\ldots,R_m$ and $C_1,\ldots,C_n$ of regular expressions over some alphabet, and your goal is to fill in an $m\times n$ grid with letters from that alphabet so that the string formed by the $i$ th row is in $L(R_i)$ , and the string formed by the $j$ th column is in $L(C_j)$ , for all $1\le i\le m$ and $1\le j\le n$ . Such a grid is a solution to the puzzle. It is known that determining whether a solution exists is NP-complete. We consider a number of restrictions and variants to this problem where all the $R_i$ are equal to some regular expression $R$ , and all the $C_j$ are equal to some regular expression $C$ . We call the solution to such a puzzle an $(R,C)$ -crossword. Our main results are the following: 1. There exists a fixed regular expression $C$ over the alphabet $\{0,1\}$ such that the following problem is NP-complete: "Given a regular expression $R$ over $\{0,1\}$ and positive integers $m$ and $n$ given in unary, does an $m\times n$ $(R,C)$ -crossword exist?" This improves the result mentioned above. 2. The following problem is NP-hard: "Given a regular expression $E$ over $\{0,1\}$ and positive integers $m$ and $n$ given in unary, does an $m\times n$ $(E,E)$ -crossword exist?" 3. There exists a fixed regular expression $C$ over $\{0,1\}$ such that the following problem is undecidable (equivalent to the Halting Problem): "Given a regular expression $R$ over $\{0,1\}$ , does an $(R,C)$ -crossword exist (of any size)?" 4. The following problem is undecidable (equivalent to the Halting Problem): "Given a regular expression $E$ over $\{0,1\}$ , does an $(E,E)$ -crossword exist (of any size)?"

preprint2012arXiv

Functions that preserve p-randomness

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 computable real number. These results follow from a general theorem: If $I$ is an open interval in the reals, $f$ is a function mapping $I$ into the reals, and $r$ in $I$ is p-random, then $f(r)$ is p-random provided 1. $f$ is p-computable on the dyadic rational points in $I$ , and 2. $f$ varies sufficiently at $r$ , i.e., there exists a real constant $C > 0$ such that either (a) $(f(x) - f(r))/(x-r) > C$ for all $x$ in $I$ with $x \ne r$ , or (b) $(f(x) - f(r))(x-r) < -C$ for all $x$ in $I$ with $x \ne r$ . Our theorem implies in particular that any analytic function about a p-computable point whose power series has uniformly p-computable coefficients preserves p-randomness in its open interval of absolute convergence. Such functions include all the familiar functions from first-year calculus.

preprint2004arXiv

Implementing fanout, parity, and Mod gates via spin exchange interactions

We show that, for any n > 0, the Heisenberg interaction among 2n qubits (as spin-1/2 particles) can be used to exactly implement an n-qubit parity gate, which is equivalent in constant depth to an n-qubit fanout gate. Either isotropic or nonisotropic versions of the interaction can be used. We generalize our basic results by showing that any Hamiltonian (acting on suitably encoded logical qubits), whose eigenvalues depend quadratically on the Hamming weight of the logical qubit values, can be used to implement generalized Mod_q gates for any q > 1. This paper is a sequel to quant-ph/0309163, and resolves a question left open in that paper.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.