Randomness and Non-determinism
From MaRDI portal
Publication:4866093
zbMATH Open0850.68021arXiv1211.0071MaRDI QIDQ4866093FDOQ4866093
Authors: Leonid A. Levin 
Publication date: 21 October 1996
Abstract: Exponentiation makes the difference between the bit-size of this line and the number (<< 2^{300}) of particles in the known Universe. The expulsion of exponential time algorithms from Computer Theory in the 60's broke its umbilical cord from Mathematical Logic. It created a deep gap between deterministic computation and -- formerly its unremarkable tools -- randomness and non-determinism. Little did we learn in the past decades about the power of either of these two basic "freedoms" of computation, but some vague pattern is emerging in relationships between them. The pattern of similar techniques instrumental for quite different results in this area seems even more interesting. Ideas like multilinear and low-degree multivariate polynomials, Fourier transformation over low-periodic groups seem very illuminating. The talk surveyed some recent results. One of them, given in a stronger form than previously published, is described below.
Full work available at URL: https://arxiv.org/abs/1211.0071
This page was built for publication: Randomness and Non-determinism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4866093)
