Secluded Connectivity Problems, and US Grad School

Expositor: Matthew P. Johnson (City University of New York – CUNY)

Fecha: Miércoles 12 de Agosto de 2015

Hora: 18:00 hrs.

Lugar: Sala E -VEO (Pabellón Mac Gregor – primer piso)

Para visitantes externos a la PUCP, favor inscribirse en el siguiente link, a efectos de autorizar el acceso al campus:

Actualizacion (13/08/15)

Las diapositivas de la presentacion se encuentran en el siguiente enlace

Abstract: In this talk I will present an example of research problema studied by my group, and I will then discuss applying to and excellingin US computer science PhD programs.

Consider a setting where possibly sensitive information sent over a path in a network is visible to every neighbor of the path, i.e., every neighbor of some node on the path, thus including the nodes on the path itself. The exposure of a path $P$ can be measured as the number of nodes adjacent to it, denoted by $N[P]$. We show that on unweighted undirected $n$-node graphs, the problem of finding the minimum exposure path connecting a given pair of vertices is strongly inapproximable, i.e., hard to approximate within a factor of $O(2^{\log^{1-\epsilon}n})$ for any $\epsilon>0$ (under an appropriate complexity assumption), but is approximable with ratio $\sqrt{\Delta}+3$, where $\Delta$ is the maximum degree in the graph.
One of our main results concerns the class of bounded-degree graphs, which is shown to exhibit the following interesting dichotomy. On the one hand, the minimum exposure path problem is NP-hard on node-weighted or directed bounded-degree graphs (even when the máximum degree is 4). On the other hand, we present a polynomial algorithm (based on a nontrivial dynamic program) for the problem on unweighted undirected bounded-degree graphs.

Finally, I'll talk about going to grad school in the US: what makes a strong application, how to prepare, and what to do once you're there.

Matthew P. Johnson is assistant professor at Lehman College and the Graduate Center of the City University of New York (CUNY). He received his PhD in computer science from CUNY in 2010 and, after postdocs at Penn State and UCLA, joined in the CUNY faculty in 2013. His current research interests focus on algorithms, including approximation algorithms and algorithmic game theory. As an undergrad he studied philosophy and math at Columbia and at Lawrence University.

My research is mostly in "applied theoretical computer science".