DIMACS
DIMACS REU 2016

General Information

me
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

Presentations


Additional Information

Our Mentor
  • Professor Eric Allender
        https://www.cs.rutgers.edu/~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.