--- _id: '44633' author: - first_name: I. full_name: Seland, I. last_name: Seland - first_name: R. full_name: Aldrich, R. last_name: Aldrich - first_name: S. full_name: Ayllón, S. last_name: Ayllón - first_name: M. full_name: Barbovschi, M. last_name: Barbovschi - first_name: A. full_name: Bărbuță, A. last_name: Bărbuță - first_name: P. full_name: Brugarolas, P. last_name: Brugarolas - first_name: Gianna full_name: Casamassima, Gianna id: '41118' last_name: Casamassima - first_name: Kerstin full_name: Drossel, Kerstin id: '48921' last_name: Drossel - first_name: Birgit full_name: Eickelmann, Birgit id: '40387' last_name: Eickelmann orcid: 0000-0001-6124-746X - first_name: E. full_name: Gosme, E. last_name: Gosme - first_name: G. B. full_name: Gudmundsdottir, G. B. last_name: Gudmundsdottir - first_name: H. B. full_name: Holmarsdottir, H. B. last_name: Holmarsdottir - first_name: C. full_name: Hyggen, C. last_name: Hyggen - first_name: S. full_name: Lado, S. last_name: Lado - first_name: T. full_name: Tove, T. last_name: Tove - first_name: O. full_name: Kapella, O. last_name: Kapella - first_name: A. full_name: Karatzogianni, A. last_name: Karatzogianni - first_name: A. full_name: Kazani, A. last_name: Kazani - first_name: Amelie full_name: Labusch, Amelie id: '65599' last_name: Labusch - first_name: L. full_name: Mifsud, L. last_name: Mifsud - first_name: S. full_name: Olabode, S. last_name: Olabode - first_name: D. full_name: Parsanoglou, D. last_name: Parsanoglou - first_name: M. full_name: Roth, M. last_name: Roth - first_name: E.-M. full_name: Schmidt, E.-M. last_name: Schmidt - first_name: H. full_name: Shorey, H. last_name: Shorey - first_name: M. full_name: Sisask, M. last_name: Sisask - first_name: M. full_name: Symeonaki, M. last_name: Symeonaki - first_name: G. full_name: Teidla-Kunitsõn, G. last_name: Teidla-Kunitsõn - first_name: L. full_name: Zinoveva, L. last_name: Zinoveva citation: ama: Seland I, Aldrich R, Ayllón S, et al. Understanding Children and Young People as Digital Citizens. (DigiGen- Working Paper Series No.12).; 2022. apa: Seland, I., Aldrich, R., Ayllón, S., Barbovschi, M., Bărbuță, A., Brugarolas, P., Casamassima, G., Drossel, K., Eickelmann, B., Gosme, E., Gudmundsdottir, G. B., Holmarsdottir, H. B., Hyggen, C., Lado, S., Tove, T., Kapella, O., Karatzogianni, A., Kazani, A., Labusch, A., … Zinoveva, L. (2022). Understanding children and young people as digital citizens. (DigiGen- working paper series No.12). bibtex: '@book{Seland_Aldrich_Ayllón_Barbovschi_Bărbuță_Brugarolas_Casamassima_Drossel_Eickelmann_Gosme_et al._2022, title={Understanding children and young people as digital citizens. (DigiGen- working paper series No.12)}, author={Seland, I. and Aldrich, R. and Ayllón, S. and Barbovschi, M. and Bărbuță, A. and Brugarolas, P. and Casamassima, Gianna and Drossel, Kerstin and Eickelmann, Birgit and Gosme, E. and et al.}, year={2022} }' chicago: Seland, I., R. Aldrich, S. Ayllón, M. Barbovschi, A. Bărbuță, P. Brugarolas, Gianna Casamassima, et al. Understanding Children and Young People as Digital Citizens. (DigiGen- Working Paper Series No.12), 2022. ieee: I. Seland et al., Understanding children and young people as digital citizens. (DigiGen- working paper series No.12). 2022. mla: Seland, I., et al. Understanding Children and Young People as Digital Citizens. (DigiGen- Working Paper Series No.12). 2022. short: I. Seland, R. Aldrich, S. Ayllón, M. Barbovschi, A. Bărbuță, P. Brugarolas, G. Casamassima, K. Drossel, B. Eickelmann, E. Gosme, G.B. Gudmundsdottir, H.B. Holmarsdottir, C. Hyggen, S. Lado, T. Tove, O. Kapella, A. Karatzogianni, A. Kazani, A. Labusch, L. Mifsud, S. Olabode, D. Parsanoglou, M. Roth, E.-M. Schmidt, H. Shorey, M. Sisask, M. Symeonaki, G. Teidla-Kunitsõn, L. Zinoveva, Understanding Children and Young People as Digital Citizens. (DigiGen- Working Paper Series No.12), 2022. date_created: 2023-05-08T11:56:34Z date_updated: 2026-04-28T08:34:11Z department: - _id: '462' language: - iso: eng main_file_link: - url: https://digigen.eu/wp-content/uploads/2022/12/DigiGen_7._1_WorkingPaper_Final.pdf status: public title: Understanding children and young people as digital citizens. (DigiGen- working paper series No.12) type: report user_id: '40387' year: '2022' ... --- _id: '65532' author: - first_name: Jan full_name: Jancar, Jan last_name: Jancar - first_name: Marcel full_name: Fourné, Marcel last_name: Fourné - first_name: Daniel De Almeida full_name: Braga, Daniel De Almeida last_name: Braga - first_name: Mohamed full_name: Sabt, Mohamed last_name: Sabt - first_name: Peter full_name: Schwabe, Peter last_name: Schwabe - first_name: Gilles full_name: Barthe, Gilles last_name: Barthe - first_name: Pierre-Alain full_name: Fouque, Pierre-Alain last_name: Fouque - first_name: Yasemin full_name: Acar, Yasemin last_name: Acar citation: ama: 'Jancar J, Fourné M, Braga DDA, et al. “They’re not that hard to mitigate”: What Cryptographic Library Developers Think About Timing Attacks. In: 2022 IEEE Symposium on Security and Privacy (SP). IEEE; 2022. doi:10.1109/sp46214.2022.9833713' apa: 'Jancar, J., Fourné, M., Braga, D. D. A., Sabt, M., Schwabe, P., Barthe, G., Fouque, P.-A., & Acar, Y. (2022). “They’re not that hard to mitigate”: What Cryptographic Library Developers Think About Timing Attacks. 2022 IEEE Symposium on Security and Privacy (SP). https://doi.org/10.1109/sp46214.2022.9833713' bibtex: '@inproceedings{Jancar_Fourné_Braga_Sabt_Schwabe_Barthe_Fouque_Acar_2022, title={“They’re not that hard to mitigate”: What Cryptographic Library Developers Think About Timing Attacks}, DOI={10.1109/sp46214.2022.9833713}, booktitle={2022 IEEE Symposium on Security and Privacy (SP)}, publisher={IEEE}, author={Jancar, Jan and Fourné, Marcel and Braga, Daniel De Almeida and Sabt, Mohamed and Schwabe, Peter and Barthe, Gilles and Fouque, Pierre-Alain and Acar, Yasemin}, year={2022} }' chicago: 'Jancar, Jan, Marcel Fourné, Daniel De Almeida Braga, Mohamed Sabt, Peter Schwabe, Gilles Barthe, Pierre-Alain Fouque, and Yasemin Acar. “‘They’re Not That Hard to Mitigate’: What Cryptographic Library Developers Think About Timing Attacks.” In 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022. https://doi.org/10.1109/sp46214.2022.9833713.' ieee: 'J. Jancar et al., “‘They’re not that hard to mitigate’: What Cryptographic Library Developers Think About Timing Attacks,” 2022, doi: 10.1109/sp46214.2022.9833713.' mla: 'Jancar, Jan, et al. “‘They’re Not That Hard to Mitigate’: What Cryptographic Library Developers Think About Timing Attacks.” 2022 IEEE Symposium on Security and Privacy (SP), IEEE, 2022, doi:10.1109/sp46214.2022.9833713.' short: 'J. Jancar, M. Fourné, D.D.A. Braga, M. Sabt, P. Schwabe, G. Barthe, P.-A. Fouque, Y. Acar, in: 2022 IEEE Symposium on Security and Privacy (SP), IEEE, 2022.' date_created: 2026-04-30T09:27:16Z date_updated: 2026-04-30T09:32:44Z doi: 10.1109/sp46214.2022.9833713 publication: 2022 IEEE Symposium on Security and Privacy (SP) publication_status: published publisher: IEEE status: public title: '“They’re not that hard to mitigate”: What Cryptographic Library Developers Think About Timing Attacks' type: conference user_id: '125442' year: '2022' ... --- _id: '27160' abstract: - lang: eng text: "We study the complexity of problems solvable in deterministic polynomial time\r\nwith access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$\r\nand $P^{QMA}$, respectively. The former allows one to classify problems more\r\nfinely than the Polynomial-Time Hierarchy (PH), whereas the latter\r\ncharacterizes physically motivated problems such as Approximate Simulation\r\n(APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by\r\nthe classes $P^{NP[\\log]}$ and $P^{QMA[\\log]}$, defined identically to $P^{NP}$\r\nand $P^{QMA}$, except that only logarithmically many oracle queries are\r\nallowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by\r\na $P^{NP}$ machine have a \"query graph\" which is a tree, then this computation\r\ncan be simulated in $P^{NP[\\log]}$.\r\n In this work, we first show that for any verification class\r\n$C\\in\\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\\exp}\\}$, any $P^C$ machine with a query\r\ngraph of \"separator number\" $s$ can be simulated using deterministic time\r\n$\\exp(s\\log n)$ and $s\\log n$ queries to a $C$-oracle. When $s\\in O(1)$ (which\r\nincludes the case of $O(1)$-treewidth, and thus also of trees), this gives an\r\nupper bound of $P^{C[\\log]}$, and when $s\\in O(\\log^k(n))$, this yields bound\r\n$QP^{C[\\log^{k+1}]}$ (QP meaning quasi-polynomial time). We next show how to\r\ncombine Gottlob's \"admissible-weighting function\" framework with the\r\n\"flag-qubit\" framework of [Watson, Bausch, Gharibian, 2020], obtaining a\r\nunified approach for embedding $P^C$ computations directly into APX-SIM\r\ninstances in a black-box fashion. Finally, we formalize a simple no-go\r\nstatement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear\r\npolynomial $p$ specified via an arithmetic circuit, if one can \"weakly\r\ncompress\" $p$ so that its optimal value requires $m$ bits to represent, then\r\n$P^{NP}$ can be decided with only $m$ queries to an NP-oracle." author: - first_name: Sevag full_name: Gharibian, Sevag id: '71541' last_name: Gharibian orcid: 0000-0002-9992-3379 - first_name: Dorian full_name: Rudolph, Dorian id: '57863' last_name: Rudolph citation: ama: 'Gharibian S, Rudolph D. On polynomially many queries to NP or QMA oracles. In: 13th Innovations in Theoretical Computer Science (ITCS 2022). Vol 215. ; 2022:1-27. doi:10.4230/LIPIcs.ITCS.2022.75' apa: Gharibian, S., & Rudolph, D. (2022). On polynomially many queries to NP or QMA oracles. 13th Innovations in Theoretical Computer Science (ITCS 2022), 215(75), 1–27. https://doi.org/10.4230/LIPIcs.ITCS.2022.75 bibtex: '@inproceedings{Gharibian_Rudolph_2022, title={On polynomially many queries to NP or QMA oracles}, volume={215}, DOI={10.4230/LIPIcs.ITCS.2022.75}, number={75}, booktitle={13th Innovations in Theoretical Computer Science (ITCS 2022)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022}, pages={1–27} }' chicago: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” In 13th Innovations in Theoretical Computer Science (ITCS 2022), 215:1–27, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.75. ieee: 'S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,” in 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, vol. 215, no. 75, pp. 1–27, doi: 10.4230/LIPIcs.ITCS.2022.75.' mla: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” 13th Innovations in Theoretical Computer Science (ITCS 2022), vol. 215, no. 75, 2022, pp. 1–27, doi:10.4230/LIPIcs.ITCS.2022.75. short: 'S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27.' date_created: 2021-11-05T08:08:29Z date_updated: 2026-04-30T14:11:00Z department: - _id: '623' - _id: '7' doi: 10.4230/LIPIcs.ITCS.2022.75 intvolume: ' 215' issue: '75' language: - iso: eng main_file_link: - open_access: '1' url: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15671 oa: '1' page: 1-27 publication: 13th Innovations in Theoretical Computer Science (ITCS 2022) status: public title: On polynomially many queries to NP or QMA oracles type: conference user_id: '71541' volume: 215 year: '2022' ...