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, 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.