Ausgabe 2/2022
Inhalt (11 Artikel)
Quadratic Lower Bounds for Algebraic Branching Programs and Formulas
Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
Open Access
Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Open Access
A cost-scaling algorithm for computing the degree of determinants
Hiroshi Hirai, Motoki Ikeda
Open Access
Zeros and approximations of Holant polynomials on the complex plane
Katrin Casel, Philipp Fischbeck, Tobias Friedrich, Andreas Göbel, J. A. Gregor Lagodzinski
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
Quantum versus Randomized Communication Complexity, with Efficient Players
Uma Girish, Ran Raz, Avishay Tal