4
$\begingroup$

In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back.

  1. What is the rationale (at least then) behind his $NC^2=P^{\#P}$ program (Valiant is a reputed researcher) which most researchers believe is false?

  2. Is his program for proving $NC^2=P^{\#P}$ taken seriously and if so what is the status of his program?

  3. Is this talk available any where?

I am aware of holographic alorithms. But typically an inventor invents something because he believes in some vision and not the other way.

$\endgroup$
  • 3
    $\begingroup$ I know precisely nothing about this, but it's quite easy to see that this refers to the talk Valiant gave for his FOCS 2006 paper doi.org/10.1109/FOCS.2006.7 $\endgroup$ – Sasho Nikolov Jul 12 '17 at 23:05
  • $\begingroup$ "But typically an inventor invents something because he believes in some vision and not the other way." I'm not so sure about that; cf. Dyson's "Birds and Frogs". Also, if I understand the history correctly, Valiant came up with holographic algorithms because he was looking for a subset (possibly all) of quantum algorithms that could be efficiently simulated classically. And then they led to these very surprising results. $\endgroup$ – Joshua Grochow Jul 17 '17 at 18:29
  • $\begingroup$ @JoshuaGrochow 'subset (possibly all) of quantum algorithms ' so he was looking for something big (possibly at least $BQP=RP$). $\endgroup$ – Turbo Jul 17 '17 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.