At Dagstuhl I got a few ideas for future posts but then...
We had some discussions about STOC allowing program committee members to submit papers that I planned to post about. But then Suresh wrote a fine post on the same issue for SODA. My thoughts: PC members should not submit--no matter how you try to avoid the conflict of interest, there will always be a cloud on the process. Suresh suggest blind reviews that other non-theory conferences use, but I prefer the tiered PC system. It's fine to have PC members submit papers if the top of the tier, a senior PC or the PC chairs, makes the final calls.
I was also going to post about Yann LeCun's Facebook rant about stodgy CS departments but then Yann goes ahead and wins a Turing award with Geoffrey Hinton and Yoshua Bengio for their work on machine learning. I knew Yann from when we worked together at NEC Research in the early 2000's and let's just congratulate him and the others and let them bask in glory for truly transforming how we think of computing today. I'll get back to his post soon enough.
As a suitable subject for future Computational Complexity essays, please allow me to suggest the Extended Church-Turing Thesis (ECT).
ReplyDeleteAs a start, Boaz Barak's online textbook-in-progress Introduction to Theoretical Computer Science (available on-line) summarizes the present ECT consensus as follows:
-----------
In the last hundred+ years of studying and mechanizing computation, no one has yet constructed a scalable computing device (or even gave a convincing blueprint) that violates the extended Church Turing Thesis. That said, as we mentioned before quantum computing, if realized, does pose a serious challenge to this thesis. However, even if the promises of quantum computing are fully realized, it still seems that the extended Church-Turing thesis is fundamentally or "morally" correct, in the sense that, while we do need to adapt the thesis to account for the possibility of quantum computing, its broad outline remains unchanged.
-----------
Barak's broad outline of the ECT encompasses (for example) the cognitive themes that Sanjeev Arora's plenary lecture at the 2018 ICM "The mathematics of machine learning and deep learning " articulates as follows (beginning at 57m20s):
-----------
"We have very little idea at an operational level of how humans think … in fact, machine learning is currently the best hope for learning how humans think … This is the hottest trend in academia: apply machine learning to discipline "X" … Machine learning speaks to age-old wonders and mysteries … it's a new way of looking at the world, via complicated inexact descriptions that we embrace … a new frontier for knowledge and math …I am optimistic that deep-learning methods can be mathematically understood and/or simplified."
-----------
Arora's views are consonant, in turn, with this year's Turing Award to (in alphabetical order) Yoshua Bengio, Geoffrey Hinton, and Yann LeCun; an award due in large measure to these researchers' development and practical application of efficient back-propagation algorithms. That this particular Turing Award is well-received amounts to a ECT-centric consensus appreciation that: (1) in practice, "merely polynomial" algorithmic speedups can be scientifically and strategically transformational, and (2) fresh insights into age-old "soft" questions like "how are mathematical ideas conceived?" can be comparably transformational to fresh insights into rigorously logical questions like "how are mathematical ideas validated?".
As yet another perspective, ultra-orthodox Quantum Supremacists — are there any? — can cite rigorously logical reasons to dismiss this particular Turing Award as "hype", in the sense that these researcher's back-propagation algorithms for network-training afford a mere polynomial speedup.
No such criticisms of this year's Turing Award are heard (that I know of anyway) … and this consensus assent itself is broadly consonant with Boaz Barak's assertion (cited above) that "the extended Church-Turing thesis is fundamentally or 'morally' correct".
In summary, then, the Extended Church-Turing Thesis affords plenty of material for discussion here on Computational Complexity (and elsewhere) … and plenty of scope too for reasonable-yet-diverse opinions.