Title: List-coloring the square of a subcubic graph

The {square} $G^2$ of a graph $G$ is the graph with the same vertex set as $G$ and with two vertices adjacent if their distance in $G$ is at most 2.

Thomassen showed that every planar graph $G$ with maximum degree $\Delta(G)=3$ satisfies $\chi(G^2)\leq 7$. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of $G^2$ equals the chromatic number of $G^2$, that is $\chi_l(G^2)=\chi(G^2)$ for all $G$. If true, this conjecture (together with Thomassen's result) implies that every planar graph $G$ with $\Delta(G)=3$ satisfies $\chi_l(G^2)\leq 7$. We prove that every connected graph (not necessarily planar) with $\Delta(G)=3$ other than the Petersen graph satisfies $\chi_l(G^2)\leq 8$ (and this is best possible). In addition, we show that if $G$ is a planar graph with $\Delta(G)=3$ and girth $g(G)\geq 7$, then $\chi_l(G^2)\leq 7$.

Dvo\v{r}\'{a}k, \v{S}krekovski, and Tancer showed that if $G$ is a planar graph with $\Delta(G) = 3$ and girth $g(G) \geq 10$, then $\chi_l(G^2)\leq 6$. We improve the girth bound to show that if $G$ is a planar graph with $\Delta(G)=3$ and $g(G) \geq 9$, then $\chi_l(G^2) \leq 6$. All of our proofs can be easily translated into linear-time coloring algorithms. This is joint work with Seog-Jin Kim, of Konkuk University, Seoul, Korea.

Title: Private Inference Control For Aggregate Database Queries

Data security is a critical issue for many organizations. Sensitive data must be protected from both inside and outside attackers. Access control policies and related mechanisms have been used for several decades to prevent unauthorized users from accidentally or deliberately extracting sensitive information. However, access control mechanisms alone cannot ensure the security of a database. An authorized user might invoke a sequence of queries, each of which is under his privileges, but whose results can be combined to infer some additional information about the data. Various ``inference control'' methods have been developed in the past to prevent users from inferring sensitive information through a sequence of queries. Private inference control provides privacy properties to both database owners and users making queries. It protects the database owner by limiting access to the data according to a specified inference control policy, but also to protect the user by preventing the database owner from learning anything about the user's queries.

We study private inference control for aggregate queries, such as those provided by statistical databases or modern database languages, to a database in a way that satisfies both privacy requirements and inference control requirements. For each query, the client learns the value of the function for that query if and only if the query passes a specified inference control rule. The server learns nothing about the queries, and the client learns nothing other than the query output for passing queries.

Title: Sums of powers of polynomial

It is known that every polynomial can be written as a sum of powers of linear polynomials (i.e., polynomials of degree one). Some polynomials may however require a large number of summands when written as a sum of powers in this way.

We give asymptotically tight bounds for the number of summands for an explicit family of polynomials (upper and lower bounds for this 'model of computation') and also devise an efficient deterministic algorithm to determine if a given sum of powers adds up to the identically zero polynomial (identity testing). Finally, we also devise an efficient algorithm to find a representation of a polynomial as a sum of powers where the number of summands is the minimum possible. This is joint work with Nitin Saxena.

Title: Scheduling and graph problems in implementation of diagnosis model

Data mining methods are increasingly used in medical research. In the specific field of clinical research, results might be combinations of medical tests that help physicians to decide whether or not a patient suffers from a disease. Medical practitioners are concerned with using these models efficiently in terms of costs and time in their daily activities.

We will describe two practical problems submitted by physicians. We will show how these questions are related to known scheduling and graph problems. Then we will focus on theoretical results on a new graph problem related to the densest subgraph problem . In this qproblem, we want to find solutions that could be extended or reduced (in term of vertices) while preserving the property of density.

Title: Approximate Dynamic Programming for High-Dimensional Applications

Approximate dynamic programming is proving to be increasingly useful for large-scale, stochastic dynamic problems that arise in a variety of applications. We focus on a broad class of problems that can be called ^Sresource allocation^T which includes transportation and logistics, medical, homeland security, electric power, and energy. These problems are naturally formulated as dynamic programs, but solving them quickly encounters the three curses of dimensionality. We review the three curses, and describe a generic algorithmic methodology for overcoming them. A critical step is the use of the post-decision state variable. Using different examples to motivate the techniques, we illustrate different approximation strategies, and discuss important topics that arise in ADP applications, including stepsizes and the exploration vs. exploitation problem.