Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Interactive Channel Capacity

Gillat Kol
Institute for Advanced Study; Member, School of Mathematics
November 19, 2013
In a profoundly influential 1948 paper, Claude Shannon defined the entropy function H, and showed that the capacity of a symmetric binary channel with noise rate (bit flip rate) eps is 1−H(eps). This means that one can reliably communicate n bits by sending roughly n/(1−H(eps)) bits over this channel. The extensive study of interactive communication protocols in the last decades gives rise to the related question of finding the capacity of a noisy channel when it is used interactively.

Efficient reasoning in PAC semantics

Brendan Juba
Harvard University
November 18, 2013
Machine learning is often employed as one step in a larger application, serving to perform information extraction or data mining for example. The rules obtained by such learning are then used as inputs to a further analysis. As a consequence of the inputs to this analysis having been learned, however, its conclusions can only be theoretically guaranteed to satisfy the same standard as the inputs---that of "PAC Semantics" (Valiant, 2000).

Hypermatrix Algebra, their spectral decomposition and applications

Edinah Gnang
Institute for Advanced Study; Member, School of Mathematics
November 12, 2013

In this talk we will present an overview of the hypermatrix generalization of matrix algebra proposed by Mesner and Bhattacharya in 1990. We will discuss a spectral theorem for hypermatrices deduced from this algebra as well as connections with other tensor spectral decompositions. Finally if time permits we will discuss some applications and related open problems.

Obfuscating Programs Against Algebraic Attacks

Yael Tauman-Kalai
Microsoft Research New England
October 14, 2013

The goal of (general-purpose) program obfuscation is to make an arbitrary computer program "unintelligible" while preserving its functionality. The problem of program obfuscation is well studied both in theory and in practice. Though despite its importance, until very recently, even heuristic constructions for general-purpose obfuscation were not known.

Rounding Moment Based SDP Relaxations by Column Selection

Ali Kemal Sinop
Institute for Advanced Study; Member, School of Mathematics
October 8, 2013

In this lecture, I will talk about moment based SDP hierarchies (which are duals of SOS relaxations for polynomial optimization) in the context of graph partitioning. The focus will be on a certain way of rounding such hierarchies, whose quality is related to the problem of column based matrix reconstruction. Finally I will describe how to relate this to the spectral or isoperimetric profiles of the underlying constraint graph.