:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Chen, Yanlin, Chen, Yilei, Kumar, Rajendra, Patro, Subhasree, Speelman, Florian
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Computational Complexity F.2.0
Online Access:	https://arxiv.org/abs/2309.16431
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fine-Grained Complexity via Quantum Natural Proofs
by: Chen, Yanlin, et al.
Published: (2025)

Quantum algorithms for path and cycle containment problems
by: Cornelissen, Arjan, et al.
Published: (2026)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
by: Cornelissen, Arjan, et al.
Published: (2022)

Quantum Sabotage Complexity
by: Cornelissen, Arjan, et al.
Published: (2024)

Quantum Search With Generalized Wildcards
by: Cornelissen, Arjan, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Complexity and algorithms for Swap median and relation to other consensus problems
by: Cunha, Luís, et al.
Published: (2024)

Constructibility and the P versus NP problem
by: Hole, Arne
Published: (2024)

Fully Characterizing Lossy Catalytic Computation
by: Folkertsma, Marten, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

An unconditional lower bound for the active-set method on the hypercube
by: Disser, Yann, et al.
Published: (2025)

Embedding formulae for diffraction problems on square lattices
by: Korolkov, A. I., et al.
Published: (2026)

Optimal lower bounds for quantum state tomography
by: Scharnhorst, Thilo, et al.
Published: (2025)

Eulerian orientations and Hadamard codes: A novel connection via counting
by: Shao, Shuai, et al.
Published: (2024)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
by: Fan, Austen, et al.
Published: (2026)

On Coefficient problems for \textbf{$S^*_ρ$}
by: Kumar, S. Sivaprasad, et al.
Published: (2024)

New examples of CR submanifolds for the $2$-jet determination problem
by: Bertrand, Florian, et al.
Published: (2025)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
by: Cheval, Vincent, et al.
Published: (2025)

A quasi-optimal lower bound for skew polynomial multiplication
by: Chen, Qiyuan, et al.
Published: (2024)

An unconditional lower bound for the active-set method in convex quadratic maximization
by: Bach, Eleon, et al.
Published: (2025)

Depth lower bounds in Stabbing Planes for combinatorial principles
by: Dantchev, Stefan, et al.
Published: (2021)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
by: Chen, Zitan
Published: (2023)

A Note On The Natural Range Of Unambiguous-SAT
by: Pay, Tayfun
Published: (2023)

The dihedral hidden subgroup problem
by: Chen, Imin, et al.
Published: (2021)

Type problem and the first eigenvalue
by: Chen, Bo-Yong, et al.
Published: (2024)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

Dirichlet problem for plurisubharmonic functions on bounded quasi B-regular domains in $\mathbb{C}^n$
by: Dieu, N. Q., et al.
Published: (2025)

Coefficient problems of Starlike Functions Related to a Balloon-Shaped Domain
by: Kumar, S. Sivaprasad, et al.
Published: (2026)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Lattice Based Crypto breaks in a Superposition of Spacetimes
by: Aggarwal, Divesh, et al.
Published: (2025)

The membership problem for constant-sized quantum correlations is undecidable
by: Fu, Honghao, et al.
Published: (2021)

A simplified version of the quantum OTOC$^{(2)}$ problem
by: King, Robbie, et al.
Published: (2025)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
by: Chia, Nai-Hui, et al.
Published: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
by: Gordeev, Lev, et al.
Published: (2026)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
by: Goubault-Larrecq, Aliénor, et al.
Published: (2025)