×

Found 44 Documents (Results 1–44)

Oracle separation of BQP and PH. (English) Zbl 1433.68152

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 13-23 (2019).
MSC:  68Q15 68Q06 68Q12
PDFBibTeX XMLCite
Full Text: DOI

The space “just above” BQP. (English) Zbl 1334.68075

Proceedings of the 7th ACM conference on innovations in theoretical computer science, ITCS’16, Cambridge, MA, USA, January 14–16, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4057-1). 271-280 (2016).
MSC:  68Q12 68Q05 68Q15 68Q17 81P68
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tissue P systems with cell separation: upper bound by PSPACE. (English) Zbl 1374.68222

Dediu, Adrian-Horia (ed.) et al., Theory and practice of natural computing. First international conference, TPNC 2012, Tarragona, Spain, October 2–4, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-33859-5/pbk). Lecture Notes in Computer Science 7505, 201-215 (2012).
MSC:  68Q05 68Q10 68Q15
PDFBibTeX XMLCite
Full Text: DOI

Separating succinct non-interactive arguments from all falsifiable assumptions. (English) Zbl 1288.94063

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). 99-108 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Speeding-up nondeterministic single-tape off-line computations by one alternation (extended abstract). (English) Zbl 0912.03022

Brim, Luboš (ed.) et al., Mathematical foundations of computer science 1998. 23rd international symposium, MFCS ’98. Brno, Czech Republic, August 24–28, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1450, 607-615 (1998).
MSC:  03D15 68Q15 03D10
PDFBibTeX XMLCite

Separating the lower levels of the sublogarithmic space hierarchy. (English) Zbl 0799.68092

Enjalbert, Patrice (ed.) et al., STACS 93. 10th annual symposium on theoretical aspects of computer science, Würzburg, Germany, February 25-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 665, 16-27 (1993).
MSC:  68Q15
PDFBibTeX XMLCite

Bounded reductions. (English) Zbl 0788.68049

Ambos-Spies, Klaus (ed.) et al., Complexity theory. Current research. Proceedings of the workshop on structure and complexity held at the Dagstuhl International Conference and Research Center, Wadern, Germany, February 2-8, 1992. Cambridge: Cambridge University Press. 83-99 (1993).
MSC:  68Q15 03D15
PDFBibTeX XMLCite

Separating counting communication complexity classes. (English) Zbl 1493.68149

Finkel, A. (ed.) et al., STACS 92. Theoretical aspects of computer science. Proceedings of the 9th annual symposium, Cachan, France, February 13–15, 1992. Berlin: Springer. Lect. Notes Comput. Sci. 577, 281-292 (1992).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field