Keynote Speakers

Dynamic Random Geometric Graphs

Josep Diaz, Universitat Politecnica de Catalunya

Random geometric graphs have been one of the most reliable models to simulate wireless networks. In the present talk, after reviewing the basic results for the stating setting, we propose a model for mobility, based on the random walk model. We will survey some results about connectivity and connectivity threshold and pose some open problems.

Computational Awareness

Lance Fortnow, Northwestern University

What are we aware of? More than a philosophical pursuit, awareness plays a crucial role in decision making as one cannot make a choice that one is not aware of. Billions of advertising dollars are spent in increasing the awareness of their brands. Most work on awareness has focused on logical/axiomatic approaches (for example you are aware of something if you know it or you know you don't know it). Instead we put awareness through a computational lens, roughly defining the unawareness of an object as the amount of time it takes to enumerate that object given the current environment. For example, if you want to buy a car, the ones you are most aware of are those which come earlier if you attempted to start enumerating cars. Based on Levin's universal enumeration, we give a formal definition of unawareness using this intuition. The formal definition uses a universal enumeration as good as any other computable enumeration up to constant factors. Our definition differs from earlier approaches as we talk about the awareness of strings as opposed to the truth of some statement and gives a quantitative measure of unawareness instead of just a binary awareness/unawareness choice. We will give some observations on how newer technologies, like search engines, have affected our awareness of various information, and how we can become unaware of objects we were once aware of. We discuss a couple of applications: - Why do loopholes occur in laws and contracts? We give an explanation based on the lack of awareness of the legislators of future circumstances and of the judge's unawareness of what the legislature's awareness. - We give a new view of sponsored search auctions based on awareness and show new bidding strategies when the advertisers wish to increase awareness of their products. This talk will cover mostly very preliminary research parts of which represent work with Kim-Sau Chung and Nikhil Devanur.