Ball, Marshall; Dachman-Soled, Dana; Loss, Julian (Nondeterministic) hardness vs. non-malleability. (English) Zbl 07694617 Dodis, Yevgeniy (ed.) et al., Advances in cryptology – CRYPTO 2022. 42nd annual international cryptology conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 13507, 148-177 (2022). MSC: 94Bxx 94A60 PDFBibTeX XMLCite \textit{M. Ball} et al., Lect. Notes Comput. Sci. 13507, 148--177 (2022; Zbl 07694617) Full Text: DOI
Leshkowitz, Maya Round complexity versus randomness complexity in interactive proofs. (English) Zbl 1522.68227 Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 49, 16 p. (2018). MSC: 68Q10 68Q15 68W20 PDFBibTeX XMLCite \textit{M. Leshkowitz}, LIPIcs -- Leibniz Int. Proc. Inform. 116, Article 49, 16 p. (2018; Zbl 1522.68227) Full Text: DOI
Carmosino, Marco L.; Impagliazzo, Russell; Sabin, Manuel Fine-grained derandomization: from problem-centric to resource-centric complexity. (English) Zbl 1499.68386 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 27, 16 p. (2018). MSC: 68W20 68Q17 68Q25 PDFBibTeX XMLCite \textit{M. L. Carmosino} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 27, 16 p. (2018; Zbl 1499.68386) Full Text: DOI
Applebaum, Benny; Artemenko, Sergei; Shaltiel, Ronen; Yang, Guang Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. (English) Zbl 1345.68126 Comput. Complexity 25, No. 2, 349-418 (2016). MSC: 68Q05 68Q10 94C10 PDFBibTeX XMLCite \textit{B. Applebaum} et al., Comput. Complexity 25, No. 2, 349--418 (2016; Zbl 1345.68126) Full Text: DOI
Goldreich, Oded In a world of \(\mathrm{P}=\mathrm{BPP}\). (English) Zbl 1343.68084 Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 191-232 (2011). MSC: 68Q15 68W20 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 191--232 (2011; Zbl 1343.68084) Full Text: DOI
Drucker, Andrew A PCP characterization of AM. (English) Zbl 1333.68117 Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 581-592 (2011). MSC: 68Q15 68Q25 PDFBibTeX XMLCite \textit{A. Drucker}, Lect. Notes Comput. Sci. 6755, 581--592 (2011; Zbl 1333.68117) Full Text: DOI
Allender, Eric; Koucký, Michal; Ronneburger, Detlef; Roy, Sambuddha The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. (English) Zbl 1235.68085 J. Comput. Syst. Sci. 77, No. 1, 14-40 (2011). Reviewer: Jacek Błazewicz (Poznań) MSC: 68Q30 PDFBibTeX XMLCite \textit{E. Allender} et al., J. Comput. Syst. Sci. 77, No. 1, 14--40 (2011; Zbl 1235.68085) Full Text: DOI