Wednesday, October 18, 2006

Analog Computing Papers

Three I've run across, but not fully digested yet:


@article{vergis1986cac,
title={The Complexity of Analog Computation},
author={Vergis, A. and Steiglitz, K. and Dickinson, B.},
journal={Mathematics \& Computers in Simulation},
volume={28},
pages={91--113},
year={1986},
comment = {Claims a digital computer can efficiently simulate an
analog one, and an analog one can't solve NP
problems if a digital one can't.}
}

@article{turan1994cbf,
title={{On the computation of Boolean functions by analog circuits ofbounded fan-in}},
author={Turan, G. and Vatan, F.},
journal={Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on},
pages={553--564},
year={1994},
comment = {Haven't read yet...}
}


@article{maass1998ean,
title={{On the effect of analog noise in discrete-time analog computations}},
author={Maass, W. and Orponen, P.},
journal={Neural Computation},
volume={10},
number={5},
pages={1071--1095},
year={1998},
publisher={MIT Press Cambridge, MA, USA}
}


The Turan paper requires an IEEE Digital Library subscription to get, the others are available free on the web if you look.

4 Comments:

At 2:50 PM, Blogger superperro1 said...

rvd, since you are an applied computer scientist (I mean the "adjective" applied as a compliment), what are your favorite books on applied, introductory, computational/circuit complexity theory. I dare not ask this question in Scott Aaronson's blog, lest I be sent to a book devoted to topics like the PCP theorem.

 
At 7:52 PM, Blogger Leucipo said...

I have always thought that there must to be an, er, analogy, between quantum computing and analog computing. Some trick using non local hidden variables in que quantum part, or something so.

 
At 1:45 AM, Blogger rdv said...

Hi SuperPerro1,

Thanks for the compliment :-).

I wish I had a good reference on circuit complexity, but I don't offhand. One place to start is The Source -- Knuth's The Art of Computer Programming. In there you will find things such as a discussion of how the performance can actually depend on the architecture of a computer (an obvious point which is often overlooked) -- a Turing Machine behaves very differently from one with random-access memory. Hope that helps.

 
At 1:50 AM, Blogger rdv said...

Hi Leucipo,

There is a lot of discussion about the relationship between quantum and analog computation, of course, and it sometimes gets heated; I think people are usually coming from a particular set of assumptions that are not always well articulated.

QC is much more than just analog computation, with its computational power coming from the superposition and entanglement of quantum variables. But, in my opinion, it's difficult to see how someone can claim that QC is not analog computation, when quantum algorithms are defined in terms of continuous rotation angles. Of course, as long as we're talking about qubits, the end result of a measurement is always a binary value, so it's not exactly analog; then, of course, there are the continuous quantum variables (qunats), which are a whole different ball of wax.

 

Post a Comment

<< Home