Plenary Speakers

Reformulations of nonlinear binary optimization problems

A pseudo-Boolean function is a real-valued function f(x)=f(x₁,x₂,...,x_n) of n binary variables. It is well-known that every pseudo-Boolean function can be uniquely represented as a multilinear polynomial in its variables. Nonlinear binary optimization problems, or pseudo-Boolean optimization (PBO) problems, of the form min{ f(x) : x ∈ {0,1}ⁿ } where f(x) is a pseudo-Boolean polynomial, have attracted the attention of numerous researchers for more than 50 years. These problems are notoriously difficult, as they naturally encompass a broad variety of models such as maximum satisfiability, max cut, graph coloring, or image restoration. In this talk, I present recent results (obtained in collaboration with Martin Anthony, Endre Boros, Christoph Buchheim, Aritanan Gruber, and Elisabeth Rodriguez-Heck) regarding reformulations of nonlinear PBO problems either as linear integer programming problems or as quadratic PBO problems.

Super-connectivity and super-edge-connectivity of graphs

Network design focuses on determining how to best connect nodes such that the resulting network is, among other considerations, efficient, resistant to threats, cost-effective and fault tolerant. A topological optimisation question that addresses the requirement of fault-tolerance asks for the connectivity of the graph (or digraph) underlying the network. The property of a graph being connected depends only on whether the graph contains a path for every pair of vertices. However, besides the classical connectivity measures that study the minimum number of vertices or edges that need to be deleted to disconnect the graph, other types of connectivity have recently received much attention. These include connectivity parameters that impose some restrictions on the components of the remaining graph; a notion proposed by Harary (1983) and known as conditional connectivity. Given a graph G and some graph theoretical property P, the size of the smallest set S of vertices (or edges), if such a set exists, such that the graph G-S is disconnected and every remaining component has property P is the conditional connectivity (or conditional edge-connectivity) of G. Although, theoretically, any property P can be chosen, the most popular choices of P are those having practical applications.

In this talk we restrict our attention to the super-connectivity and the super-edge-connectivity of a graph. These notions respectively study the least number of vertices and edges that need to be deleted from a graph to disconnect the graph such that each remaining component is not trivial. In other words, the property that each component must possess is that of not being an isolated vertex, or equivalently, that of containing at least one edge. We will present well-known bounds for these parameters and discuss sufficient conditions for the bounds to be attained in terms of vertex-degrees, diameter and girth. Finally we review the super-connectivity and the super-edge-connectivity of some families of graphs, including circulant graphs, hypercubes, generalized Petersen graphs, Kneser graphs and Johnson graphs.

A computer scientist thinks about the brain

How does the Brain beget the Mind? How do neurons and synapses, molecules and genes, give rise to behavior and cognition, love and sadness, language and intelligence? Despite lightning progress in recording and molecular technology and a deluge of experimental data, we do not seem to get closer to an answer. This is a talk about admiring and appreciating the problem, and proposing a new approach based on a recognized but little studied intermediate level of Brain computation carried out by the synchronous firing of large and highly interconnected sets of neurons called assemblies. We show that assemblies give rise to a novel algebra and calculus, and we speculate that they instrument our higher cognitive functions, such as language and math.

From Data to Less Data to Decisions

The proliferation of “big data" created by mobile devices, social media, sensor networks, satellites etc. offers the potential to make more informed decisions, but it also poses a significant challenge to the scalability of the current optimization methods and decision support tools. This raises a number of fundamental questions: How should uncertain parameters in the big data regime be represented so that they lend themselves to integration into optimization problems? Which observations and features of a high-dimensional parameter set are most relevant for a particular optimization problem? How can these relevant observations and features be identified efficiently? How can one maintain the computational tractability of the emerging optimization problems? In the first part of the talk I will introduce tractable approaches for reducing large datasets to smaller ones at minimal loss of information. In the second part I will describe tractable methods for recognizing balanced clusters of similar datapoints in large unstructured datasets. Both methods come with rigorous performance guarantees. Implications for practical decision-making will be highlighted.