General Information

Student: Karel Král
Office: 444
School: Charles University in Prague
E-mail: kralka guess_what_is_here kam.mff.cuni.cz
Project: The Minimum Circuit Size Problem: A possible NP-Intermediate Problem
Previous Projects: DIMACS REU 2013, DIMACS REU 2014

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


Additional Information

Our Mentor
  • Professor Eric Allender
  • Funded by

    EU Flag
    The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 616787.