ARC 7 (Annual Event) with Keynote by Christos Papadimitriou


 9:00 - 9:05      Introduction

 9:05 - 10:35    Talks by Srinivas Aluru (CSE), Santosh Vempala (CS), and Natashia Boland (ISyE)  (30 minutes each)

 10:35 - 11:00  Break and light snacks

 11:00 - 12:00  Keynote by Christos Papadimitriou (U.C.- Berkeley) 

(see titles and abstracts below)


Srinivas Aluru, (CSE)

Title: Parallel machine learning approaches for reverse engineering genome-scale networks

Abstract: Reverse engineering whole-genome networks from large-scale gene expression measurements and analyzing them to extract biologically valid hypotheses are important challenges in systems biology. While simpler models easily scale to large number of genes and gene expression datasets, more accurate models are compute intensive limiting their scale of applicability. In this talk, I will present our research on the development of parallel mutual information and Bayesian network based structure learning methods to eliminate such bottlenecks and facilitate genome-scale network structure learning.


Santosh Vempala, (CS)

Title: Safe and Easy: Humanly Usable Password Generation Methods

Abstract: On a typical day, humans brush teeth, read, eat, converse ... and type passwords. This last task seems to be overly time-consuming (multiple attempts, frequent resets) and insecure --- passwords are often compromised. We desire passwords that are HUMANLY USABLE, i.e., easy to generate when needed, and SECURE, i.e., any single password is hard to crack, but even knowing several passwords doesn't allow an adversary infer others. Is this possible? How? How to even measure human effort? These questions lead us to ask what (protocols and algorithms) humans can compute and cannot compute. We present a model for measuring the complexity of human computation, and apply it in a rigorous framework for password generation.

This is joint work with Manuel Blum.


Natashia L Boland, (ISyE)

Title: Alternating Projection Algorithms and Integer Programming

Abstract: Alternating projection algorithms have been independently discovered, and have made a significant impact, in diverse areas of science and engineering. They remain of great interest and current activity in convex optimization, and were independently discovered for general-purpose integer programming (IP) in 2005. Their use has been one component of the major advances in IP technology that now make IP a valuable and practical tool for solution of large-scale industrial problems. An essential element of the success of these methods is the application of randomization within the alternating projection framework.  Since their first discovery for IP, the methods have been improved and extended in a number of directions. In this talk, we will give an overview of recent activity in these methods, including two new ideas for improving their performance.


Keynote Speaker

Christos H Papadimitriou, UC-Berkeley

Title: Life under the lens

Abstract: Applying the algorithmic point of view to the natural, life, and social sciences often results in unexpected insights and progress in central problems, a mode of research that has been described as ``the lens of computation.''  I will focus on examples in the life sciences, from joint work with Erick Chastain, Costis Daskalakis, Adi Livnat, Umesh Vazirani, Santosh Vempala, and Albert Wu:  Evolution of a population through sexual reproduction can be rethought of as a repeated game between genes played through the multiplicative weight updates algorithm.  In an infinite population, when selection acts not on genes alone but on pairs of genes, fixation can take exponentially many generations.  And unsupervised learning of patterns can be achieved spontaneously and with high probability through a simple and neurally plausible primitive.

Bio: Christos H. Papadimitriou is the C. Lester Hogan Professor of Computer Science at UC-Berkeley.  Before joining Berkeley in 1996, he taught at Harvard, MIT, NTU Athens, Stanford, and UCSD.  He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, control, AI, robotics, economics, game theory, the Internet, evolution, and brain science.  He holds a PhD from Princeton, and seven honorary doctorates.  He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering. He has also written three novels: “Turing”, “Logicomix” (with Apostolos Doxiadis) and “Independence” (in Greek).

Event Details


  • Friday, April 17, 2015
    9:00 am - 12:00 pm
Location: MiRC 102

For More Information Contact