DIMACS
DIMACS REU 2016

General Information

me
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

Second Week

Third Week

Fourth Week

Fifth Week

Sixth Week

Seventh Week


Main Complexity Group

Whole Czech Team

Presentations


Additional Information

Our Mentor
  • Professor Eric Allender
        https://www.cs.rutgers.edu/~allender/