×

Found 7 Documents (Results 1–7)

(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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

Filter Results by …

Document Type

Year of Publication

Main Field