Lower bounds and derandomizations for branching programs

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

GENERAL:******The long-term goal of my research program is to help elucidating the structure of the complexity class P of efficiently solvable problems. In particular, can every problem in P be solved using a logarithmic amount of memory? This question predates the P versus NP question and hints at the main shortcoming of complexity theory: despite intensive efforts by a generation of researchers, no truly satisfactory lower bounds on the complexity of problems within the complexity class NP, let alone the class P, are known.******SPECIFICS:******In the next 5 years I will return to the study of branching programs, a computation model known to capture the memory resource. I first propose to concentrate on trying to explain why no branching program size lower bound better than quadratic is known for problems in NP. Obstacles to obtaining lower bounds on computational resources for solving a problem have been identified before. One influential notion of such an obstacle was developed by Razborov and Rudich in 1997: strong lower bounds obtained by means of what these authors named "natural proofs" were shown to rule out the existence of objects called efficient pseudorandom number generators, widely believed to exist. The empirical fact that many of our best current complexity lower bounds were obtained by natural proofs is thus an obstacle in the above sense.******The last 25 years have seen much research on pseudo-randomness in the context of memory-bounded computation. I am hoping to draw from this work in order to define the equivalent of natural proofs against (say) cubic size lower bounds for branching programs and to derive unlikely derandomization consequences. I will explore possible variants of natural proofs involving the recently introduced notion of pseudo-deterministic computation. I will investigate derandomization of bounded-width branching programs under the guidance of algebraic automata theory. I will consider probabilistic variants of restricted branching programs (such as monotone or incremental) and analyse their expressivity and their derandomizations. ******SIGNIFICANCE:******Rigorously proving computational complexity lower bounds can be very useful. A famous example arises in cryptography, where the current lack of computational hardness proofs prevents ruling out that a clever individual or organization might break into communication channels thought to be secure. Other examples follow from a 30-year-old discovery by now exploited extensively: if certain computational problems could be proved hard, then tools to construct pseudorandom number generators would follow; such tools in turn could serve to transform known efficient probabilistic algorithms into equally efficient deterministic (hence freed from the uncertainty that accompanies the reliance on random bits) algorithms. Searching for obstacles to proving lower bounds could as well suggest new ways to improve existing algorithms.********