Randomness in Computing

点击翻译按钮获取中文摘要

CCR-9820934LevinDecades of research failed to demystify the power of the two basic "freedoms" stretching the concept of deterministic computation: randomness and non-determinism. In recent years, however, some vague pattern is emerging in relationships between them. Even more notable seems the pattern of techniques instrumental for quite different results in this area: multilinear and low-degree multivariate polynomials, Fourier transformation over low-periodic groups, related to classical results on error-correcting codes or hashing. Some techniques based on different math, like expander graphs, also emerge as very relevant. This project continues investigation of the power of randomness and non-determinism using the above or similar techniques. Several specific directions of the research are:The concept and specific examples of average-case (rather than worst case) intractability of NP-problems and problems of inverting one-way functions; removing degeneracy of one-way functions as an obstacle to efficient generation of pseudo-random bits. Improvement and simplification of fault-resistant computation and communication.