4 found
Order:
  1.  5
    Expander Construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
    We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the “NC^1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC^1 . This in turn implies that every proof in Gentzen's sequent calculus LK of a (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2.  9
    What Can Be Efficiently Reduced to the Kolmogorov-Random Strings?Eric Allender, Harry Buhrman & Michal Koucký - 2006 - Annals of Pure and Applied Logic 138 (1):2-19.
    We investigate the question of whether one can characterize complexity classes in terms of efficient reducibility to the set of Kolmogorov-random strings . This question arises because and , and no larger complexity classes are known to be reducible to in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. What follows is a list of some of our main results.• Although (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  3.  9
    Agreement on Intrapartum Cardiotocogram Recordings Between Expert Obstetricians.Lukáš Hruban, Jiří Spilka, Václav Chudáček, Petr Janků, Michal Huptych, Miroslav Burša, Adam Hudec, Marian Kacerovský, Michal Koucký, Martin Procházka, Vladimír Korečko, Jan Seget'A., Ondřej Šimetka, Alena Měchurová & Lenka Lhotská - 2015 - Journal of Evaluation in Clinical Practice 21 (4):694-702.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  5
    Isaac Newton Institute, Cambridge, UK July 2–6, 2012.George Barmpalias, Vasco Brattka, Adam Day, Rod Downey, John Hitchcock, Michal Koucký, Andy Lewis, Jack Lutz, André Nies & Alexander Shen - 2013 - Bulletin of Symbolic Logic 19 (1).
    Direct download  
     
    Export citation  
     
    Bookmark