×

Found 172 Documents (Results 1–100)

Type-two polynomial-time and restricted lookahead. (English) Zbl 1452.03097

Proceedings of the 2018 33rd annual ACM/IEEE symposium on logic in computer science, LICS 2018, Oxford, UK, July 9–12, 2018. New York, NY: Association for Computing Machinery (ACM). 579-588 (2018).
MSC:  03D65 03B40
PDFBibTeX XMLCite
Full Text: DOI arXiv

A hierarchy for BPP//log\(\star\) based on counting calls to an oracle. (English) Zbl 1396.68049

Adamatzky, Andrew (ed.), Emergent computation. A Festschrift for Selim G. Akl. Cham: Springer (ISBN 978-3-319-46375-9/hbk; 978-3-319-46376-6/ebook). Emergence, Complexity and Computation 24, 39-56 (2017).
MSC:  68Q15 68Q05 68Q87
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

Limits of random oracles in secure computation (extended abstract). (English) Zbl 1364.68206

Proceedings of the 5th conference on innovations in theoretical computer science, ITCS’14, Princeton, NJ, USA, January 11–14, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2243-0). 23-33 (2014).
MSC:  68Q05 68Q10 94A60
PDFBibTeX XMLCite
Full Text: DOI

Physical aspects of oracles for randomness and Hadamard’s conjecture. (English) Zbl 1323.68281

Calude, Cristian S. (ed.) et al., Computing with new resources. Essays dedicated to Jozef Gruska on the occasion of his 80th birthday. Cham: Springer (ISBN 978-3-319-13349-2/pbk; 978-3-319-13350-8/ebook). Lecture Notes in Computer Science 8808, 223-230 (2014).
MSC:  68Q05 65C10 68Q87 81P68
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the query complexity of real functionals. (English) Zbl 1366.03218

Proceedings of the 2013 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, Tulane University, New Orleans, LA, USA, June 25–28, 2013. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-5020-6). 103-112 (2013).
MSC:  03D78 03D10 03D15
PDFBibTeX XMLCite
Full Text: DOI

Relativizations of the P =? DNP question for the BSS model. (English) Zbl 1247.68087

Bauer, Andrej (ed.) et al., 6th international conference on computability and complexity in analysis (CCA’09). Proceedings of the international conference, August 18–22, 2009, Ljubljana, Slovenia. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-12-5). OASIcs – OpenAccess Series in Informatics 11, 8 p., electronic only (2009).
MSC:  68Q05 68Q15
PDFBibTeX XMLCite
Full Text: DOI

Complexity of operators on compact sets. (English) Zbl 1262.03061

Dilhage, R. (ed.) et al., Proceedings of the fourth international conference on computability and complexity in analysis (CCA 2007), Siena, Italy, June 16–18, 2007. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 202, 101-119 (2008).
MSC:  03D15 03D80 54D30 68Q05 68Q15
PDFBibTeX XMLCite
Full Text: DOI

On relativizations of the P =? NP question for several structures. (English) Zbl 1262.68043

Brattka, V. (ed.) et al., Proceedings of the fifth international conference on computability and complexity in analysis (CCA 2008), Hagen, Germany, August 21–24, 2008. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 221, 71-83 (2008).
MSC:  68Q15 03D10 03D78 68Q05
PDFBibTeX XMLCite
Full Text: DOI

A note on universal measures for weak implicit computational complexity. (English) Zbl 1023.03033

Baaz, Matthias (ed.) et al., Logic for programming, artificial intelligence, and reasoning. 9th international conference, LPAR 2002, Tbilisi, Georgia, October 14-18, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2514, 53-67 (2002).
PDFBibTeX XMLCite
Full Text: Link

A machine model for the complexity of NP-approximation problems. (English) Zbl 1049.68065

Păun, Gheorghe (ed.) et al., Current trends in theoretical computer science. Entering the 21st century. Based on columns and tutorials published in the Bulletin of the European Association for Theoretical Computer Science (EATCS), 1992–2000. Singapore: World Scientific (ISBN 981-02-4473-8). 4-24 (2001).
MSC:  68Q15 68Q05
PDFBibTeX XMLCite

Counting, selecting, and sorting by query-bounded machines. (English) Zbl 0791.68063

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, 196-205 (1993).
MSC:  68Q15 68P10 68Q05
PDFBibTeX XMLCite

Learning via queries to an oracle. (English) Zbl 0747.68043

Computational learning theory, Proc. 2nd Annu. Workshop, Santa Cruz, CA/USA 1989, 214-229 (1989).
MSC:  68T05
PDFBibTeX XMLCite

Filter Results by …

Document Type

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software