Events

Boneh-Boyen signatures and the Strong Diffie-Hellman problem

Abstract:

The Boneh-Boyen digital signature scheme is a pairing based short signature scheme which is provably secure in the standard model under the $q$-Strong Diffie-Hellman assumption.

Verifiable sufficient conditions in Compressed Sensing

Abstract:

Compressed Sensing is a rapidly developing novel area in Signal Processing aimed at recovering sparse high-dimensional signals from their low-dimensional linear images, or, which is the same, recovering sparse solutions to heavily underdeter

Computational Complexity of Translationally-Invariant Systems

Abstract:

In general, it is a computationally hard problem to determine whether a two-dimensional grid can be tiled using some set of rules on what kinds of tiles can be adjacent.

Scheduling, Percolation, and the Worm Order

Abstract:

We show that in any submodular system there is a maximal chain that is minimal, in a very strong sense, among all paths from 0 to 1. The consequence is a set of general conditions under which parallel scheduling can be done without backward steps.

Load balancing and random graphs

Abstract:

Many problems involve assigning a set of jobs to a set of processors (i.e. things that can deal with the jobs). Load balancing becomes involved if we wish to assign the jobs such that, roughly speaking, all processors are kept equally busy.

Sign in: Breakfast and sign in will be on Monday at 8:30 AM in William G. Davis Computer Research Centre (DC) 1301 (The Fishbowl).

Primary speaker: Carsten Thomassen, Technical University of Denmark

Binary matroid minors

Abstract:

In recent work with Bert Gerards and Geoff Whittle, we have extended significant parts of the graph minors project of Robertson and Seymour to binary matroids. This talk is intended as a gentle overview of this work.

On Generalizations of Network Design Problems with Degree Bounds

Abstract:

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems.

Awful Graphs

Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization

Abstract:

The sensor network localization (SNL) problem consists of locating the positions of ad hoc wireless sensors, given only the distances between sensors that are within radio range and the positions of