I will begin by surveying my work within algorithms and uncertainty: the study of algorithms with uncertainty in their inputs. This study arises in different contexts such as average case analysis and understanding properties of complex networks. I will present results on bootstrap percolation in random graphs, the effects of adding a small number of random edges to connected graphs and the computational complexity of solving NP-hard problems over instances that are subjected to random deletions. I will then present recent work concerned with mathematical modeling inspired by questions from artificial intelligence, cognitive science and neuroscience: Using graph theory to study multitasking in parallel architectures. Finally, I will conclude with some future directions arising from these works.
No familiarity with the topics in the lecture will be assumed.
Daniel Reichman is a Postdoctoral fellow at UC Berkeley affiliated with EECS and BAIR.