Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Luke Schaeffer:

TR16-159 | 18th October 2016
Daniel Grier, Luke Schaeffer

New Hardness Results for the Permanent Using Linear Optics

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

TR15-066 | 20th April 2015
Scott Aaronson, Daniel Grier, Luke Schaeffer

The Classification of Reversible Bit Operations

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>>

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

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

TR14-084 | 12th June 2014
Luke Schaeffer

A Physically Universal Cellular Automaton

Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by ... more >>>

ISSN 1433-8092 | Imprint