Sherstov, Alexander A.; Storozhenko, Andrey A.; Wu, Pei An optimal separation of randomized and quantum query complexity. (English) Zbl 07680600 SIAM J. Comput. 52, No. 2, 525-567 (2023). MSC: 68Q12 68Q17 68Q15 81P45 PDFBibTeX XMLCite \textit{A. A. Sherstov} et al., SIAM J. Comput. 52, No. 2, 525--567 (2023; Zbl 07680600) Full Text: DOI arXiv
Pass, Rafael Unprovable security of perfect NIZK and non-interactive non-malleable commitments. (English) Zbl 1369.94562 Comput. Complexity 25, No. 3, 607-666 (2016). MSC: 94A60 68Q15 PDFBibTeX XMLCite \textit{R. Pass}, Comput. Complexity 25, No. 3, 607--666 (2016; Zbl 1369.94562) Full Text: DOI
Dachman-Soled, Dana; Mahmoody, Mohammad; Malkin, Tal Can optimally-fair coin tossing be based on one-way functions? (English) Zbl 1323.94108 Lindell, Yehuda (ed.), Theory of cryptography. 11th theory of cryptography conference, TCC 2014, San Diego, CA, USA, February 24–26, 2014. Proceedings. Berlin: Springer (ISBN 978-3-642-54241-1/pbk). Lecture Notes in Computer Science 8349, 217-239 (2014). MSC: 94A60 68Q15 PDFBibTeX XMLCite \textit{D. Dachman-Soled} et al., Lect. Notes Comput. Sci. 8349, 217--239 (2014; Zbl 1323.94108) Full Text: DOI
Pass, Rafael Limits of provable security from standard assumptions. (English) Zbl 1288.94080 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 109-118 (2011). MSC: 94A60 68Q15 68Q17 68Q87 PDFBibTeX XMLCite \textit{R. Pass}, in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 109--118 (2011; Zbl 1288.94080) Full Text: DOI
Goldreich, Oded; Sudan, Madhu; Trevisan, Luca From logarithmic advice to single-bit advice. (English) Zbl 1343.68080 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, 109-113 (2011). MSC: 68Q05 68Q10 68Q15 PDFBibTeX XMLCite \textit{O. Goldreich} et al., Lect. Notes Comput. Sci. 6650, 109--113 (2011; Zbl 1343.68080) Full Text: DOI
Gavinsky, Dmitry; Sherstov, Alexander A. A separation of NP and conp in multiparty communication complexity. (English) Zbl 1213.68293 Theory Comput. 6, Paper No. 10, 227-245 (2010). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{D. Gavinsky} and \textit{A. A. Sherstov}, Theory Comput. 6, Paper No. 10, 227--245 (2010; Zbl 1213.68293) Full Text: DOI
Beame, Paul; Pitassi, Toniann An exponential separation between the parity principle and the pigeonhole principle. (English) Zbl 0866.03029 Ann. Pure Appl. Logic 80, No. 3, 195-228 (1996). MSC: 03F20 68Q15 68Q25 PDFBibTeX XMLCite \textit{P. Beame} and \textit{T. Pitassi}, Ann. Pure Appl. Logic 80, No. 3, 195--228 (1996; Zbl 0866.03029) Full Text: DOI
Bruschi, Danilo Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets. (English) Zbl 0755.68050 Theor. Comput. Sci. 102, No. 2, 215-252 (1992). Reviewer: U.Schöning (Ulm) MSC: 68Q15 03D15 PDFBibTeX XMLCite \textit{D. Bruschi}, Theor. Comput. Sci. 102, No. 2, 215--252 (1992; Zbl 0755.68050) Full Text: DOI
Li, Xiang Relationships between polynomial-time random and exponential-time deterministic complexity classes. (English) Zbl 0779.68034 Found. Comput. Decis. Sci. 17, No. 2, 109-128 (1992). Reviewer: M.Zimand (Bucureşti) MSC: 68Q15 PDFBibTeX XMLCite \textit{X. Li}, Found. Comput. Decis. Sci. 17, No. 2, 109--128 (1992; Zbl 0779.68034)
Beigel, Richard Relativized counting classes: Relations among thresholds, parity, and mods. (English) Zbl 0717.68031 J. Comput. Syst. Sci. 42, No. 1, 76-96 (1991). Reviewer: J.Hromkovic MSC: 68Q15 68Q10 PDFBibTeX XMLCite \textit{R. Beigel}, J. Comput. Syst. Sci. 42, No. 1, 76--96 (1991; Zbl 0717.68031) Full Text: DOI
Cai, Jin-yi; Hemachandra, Lane A. On the power of parity polynomial time. (English) Zbl 0718.68038 Math. Syst. Theory 23, No. 2, 95-106 (1990). MSC: 68Q15 03D15 68Q05 PDFBibTeX XMLCite \textit{J.-y. Cai} and \textit{L. A. Hemachandra}, Math. Syst. Theory 23, No. 2, 95--106 (1990; Zbl 0718.68038) Full Text: DOI