||Charles University in Prague
||The Minimum Circuit Size Problem: A possible NP-Intermediate Problem
We are interested in relations of the Minimum Circuit Size Problem (MCSP) to other not
yet classificated problems and classes. We are also interested in connections between
MCSP, Kolmogorov random strings and statistical zero knowledge (SZK) proofs.
- We are trying to decide which particular problem will be suitable for us.
- We read some articles about MCSP and about pseudorandom generators.
- Michael is investigating where does the graph authomorphism problem belong.
- We have met with our mentor Eric Allender and we have learned a lot of insights in nonuniform classes.
- We are finishing reading the paper about pseudorandom generators from one-way functions.
- We have tryed to tamper with some proofs from the paper Power from Random Strings by
Dieter van Melkebeek,
Detlef Ronneburger and Natural Proofs by Alexander A. Razborov and
- We are also discussing the progres with Michael.
- We have gone through the HILL paper with NC1.
- We are dealing with compositions and trying to get a pseudorandom (function) generator.
- Michal Koucký told us about the construction of Nisan-Wigderson that might help us.
- We are still working on the idea of Nisan-Wigderson.
- The idea of Nisan-Wigderson does not seem to be altered to suit our needs.
- We are trying to generalize the construction of Naor Reingold.
- None of the existing constructions seems really useful for our problem.
- We have also thought about a different problem assigned to us in Prague.
- Our mentor suggested another problem that we might try. We reading up on
- Our idea for the Prague problem using matrix multiplication turned out to
- We are trying to understand the structure of the gap-MSCP and how it can
be used to replace randomness.
- There is a very interesting conference taking
place at DIMACS from Monday to Wednesday. We plan to see as much as will be
possible because many authors of papers we have read will be there presenting.
- We have been to many very interesting and relevant talks at the
- We are preparing the final presentation and summarizing what we have
Main Complexity Group
Whole Czech Team
Professor Eric Allender