Works by Ján Pich

( view other items matching `Ján Pich`, view all matches )
Order:
  1.  24
    Feasibly constructive proofs of succinct weak circuit lower bounds.Moritz Müller & Ján Pich - 2020 - Annals of Pure and Applied Logic 171 (2):102735.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  10
    Circuit lower bounds in bounded arithmetics.Ján Pich - 2015 - Annals of Pure and Applied Logic 166 (1):29-45.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  19
    Nisan-Wigderson generators in proof systems with forms of interpolation.Ján Pich - 2011 - Mathematical Logic Quarterly 57 (4):379-383.
    We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation