My research statements for MFO workshop on complexity

Starting 2012, the organizers of this workshop asked all participants to provide brief statements of their research in recent years. I cannot locate my 2012 statement, but here are the later ones.

For November 2015

In the last few years, while continuing to conduct research on property testing, I became involved in research on AC0. It started with my work with Avi Wigderson on the size of depth-three Boolean circuits for computing multilinear functions, which later led to work with Avishay Tal on matrix rigidity of random Toeplitz matrices. Another direction pursued with Avi is the derandomizing of algorithms that err extremely rarely, which had a main component regarding AC0 and AC0[2], and led to a study of randomness extraction in AC0 (with Avi and Emanuele Viola).

For November 2018

Starting Summer 2015, I was working on an introductory book on Property Testing, which I completed by April 2017. It was published in November 2017. Research-wise, my focus was on property testing as well as on doubly-efficient interactive proof systems and worst-case to average-case reductions for problems in P. By doubly-efficient interactive proof systems we mean interactive proofs in which the (prescribed) prover strategy runs in polynomial-time, whereas the verifier runs in almost linear time (or much faster than the decision procedure known for the set). Developments in the study of such proof systems seems to occur alongside developments in the study of worst-case to average-case reductions. Is this a coincidence? Guy has an opinion.

Back to Oded Goldreich's homepage.