Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

On minimizers and critical points for anisotropic isoperimetric problems

Robin Neumayer
Member, School of Mathematics
February 19, 2019

Anisotropic surface energies are a natural generalization of the perimeter functional that arise in models in crystallography and in scaling limits for certain probabilistic models on lattices. This talk focuses on two results concerning isoperimetric problems with anisotropic surface energies. In the first part of the talk, we will discuss a weak characterization of critical points in the anisotropic isoperimetric problem (joint work with Delgadino, Maggi, and Mihaila). 

Interactive Coding Over the Noisy Broadcast Channel

Gillat Kol
Princeton University
February 11, 2019

A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? 

This problem was first suggested by El Gamal in 1984. In 1988, Gallager gave an elegant noise-resistant protocol requiring only

Non-commutative rank

Visu Makam
University of Michigan; Member, School of Mathematics
February 5, 2019

A linear matrix is a matrix whose entries are linear forms in some indeterminates $t_1,\dots, t_m$ with coefficients in some field $F$. The commutative rank of a linear matrix is obtained by interpreting it as a matrix with entries in the function field $F(t_1,\dots,t_m)$, and is directly related to the central PIT (polynomial identity testing) problem. The

Near-Optimal Strong Dispersers

Dean Doron
The University of Texas at Austin
February 4, 2019

Randomness dispersers are an important tool in the theory of pseudorandomness, with numerous applications. In this talk, we will consider one-bit strong dispersers and show their connection to erasure list-decodable codes and Ramsey graphs. 

PCP and Delegating Computation: A Love Story.

Yael Tauman Kalai
Microsoft Research
January 28, 2019

In this talk, I will give an overview on how PCPs, combined with cryptographic tools,
are used to generate succinct and efficiently verifiable proofs for the correctness of computations.
I will focus on constructing (computationally sound) *succinct* proofs that are *non-interactive*
(assuming the existence of public parameters) and are *publicly verifiable*.
In particular, I will focus on a recent result with Omer Paneth and Lisa Yang,
where we show how to construct such proofs for all polynomial time computations,

New Results on Projections

Guy Moshkovitz
Member, School of Mathematics
January 22, 2019

What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n? This fundamental question is intimately connected to important topics and results in combinatorics and computer science (Turan number, Sauer-Shelah Lemma, Kahn-Kalai-Linial Theorem, and more), and is wide open for most settings of the parameters. We essentially settle the question for linear k and sub-exponential m. 

Based on joint work with Noga Alon and Noam Solomon.

A matrix expander Chernoff bound

Ankit Garg
Microsoft Research
December 10, 2018
Chernoff-type bounds study concentration of sums of independent random variables and are extremely useful in various settings. In many settings, the random variables may not be completely independent but only have limited independence. One such setting, which turns out to be useful in derandomization and theoretical computer science, in general, involves random walks on expanders. I will talk about a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander.