# Computer Science and Discrete Mathematics (CSDM)

## Efficient reasoning in PAC semantics

## Hypermatrix Algebra, their spectral decomposition and applications

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.

## Communication Lower Bounds via Block Sensitivity

## Learning from positive examples

## Approximating large frequency moments with pick-and-drop sampling

## Matrix perturbation with random noise and matrix recovery problems

## Minimal majority sequences

## Obfuscating Programs Against Algebraic Attacks

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

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.