3/1/12 Raef Bassily, A cryptographic treatment of the wiretap channel: An optimal, explicit, and efficient encryption
Abstract: In this talk, I will present the recent work of M. Bellare, S.Tessaro, and A. Vardy where they establish important results that bridge some gaps between the information-theoretic and cryptographic perspectives to the security problem in the context of wiretap channels. I will also present a subsequent work of Bellare and Tessaro where they provide the first explicit polynomial-time construction of an encryption scheme that attains the secrecy capacity of a class of wiretap channels under a security definition that is shown to be stronger than the standard one in the information-theoretic security literature.

In particular, the following contributions are made:
First, new, strong definitions of security in the wiretap model are suggested. One, called MIS (mutual information security), is an extension of a weaker definition called MIS-R (mutual information security for random messages) which is the one in current use in the information theory community. Another, called SS (semantic security), adapts a definition of security that is well-understood in the cryptography community, vetted by decades of cryptographic research and targeted by standards deployed in practice. Next, it is shown that MIS and SS definitions are indeed equivalent.

3/8/12 Vinay A. Vaishampayan (AT&T Labs), Query Matrices for the Hamming Oracle

Abstract: x is an unknown binary string of length n. In response to an n-bit query y, the Hamming oracle returns the Hamming distance d(x,y). The problem is to construct a set of queries that allow us to determine x based on the query results. All queries must be set up in advance, i.e. queries are not allowed to depend on the response of the oracle to preceding queries. Our figure of merit is the query ratio, i.e. the ratio of the number of queries to the length of the string.

Connections to the distinct-subset-sum problem and to other more widely known problems will be explored. Bounds on the achievable query ratio as a function of the string length n will be derived. An algebraic construction will be presented along with a decoding algorithm, and it will be shown that query ratios arbitrarily close to zero can be achieved.
 

3/15/12 Raef Bassily, cont'd

3/22/12 Spring break

3/29/12 Yuval Lomnitz (Tel Aviv University), Universal communication over unknown channels (with feedback)
Abstract: A communication problem over an unknown channel is discussed. Two main settings are presented. In the "individual channel" setting, there is no model for the channel, and information rates are defined as a function of the channel input sequence and channel output sequence,
i.e. "what really happened". The range of rate-functions, defining the rate as a function of the inputs and outputs is explored. In the "unknown vector channel" setting, the channel has a vector-wise probabilistic model, defining the probability of every output sequence given every input sequence (not necessarily stationary), however this probability is unknown to the transmitter and the receiver. Using low rate feedback, and common randomness, the goal is to approach the same rates that would be obtained by someone knowing the channel, but constrained in encoding and decoding complexity.

4/5, 4/12  David Ward (UMD) Introduction to Team Decision Problems
Abstract: In this introduction to team decision problems, static team decision problems will be discussed and it will be proven that under
quadratic costs the Bayes team decision function is obtained as a projection. Under the further assumptions of jointly Gaussian distributions
on the information variables and additional assumptions on the cost function, the Bayes team decision function will be shown to be linear in the
information variables. This discussion will follow Team Decision Problems by Radner.

Also, partially nested information patterns will be discussed. It will be shown that under the assumption of a linear information pattern, partially
nested information patterns are the only ones equivalent to static information patterns.
 

4/19, 4/26 Maya Kabkab (UMD) Equilibrium selection in repeated coordination games
Abstract: In this talk I will discuss equilibrium selection in repeated coordination games. I will begin by formally defining what a pure
coordination game means, and provide examples. We will then allow a coordination game, with binary choices, to be played repeatedly by
identical players. We will be interested in the long-run behavior of the fraction of players playing each action. The equilibrium selection
criteria will be formally characterized for the different dynamics we will consider. The discussion will follow Equilibrium Selection in n-Person Coordination Games by Youngse Kim.

5/3 Anup Menon (UMD) Cheeger Inequality and it's implications in the study of Expander Families of Graphs

Abstract: We motivate the study of expanders with a couple of examples relevant to us. We define a combinatorial quantity called edge expansion of a graph and give the combinatorial definition of expander families. The main result that we  discuss is Cheeger's inequality. It is a relationship between edge expansion and spectral properties of the graph adjacency matrix for regular graphs and leads to a spectral characterisation of expander families. We follow Luca Trevisan's lecture notes 3 and 4:  http://theory.stanford.edu/~trevisan/cs359g/