Tutorial courses will be held on the two days immediately preceding the workshop.
Saturday, April 9, 2016
Afternoon session:
Speaker:
Madhu Sudan
Topic:
Locality in Coding Theory (slides1, slides2)
Abstract:
An error-correcting code is said to be L-locally testable
if given any word it can be determined whether it is close to a codeword or not by sampling only L coordinates of the word.
A code (or more precisely an encoding scheme) is said to be L-locally decodable if given a received word that is close to some codeword,
any single coordinate of the message being encoded can be computed by sampling only L-coordinates of the received word.
When L is much smaller than N, the block length of the code, locally testable and correctible
codes offer reliability associated with N-long codewords while producing decoding delays of only L-long codewords.
In this tutorial I will describe some of the motivations that led to the study of
local codes in theoretical computer science and then describe some basic constructions and
some of the state of the art results (due to Kopparty, Meir, Ron-Zewi and Saraf) that
show codes of sub-polynomial locality (L = N^{o(1)}) close to the Singleton bound.
Sunday, April 10, 2016
Morning session:
Speaker:
Amir Yehudayoff
Topic:
Communication complexity (slides1, slides2)
Abstract:
The plan is to define the basic model of two-party communication complexity,
and the three-party number-on-forehead model. Describe a few protocols and simple lower bound techniques.
Give a brief introduction to information complexity and compression of protocols.
Discuss connections to other areas in theoretical computer science, like distributed computing.
Afternoon session:
Speaker:
Sofya Raskhodnikova
Topic:
Introduction to Property Testing (slides)
Abstract:
Suppose we are given a list of numbers and we wish to determine whether it is sorted in increasing order. Solving this problem obviously requires reading the entire list. However, it turns out that if we know in advance that our list is either sorted or far from sorted, we can distinguish the two cases after reading only a small portion of the list. This is an example of a global property of a dataset that we can understand by making a small number of queries to the input.
What global properties can be understood while reading only a sublinear portion of the input? This question is at the heart of the research area, called Property Testing, that has provided important insights into fast approximate computation.
In this talk, we will define and motivate property testing. Then we will present and analyze several examples of property testers that run in constant or polylogarithmic time in the size of the input. We will look at testing properties of different types of objects, starting with the sorting example, and moving on to geometric properties and properties of functions. We will present simple algorithms with elegant analysis, based on combinatorics, geometry, and probability theory. Time permitting, we will also discuss tolerant testers -- the testers that can distinguish inputs that are close to having the property from inputs that are far from having the property.
Speaker:
Artur Czumaj
Topic:
Testing Graph Properties (slides)
Abstract:
In this talk, we will introduce and survey some basic results and techniques in the framework of graph property testing.
After a brief introduction of the models, we will discuss how graph properties can be efficiently tested in the model of dense graphs.
Then we will move to the model of sparse graphs and present central challenges of very fast testing of graph properties.
Next, we will present several sublinear-time algorithms for some basic graph properties in the model of sparse graphs, including some testing algorithms for planar graphs.
At the end, as an example of the techniques developed, we will also show how the techniques designed to test graph properties can be turned into very efficient combinatorial algorithm for the fundamental problem of estimating the weight of a minimum spanning tree in a graph.