Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
We show that one cannot rule out even a single possibility for the value of an arithmetic circuit on a given input using an NC algorithm, unless P collapses to NC (i.e., unless all problems with polynomial-time sequential solutions can be efficiently parallelized). In other words, excluding any possible solution in this case is as hard as actually finding the solution. The result is robust with respect to NC algorithms that err (i.e., exclude the correct value) with small probability. We also show that P collapses all the way down to NC1 when the characteristic of the field that the problem is over is sufficiently large (but in this case under a stronger elimination hypothesis that depends on the characteristic). © 2005 Elsevier B.V. All rights reserved.
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
M.J. Slattery, Joan L. Mitchell
IBM J. Res. Dev
Daniel M. Bikel, Vittorio Castelli
ACL 2008
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering