Videos
Communication with Imperfectly Shared Randomness
Communication with Imperfectly Shared Randomness
Madhu Sudan
01:11:06 · 8 October 2014

A common feature in most natural communication is that it relies on a large shared context between speaker and listener, where the context is shared vaguely rather than precisely. Knowledge of language, technical terms, socio-political events, history etc. all combine to form this shared context; and it should be obvious that no one can expect any part of this context to be shared perfectly by the two parties. This shared context helps in compressing communication (else I would have to include an English dictionary, a book on grammar etc. to this abstract); but the imperfection of the sharing potentially leads to misunderstanding and ambiguity. The challenge of achieving the benefits provided by the shared context without leading to new errors due to the imperfection leads to a host of new mathematical questions. In this talk we will focus on one specific setting for this tension between shared context and imperfection of sharing, namely in the use of shared randomness in communication complexity. It is widely known that shared randomness between speaker and listener can lead to immense savings in communication complexity for certain communication tasks. What happens when this randomness is not perfectly shared? We model this as saying that sender has access to a sequence of uniform random bits and receiver has access to a noisy version of the same sequence where each bit is flipped independently with some probability p. While most known communication protocols fail when the randomness is imperfectly shared, it turns out that many of the effects of shared randomness can be recovered with a slight loss by more carefully designed protocols. Among other results we will describe a general one which shows that any k-bit one-way communication protocol with perfectly shared randomness can be 'simulated' with 2k bits of imperfectly shared randomness, and this is essentially tight. Based on joint work with Clément Canonne (Columbia), Venkatesan Guruswami (CMU), and Raghu Meka ().

P: A Domain-Specific Language for Asynchronous Event-Driven Programming
P: A Domain-Specific Language for Asynchronous Event-Driven Programming
Shaz Qadeer
01:00:08 · 24 August 2014

Asynchrony is fundamental to a broad class of software systems such as device drivers, cloud infrastructure, interacting web services, and client-server web applications. These software systems exhibit reactive and concurrent execution whose control requires carefully designed and implemented protocols. Traditional programming languages provide little support to specify and validate protocols. To address this gap, we have developed a domain-specific language called P for specification, implementation, and validation of protocols in asynchronous software. P is being used inside Microsoft in Windows and Windows Phone for developing device drivers; the USB device driver stack that ships with Windows and Windows Phone is implemented in P. In this talk, I will present the design and implementation of the language features and the systematic testing framework of P. I will also touch upon our current work extending P for programming fault-tolerant distributed services.

Sampling Techniques for Constraint Satisfaction and Beyond
Sampling Techniques for Constraint Satisfaction and Beyond
Kuldeep Meel
01:01:46 · 21 August 2014

Constraint problems have played a key role in diverse areas spanning testing, formal verification, planning, inferencing and the like. Apart from the classical problem of checking satisfiability, the problems of generating satisfying assignments randomly and of counting the total number of satisfying assignments have also attracted significant theoretical and practical interest over the years. Prior work offered heuristic approaches with no guarantee of solution distribution, and approaches with proven guarantees, but poor performance in practice. In this talk, I will describe a novel approach based on limited independent hashing and present two practical algorithms, UniGen and WeightMC, for solving these two fundamental problems. Unlike prior work, our algorithms provide strong theoretical guarantees and also scale to large problem sizes.

Culture-Aware Approaches to Music Information Research
Culture-Aware Approaches to Music Information Research
Gopala Krishna Koduri
01:01:49 · 7 August 2014

