Found 16 Documents (Results 1–16)
Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. (English) Zbl 07765252
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 1330-1342 (2021).
MSC:
68Qxx
Tangible reduction in learning sample complexity with large classical samples and small quantum system. (English) Zbl 1508.81539
MSC:
81P68
The hardest halfspace. (English) Zbl 1508.68122
Quantum query-to-communication simulation needs a logarithmic overhead. (English) Zbl 07561760
Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 32, 15 p. (2020).
MSC:
68Q25
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates. (English) Zbl 1495.68065
Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 15, 41 p. (2020).
The polynomial method strikes back: tight quantum query bounds via dual polynomials. (English) Zbl 1462.68060
Algorithmic polynomials. (English) Zbl 1495.68096
Optimal separation and strong direct sum for randomized query complexity. (English) Zbl 07564429
Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 29, 17 p. (2019).
MSC:
68Q25
Formula lower bounds via the quantum method. (English) Zbl 1370.68142
Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 1256-1268 (2017).
Separations in query complexity using cheat sheets. (English) Zbl 1373.68216
Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 863-876 (2016).
Bounded indistinguishability and the complexity of recovering secrets. (English) Zbl 1406.94027
Robshaw, Matthew (ed.) et al., Advances in cryptology – CRYPTO 2016. 36th annual international cryptology conference, Santa Barbara, CA, USA, August 14–18, 2016. Proceedings. Part III. Berlin: Springer (ISBN 978-3-662-53014-6/pbk; 978-3-662-53015-3/ebook). Lecture Notes in Computer Science 9816, 593-618 (2016).
MSC:
94A60
Filter Results by …
Document Type
- Journal Articles (9)
- Collection Articles (7)
all
top 5
Author
- Kothari, Robin (3)
- Sherstov, Alexander A. (3)
- Aaronson, Scott (2)
- Ben-David, Shalev (2)
- Bun, Mark (2)
- Tal, Avishay (2)
- Thaler, Justin (2)
- Bang, Jeongho (1)
- Blais, Eric (1)
- Bogdanov, Andrej (1)
- Brody, Joshua E. (1)
- Chakraborty, Sourav (1)
- Chattopadhyay, Arkadev (1)
- Drucker, Andrew (1)
- Ishai, Yuval (1)
- Jain, Rahul (1)
- Kabanets, Valentine (1)
- Kim, Jaewan (1)
- Klauck, Hartmut (1)
- Koroth, Sajin (1)
- Lee, Jinhyoung (1)
- Liu, Nana (1)
- Lu, Zhenjian (1)
- Malykhin, Yuriĭ Vyacheslavovich (1)
- Mande, Nikhil S. (1)
- Myrisiotis, Dimitrios (1)
- Oliveira, Igor Carboni (1)
- Paraashar, Manaswi (1)
- Pawłowski, Marcin (1)
- Rao, Shravas K. (1)
- Ryutin, Konstantin S. (1)
- Santha, Miklos (1)
- Song, Wooyeong (1)
- Viola, Emanuele (1)
- Wieśniak, Marcin (1)
- Williamson, Christopher (1)
