Boris Aronov - Polytechnic University, New York

Incidences problems: some history and new developments

Abstract: We discuss the so-called "incidence" problem in which one is interested in the maximum number of incidences possible between a set of points and a set of curves in two and higher dimensions.

We start with the history of the simplest and best known version of the problem, namely that of lines and points in the plane. We discuss several methods used for solving these problems and their applicability in other contexts. The state of the art has evolved to the point where the original question has a "one-line" solution, but several extensions remain quite challenging and open. We describe the tools needed to construct upper bounds for lines and cirles, in dimensions two and higher.

Colloquium - 16:00

Carola Wenk - University of Arizona

Software Watermarking

Abstract: Watermarking is the art of embedding a secret message (the "watermark") into an object such that the existence of the secret message is concealed, and the watermark is hard to detect, but with a secret key it can easily be retrieved. This has wide-ranging applications in the protection of intellectual property of digital media or software products. A popular example which has received lots of attention in the literature is that of media watermarking: One sophisticated way to protect the copyright of a digital image for example is to hide a copyright notice in it (which is usually done by taking advantage of the limits of the human visual system). This way all copies are also invisibly marked, such that illegal copies can be detected by retrieving the hidden copyright notice which proves the ownership.

However, being aware of a possibly hidden watermark an adversary could try to alter the image in such a way that the image itself is still useful, however the watermark is for example too scrambled to be retrieved. Therefore watermarking techniques have to be resilient to a diversity of possible adversarial attacks.

We give an introduction to the recently emerged field of software watermarking. Here the task is to protect software by hiding copyright information directly in the source code. We discuss different threat models and two fundamental classes of software watermarks: Static and dynamic software watermarks. In particular we present the recent direction of dynamic graph watermarks, which are incorparted in the watermarking software "Sandmark" by Collberg and Townsend -- see http://www.cs.arizona.edu/sandmark/ for downloads and documentation.