Music traditions from around the world share a few common characteristics. Yet, they differ substantially when viewed within their geographical and cultural context. Yet, our data-, cognition-, interaction-, user-models and ontologies do not cater to this diversity. CompMusic project (http://compmusic.upf.edu/) aims to address this by advancing the field of music information research placing emphasis on culture-aware approaches to music description. The first of the two parts of the talk will give an overview of the work being done in the project. The second part of the talk is about my ongoing thesis work, which draws upon multi-modal data sources concerning art music traditions, extracting culturally relevant and musically meaningful information from each of them and structuring it with formal knowledge representations. As part of this, information extraction methods that are sensitive to the culture-specificities of the given music are proposed. Due to the complementary nature of the data sources, structuring and linking the information extracted from them results in a symbiotic link, mutually enriching their information. Over this multi-modal knowledge base, relatedness measures for the discovery of musical entities are proposed, yielding a culturally-sound navigation space.

Measurement Campaigns for Spectrum Occupancy
Measurement Campaigns for Spectrum Occupancy
Sumit Roy
01:02:01 · 2 July 2014

The evolution of cognitive (secondary) networks to enable more efficient spectrum usage will rely on fast and accurate spectrum sensing/mapping, supported by a suitable architecture for data integration and model building. In the first part of the talk, fundamental aspects of the wide-area RF mapping problem as a grand challenge will be highlighted; and some recent work at UW that clarifies sub-system level trade-offs (between scan latency and channel status estimation accuracy, for example) will be described. Next, the evolution of a hybrid architecture - decentralized client-side sensing assisted database updating - is explored. Within this, model-based answers to fundamental questions such as 'how much white space capacity is available' as a function of location for U.S. TV bands are developed. The talk will conclude with a description of current efforts for spectrum sharing (co-existence) just underway in the 3 GHz band (broadly) between different primaries (largely government operated communications such as military and non-military radars) and commercial networks (802.11 and 4G LTE).

White Space Networking and Spectrum Sharing - Part 2
White Space Networking and Spectrum Sharing - Part 2
Sumit Roy
01:16:00 · 2 July 2014

The evolution of cognitive (secondary) networks to enable more efficient spectrum usage will rely on fast and accurate spectrum sensing/mapping, supported by a suitable architecture for data integration and model building. In the first part of the talk, fundamental aspects of the wide-area RF mapping problem as a grand challenge will be highlighted; and some recent work at UW that clarifies sub-system level trade-offs (between scan latency and channel status estimation accuracy, for example) will be described. Next, the evolution of a hybrid architecture - decentralized client-side sensing assisted database updating - is explored. Within this, model-based answers to fundamental questions such as 'how much white space capacity is available' as a function of location for U.S. TV bands are developed. The talk will conclude with a description of current efforts for spectrum sharing (co-existence) just underway in the 3 GHz band (broadly) between different primaries (largely government operated communications such as military and non-military radars) and commercial networks (802.11 and 4G LTE).

Peter Lee Address to Summer School 2014 Attendees
Peter Lee Address to Summer School 2014 Attendees
Peter Lee
00:44:10 · 1 July 2014

Software defined radios are a powerful tool for experimenting with wireless PHY and MAC layers. At the same time, they are a challenging programming environment, given tight timing constraints imposed. A student who wants to venture in this area of research needs to master computer architecture and hardware, as well as numerous algorithms for signal processing and communication. In this lecture we will talk about Ziria, a programming language and a compiler that we have recently developed to simplify this task. Ziria is a high-level language, specialized for PHY design, that delegates most of the burdensome hardware optimization to the compiler and allows us to keep the code design clean and simple. We will walk through various building blocks of Wifi PHY design and show how to implement them in Ziria. At the end of the talk you should be able to understand the signal processing foundations of WiFi as well as to quickly implement and deploy your own PHY using Ziria. Ziria compiler is open sourced so you will be able to download it and play with the code yourselves. It currently supports Sora SDR platform but could be easily adapted to other similar platforms.

Ziria: Wireless Programming for Hardware Dummies - Part 4
Ziria: Wireless Programming for Hardware Dummies - Part 4
Bozidar Radunovic
01:01:39 · 1 July 2014

Software defined radios are a powerful tool for experimenting with wireless PHY and MAC layers. At the same time, they are a challenging programming environment, given tight timing constraints imposed. A student who wants to venture in this area of research needs to master computer architecture and hardware, as well as numerous algorithms for signal processing and communication. In this lecture we will talk about Ziria, a programming language and a compiler that we have recently developed to simplify this task. Ziria is a high-level language, specialized for PHY design, that delegates most of the burdensome hardware optimization to the compiler and allows us to keep the code design clean and simple. We will walk through various building blocks of Wifi PHY design and show how to implement them in Ziria. At the end of the talk you should be able to understand the signal processing foundations of WiFi as well as to quickly implement and deploy your own PHY using Ziria. Ziria compiler is open sourced so you will be able to download it and play with the code yourselves. It currently supports Sora SDR platform but could be easily adapted to other similar platforms.

Ziria: Wireless Programming for Hardware Dummies - Part 3
Ziria: Wireless Programming for Hardware Dummies - Part 3
Bozidar Radunovic
00:58:21 · 1 July 2014

Software defined radios are a powerful tool for experimenting with wireless PHY and MAC layers. At the same time, they are a challenging programming environment, given tight timing constraints imposed. A student who wants to venture in this area of research needs to master computer architecture and hardware, as well as numerous algorithms for signal processing and communication. In this lecture we will talk about Ziria, a programming language and a compiler that we have recently developed to simplify this task. Ziria is a high-level language, specialized for PHY design, that delegates most of the burdensome hardware optimization to the compiler and allows us to keep the code design clean and simple. We will walk through various building blocks of Wifi PHY design and show how to implement them in Ziria. At the end of the talk you should be able to understand the signal processing foundations of WiFi as well as to quickly implement and deploy your own PHY using Ziria. Ziria compiler is open sourced so you will be able to download it and play with the code yourselves. It currently supports Sora SDR platform but could be easily adapted to other similar platforms.

White Space Networking and Spectrum Sharing
White Space Networking and Spectrum Sharing
Sumit Roy
02:07:18 · 30 June 2014

The evolution of cognitive (secondary) networks to enable more efficient spectrum usage will rely on fast and accurate spectrum sensing/mapping, supported by a suitable architecture for data integration and model building. In the first part of the talk, fundamental aspects of the wide-area RF mapping problem as a grand challenge will be highlighted; and some recent work at UW that clarifies sub-system level trade-offs (between scan latency and channel status estimation accuracy, for example) will be described. Next, the evolution of a hybrid architecture - decentralized client-side sensing assisted database updating - is explored. Within this, model-based answers to fundamental questions such as 'how much white space capacity is available' as a function of location for U.S. TV bands are developed. The talk will conclude with a description of current efforts for spectrum sharing (co-existence) just underway in the 3 GHz band (broadly) between different primaries (largely government operated communications such as military and non-military radars) and commercial networks (802.11 and 4G LTE).

More videos...