Tuesday May 27

11:30 - 13:00    Jayme Luiz Szwarcfiter "Optimal binary search trees with costs depending on the access paths"
 

14:30 - 16:00     Luca Trevisan "Error-Correcting Codes in Complexity Theory"

16:30 - 18:00     David Peleg "Localized network representations"
 
 

Wednesday May 28

11:30 - 13:00    David Peleg "Localized network representations"

 
 
Abstracts

David Peleg: Localized network representations

The talk will concern compact, localized and distributed network r epresentation methods. Traditional approaches to network representation are based on global data structures, which require access to the entire structure even if the sought information involves only a small and local set of entities. In contrast, localized network representation schemes are based on breaking the information into small local pieces, or labels, selected in a way that allows one to infer information regarding  a small set of entities directly from their labels, without using any additional (global) information. The talk will concentrate mainly on combinatorial and algorithmic techniques, such as adjacency and distance labeling schemes and interval schemes for routing, and will cover a variety of complexity results.

Jayme L. Szwarcfiter: Optimal binary search trees with costs depending on the access paths

We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys, which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees.  The time and space complexity of both algorithms are O(n^{k+2}) and O(n^{k+1}), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys, which are paths of special kinds in binary search trees. Finally, using generating functions, the exact number of steps performed by the algorithms has been calculated. The subject will be introduced by a general discussion on the construction of optimal binary search trees.

Jayme L. Szwarcfiter: On the generation of extensions of a partially ordered set

A partially ordered set (or simply order) P is a set of elements E, together with a set R of relations of E, satisfying reflexivity, anti-symmetry and transitivity. The set E is called the ground set of P, while R is the relation set of it. There are many special orders. For example, when any two elements of E are related, the order is a chain. Similarly, we can define tree orders, forest orders and many others. An extension P´ of P is an order P´ having the same ground set as P, and such that its relation set contains R. When P´ is a chain then P´ is a linear extension of P. Similarly, when P´ is a forest then it is a forest extension of P. We consider the algorithmic problem of generating all extensions of a given order and also extensions of a special kind. The subject will be introduced by a general discussion on partially ordered sets.

Luca Trevisan: Error-Correcting Codes in Complexity Theory

Error-correcting codes and related combinatorial constructs play an important role is several recent (and old) results in complexity theory. This course will give a brief overview of the theory, constructions, algorithms, and applications of error-correcting codes. We will begin with basic definitions and the constructions of Reed-Solomon, Reed-Muller, and low-weight parity-check codes, then see unique-decoding and list-decoding algorithms, and finally, as time allows, applications to secret-sharing, hashing, private information retrieval, average-case complexity and probabilistically checkable proofs.