General Information
| Student: | Veronika Slívová |
|---|---|
| Office: | 442 |
| School: | Charles University in Prague |
| Project: | The Minimum Circuit Size Problem: A possible NP-Intermediate Problem |
Project Description
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.Previous Work
Weekly Log
First Week
- 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.
Second Week
- 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 Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger and Natural Proofs by Alexander A. Razborov and Steven Rudich.
- We are also discussing the progres with Michael.
Third Week
- 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.
Fourth Week
- 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.
Fifth Week
- 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 it.
Sixth Week
- Our idea for the Prague problem using matrix multiplication turned out to be flawed.
- We are trying to understand the structure of the gap-MSCP and how it can be used to replace randomness.
Seventh Week
- 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 conference.
- We are preparing the final presentation and summarizing what we have done.
Main Complexity Group
Whole Czech Team
Presentations
Additional Information
Our Mentorhttps://www.cs.rutgers.edu/~allender/