# Computer Science and Discrete Mathematics (CSDM)

## Pseudorandom Generators for Regular Branching Programs

We shall discuss new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is (either 0 or) 2. For every width d and length n, the pseudorandom generator uses a seed of length $O((log d + log log n + log(1/p)) log n)$ to produce $n$ bits that cannot be distinguished from a uniformly random string by any regular width $d$ length $n$ read-once branching program, except with probability $p > 0$

## Extremal Problems for Convex Lattice Polytopes

In this survey I will present several extremal problems, and some solutions, concerning convex lattice polytopes.

A typical example is to determine the smallest area that a convex lattice polygon can have if it has exactly n vertices.

## Behavioral Experiments in Strategic Networks

## Computational Complexity and Information Asymmetry in Financial Products

Collateralized Default Obligations (CDOs) and related financial derivatives have been at the center of the last financial crisis and subject of ongoing regulatory overhaul.

## A Theory of Cryptographic Complexity

In this talk, I shall describe an ongoing project to develop a complexity theory for cryptographic (multi-party computations. Different kinds of cryptographic computations involve different constraints on how information is accessed. Our goal is to qualitatively -- and if possible, quantitatively -- characterize the "cryptographic complexity" (defined using appropriate notions of reductions) of these different modes of accessing information. Also, we explore the relationship between such cryptographic complexity and computational intractability.

## A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

## Testing Correlations and Inverse Theorems

## Average Sensitivity of Polynomial Threshold Functions

How many edges of the n-dimensional Boolean hypercube can be sliced by a degree-d polynomial surface? This question can be equivalently stated as "What is the maximum average sensitivity of any degree-d polynomial threshold function?" In 1994 Gotsman and Linial posed this question and gave a conjectured answer: the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d polynomial threshold functions.

## Complexity of Constraint Satisfaction Problems: Exact and Approximate

Is there a common explanation for 2SAT being solvable polynomial time, and Max2SAT being approximable to a 0.91 factor? More generally, it is natural to wonder what characterizes the complexity of exact constraint satisfaction problems (CSP) like 2SAT and what determines the approximation ratios for MaxCSPs like Max2SAT.