Zobrazeno 1 - 10
of 89
pro vyhledávání: '"Steven Homer"'
Publikováno v:
ACM SIGACT News. 49:35-47
For a number of years we have been investigating the geometric and algebraic properties of a family of discrete sets of points in Euclidean space generated by a simple binary operation: pairwise affine combination by a xed parameter, which we call xe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f0db6849bab8c404a1c11fec1b4a8875
https://doi.org/10.1145/3289137.3289145
https://doi.org/10.1145/3289137.3289145
Publikováno v:
ACM SIGACT News. 38:35-50
Small depth quantum circuits have proved to be unexpectedly powerful in comparison to their classical counterparts. We survey some of the recent work on this and present some open problems.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1db70982ae0c195890eb9a0a0d846a03
https://doi.org/10.1145/1272729.1272739
https://doi.org/10.1145/1272729.1272739
Publikováno v:
Quantum Information and Computation. 6:46-57
We consider the resource bounded quantum circuit model with circuits restricted by the number of qubits they act upon and by their depth. Focusing on natural universal sets of gates which are familiar from classical circuit theory, several new lower
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1bd81cee8d57455214fab603c961f30a
https://doi.org/10.26421/qic6.1-3
https://doi.org/10.26421/qic6.1-3
Autor:
Steven Homer, Alan L. Selman
The theory of computing provides computer science with concepts, models, and formalisms for reasoning about both the resources needed to carry out computa tions and the efficiency of the computations that use these resources. lt provides tools to m
Autor:
Steven Homer, Alan L. Selman
Publikováno v:
Turing's Legacy
Turing's beautiful capture of the concept of computability by the “Turing machine” linked computability to a device with explicit steps of operations and use of resources. This invention led in a most natural way to build the foundations for comp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0a321a5ba067a0ad78f9a0a3efd45561
https://doi.org/10.1017/cbo9781107338579.009
https://doi.org/10.1017/cbo9781107338579.009
Publikováno v:
Theoretical Computer Science. 262(1-2):241-256
Assuming that the polynomial hierarchy (PH) does not collapse, we show the existence of ascending sequences of ptime Turing degrees of length ω 1 CK in PSPACE such that successors are polynomial jumps of their predecessors. Moreover these ptime degr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9ff9efa6357745c20c059c28d93e9f33
Publikováno v:
Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences. 455:3953-3966
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 a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::728dc8d53939a1659fd5c0dd8008454b
https://doi.org/10.1098/rspa.1999.0485
https://doi.org/10.1098/rspa.1999.0485
Autor:
Marcus Peinado, Steven Homer
Publikováno v:
Journal of Parallel and Distributed Computing. 46:48-61
We develop and experiment with a new parallel algorithm to approximate the maximum weight cut in a weighted undirected graph. Our implementation starts with the recent (serial) algorithm of Goemans and Williamson for this problem. We consider several
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a8447fd80f981e48c31972ca2bff9cc5
https://doi.org/10.1006/jpdc.1997.1381
https://doi.org/10.1006/jpdc.1997.1381
Publikováno v:
SIAM Journal on Computing. 26:1043-1065
This paper focuses on complexity classes of partial functions that are computed in polynomial time with oracles in NPMV, the class of all multivalued partial functions that are computable nondeterministically in polynomial time. Concerning determinis
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3c9561fe424ee0cdfdba0888aaf0f059
https://doi.org/10.1137/s0097539793247439
https://doi.org/10.1137/s0097539793247439