School of Mathematics
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.
Given an arbitrary graph, we show that if we are allowed to modify (say) 1% of the edges then it is possible to obtain a much smaller regular partition than in Szemeredi's original proof of the regularity lemma. Moreover, we show that it is impossible to improve upon the bound we obtain.
We prove that the systole (or more generally, any k-th
homology systole) of a minimal surface in an ambient three manifold of
positive Ricci curvature tends to zero as the genus of the minimal
surfaces becomes unbounded. This is joint work with Anna Siffert.
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,